NOIP 2006年普及组解题报告

1、DP，f表示合并区间内的珠子获得最大能源2、DP，可以先把主件和附件的搭配全部分出来，然后分阶段做背包3、模拟4、递推+高精度1．这题具有最优子结构的性质，与合并石子相似，所以可以用动态规划来做。

首先将数据存于c数组中，每次需要枚举一下起始点i和终点j的位置，还要枚举起点和终点之间一个断点k的位置，表示第i—k个珠子已经合并在了一起，第k—j个珠子也已经合并在了一起，当前要合并的是这两个已经合并在了一起的小珠子，这样就把一个问题分成了许多子问题。

当前一次操作所产生的能量K=c[i]*c[k]*c[j]具体做法是：开一个二维数组a，a[i,j]表示从i开始到j结束这一段中所有珠子合并所能产生的能量的最大值。

然后先枚举段的长度i（i为2到N），接着枚举开始位置j，由i, j 可推出结束位置k。

然后枚举断点位置v，v为j+1到k-1之间。

在每个断点处断开所能获得的能量为K=c[j]*c[v]*c[k]+a[j,v]+a[v,k]。

取这中间的一个最大值赋给a[j , k]。

这样做的时间复杂度为O(n3)，因为N<=100，所以时间上肯定没有问题。

最后a[i,i]的最大值就是合并所有珠子后所能产生的能量的最大值。

constmaxn=100;varc:array[0..maxn] of longint;a:array[0..maxn,0..maxn] of longint;n,i,j,k,t,v,u,max:longint;beginassign(input,'energy.in'); reset(input);assign(output,'energy.out'); rewrite(output);readln(n);for i:=0 to n-1 do read(c[i]);fillchar(a,sizeof(a),0);for i:=2 to n do beginfor j:=0 to n-1 do begink:=(j+i) mod n;max:=0;for v:=j+1 to j+i-1 do beginu:=v mod n;t:=c[j]*c[u]*c[k]+a[j,u]+a[u,k];if t>max then max:=t;end;a[j,k]:=max;end;end;max:=0;for i:=0 to n-1 doif a[i,i]>max then max:=a[i,i];writeln(max);close(input); close(output)end.2、此题初看MS是01背包问题，只是多了附件这个条件。

第十二届全国青少年信息学奥林匹克联赛初赛试题 2006（普及组C++ 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案.）1. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。

A. 沃尔夫奖B. 诺贝尔奖C. 菲尔兹奖D. 图灵奖2. 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A. gcc/g++B. Turbo PascalC. RHIDED. free pascal3. 以下断电之后仍能保存数据的有（）。

A. 寄存器B. ROMC. RAMD. 高速缓存4．Linux是一种( )。

A. 绘图软件B. 程序设计语言C. 操作系统D. 网络浏览器5. CPU是( )的简称。

A. 硬盘B. 中央处理器C. 高级程序语言D. 核心寄存器6. 在计算机中，防火墙的作用是（）。

A. 防止火灾蔓延B.防止网络攻击C. 防止计算机死机D. 防止使用者误删除数据7. 在下列关于计算机语言的说法中，不正确的是（）。

A. Pascal和C都是编译执行的高级语言B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C. C++是历史上的第一个支持面向对象的计算机语言D. 与汇编语言相比，高级语言程序更容易阅读8. 在下列关于计算机算法的说法中，不正确的是（）。

A. 一个正确的算法至少要有一个输入B. 算法的改进，在很大程度上推动了计算机科学与技术的进步C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。

A. 选择排序B. 冒泡排序C. 插入排序D. 基数排序10．在编程时（使用任一种高级语言，不一定是C++），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

第十二届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案.）。

1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。

A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖2.在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A.gcc/g++B.Turbo PascalC.RHIDED.free pascal3.以下断电之后仍能保存数据的有（）。

A.寄存器B.ROMC.RAMD.高速缓存4．Linux是一种()。

A.绘图软件B.程序设计语言C.操作系统D.网络浏览器5.CPU是()的简称。

A.硬盘B.中央处理器C.高级程序语言D.核心寄存器6.在计算机中，防火墙的作用是（）。

A.防止火灾蔓延B.防止网络攻击C.防止计算机死机D.防止使用者误删除数据7.在下列关于计算机语言的说法中，不正确的是（）。

A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C++是历史上的第一个支持面向对象的计算机语言D.与汇编语言相比，高级语言程序更容易阅读8.在下列关于计算机算法的说法中，不正确的是（）。

A.一个正确的算法至少要有一个输入B.算法的改进，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。

A.选择排序B.冒泡排序C.插入排序D.基数排序10．在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

【NOIP2006普及组】开⼼的⾦明
看过题后，你可能会发现这是很典型的0-1背包问题，即要么选择这件要么不选。

0-1背包问题最经典的解法就是动态规划了。

当然这道题的数据范围较⼩，也可以⽤暴搜（暴⼒搜索）来做，即枚举所有情况。

我们⽤递归来实现⼀下。

对于每⼀件物品就模拟两种情况选或者不选，千万不要漏掉哪⼀种情况，最后求取最⼤值就好了。

（由于我们当时模拟赛，所以写了⽂件读取数据，请见谅。

）
好了，暴搜的解法就介绍到这⾥，接下来，要介绍经典解法——动态规划。

动态规划最重要的就是建⽴递推式，根据上⾯讲解我们已经明确了对于每个物品依次检查选或不选，⽤dp[i][j]表⽰前 i 个物品在 j ⾦额下的最优解（结果最⼤）。

如果j放不下第i个物品的话，那么就只能从编号为[1,i-1]的物品中选择了，也就是dp[i-1][j]的值。

所以，
dp[i][j] = dp[i-1][j]; （其中，j < v[i]）
那么j可以放的下这个物品的时候应该怎么办呢？很明显，我们有两种选择，选或不选，之后我们取较⼤的值。

选 dp[i-1][j-v[i]]+v[i]*p[i];
不选 dp[i-1][j];
所以我们得到递推式
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]*p[i]);（其中，j>=v[i]）
把两种情况整理⼀下，
怎么样？思路明确多了吧！
根据递推式来写代码就好了。

最后附上AC代码。

第十二届全国青少年信息学奥林匹克联赛初赛试题 2006（普及组C++ 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案.）1. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。

A. 沃尔夫奖B. 诺贝尔奖C. 菲尔兹奖D. 图灵奖2. 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A. gcc/g++B. Turbo PascalC. RHIDED. free pascal3. 以下断电之后仍能保存数据的有（）。

A. 寄存器B. ROMC. RAMD. 高速缓存4．Linux是一种( )。

A. 绘图软件B. 程序设计语言C. 操作系统D. 网络浏览器5. CPU是( )的简称。

A. 硬盘B. 中央处理器C. 高级程序语言D. 核心寄存器6. 在计算机中，防火墙的作用是（）。

A. 防止火灾蔓延B.防止网络攻击C. 防止计算机死机D. 防止使用者误删除数据7. 在下列关于计算机语言的说法中，不正确的是（）。

A. Pascal和C都是编译执行的高级语言B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C. C++是历史上的第一个支持面向对象的计算机语言D. 与汇编语言相比，高级语言程序更容易阅读8. 在下列关于计算机算法的说法中，不正确的是（）。

A. 一个正确的算法至少要有一个输入B. 算法的改进，在很大程度上推动了计算机科学与技术的进步C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。

A. 选择排序B. 冒泡排序C. 插入排序D. 基数排序10．在编程时（使用任一种高级语言，不一定是C++），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

NOIP2006复赛普及组解题报告【第一题解题思想】：这道题属于容易题，但是题目难度大于NOIP2005和2004普及组第一题，和去年第二题难度相当后者略低一些。

解法1：我们可以用先去掉重复（读入第i个数，和他前面的i-1个数比较），然后用简单排序和冒泡排序排序，最后输出结果。

解法2：运用插入排序（略加修改），边排序边除掉重复。

解法3：直接排序，不去掉重复，计算出不重复的元素个数，输出不重复的元素即可。

如果用数组A存储这些随机数，对于2到N个元素需要比较A是否等于A[i-1]。

解法4：开一个1到1000初值均为假的布尔数组A。

用整型变量X读入N个随机数，赋A[X]的值为真。

统计数组中值为真的元素个数即M，从i从1到1000输出A值为真的i。

这种方法可以算作哈希表的简单应用。

解法5：很多人想到排序，效率大概是O(n^2)吧，其实还有个更简单的方法。

用一个1到1000的数组储存每个数的出现情况，t每出现一次，a[t]=a[t]+1，而且，同时操作if(a[t]>1) 则总数=总数-1。

然后从1到1000的循环，如果a≠0，输出，这样就根本不用排序了。

大概这个应该是最优算法吧。

O(n)的效率。

program random(input,output);var a:array[1..1000] of integer; / ’a是记录数组，相当于数轴，与数一一对应，temp 是临时存储数据，n和题目一样，记录不相同的数的个数’ /i,m,temp,n:integer;beginassign(input,'d:\data\random.in');reset(input);assign(output,'d:\data\random.out');rewrite(output);read(n);readln;fillchar(a,sizeof(a),0); /*初始化数组为0，pascal有fillchar*/m:=n;for i:=1 to n dobeginread(temp);a[temp]:=a[temp]+1; /*记录是哪个数*/if a[temp]>1 then dec(m);end;write(m);writeln;for i:=1 to 1000 doif a>0 then / *如果a不为0。

第十二届全国青少年信息学奥林匹克联赛初赛试题（2006 NOIP 普及组C++ 语言二小时完成）一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案.）。

1. 在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。

A. 沃尔夫奖B. 诺贝尔奖C. 菲尔兹奖D. 图灵奖2. 在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A. gcc/g++B. Turbo PascalC. RHIDED. free pascal3. 以下断电之后仍能保存数据的有（）。

A. 寄存器B. ROMC. RAMD. 高速缓存4．Linux是一种( )。

A. 绘图软件B. 程序设计语言C. 操作系统D. 网络浏览器5. CPU是( )的简称。

A. 硬盘B. 中央处理器C. 高级程序语言D. 核心寄存器6. 在计算机中，防火墙的作用是（）。

A. 防止火灾蔓延B.防止网络攻击C. 防止计算机死机D. 防止使用者误删除数据7. 在下列关于计算机语言的说法中，不正确的是（）。

A. Pascal和C都是编译执行的高级语言B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C. C++是历史上的第一个支持面向对象的计算机语言D. 与汇编语言相比，高级语言程序更容易阅读8. 在下列关于计算机算法的说法中，不正确的是（）。

A. 一个正确的算法至少要有一个输入B. 算法的改进，在很大程度上推动了计算机科学与技术的进步C. 判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法9. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。

A. 选择排序B. 冒泡排序C. 插入排序D. 基数排序10．在编程时（使用任一种高级语言，不一定是C++），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000 的double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

Day1：#1：网络收费(network)这道题完全不会，当时写了个搜索拿了40分把配对收费规则转化一下，对于任两个用户i,j，设它们的最近公共祖先(LCA)是p如果在p上na<nb，则i,j中谁是A谁支付F[i,j]的费用如果在p上na≥nb，则i,j中谁是B谁支付F[i,j]的费用这样的转化让点对交费转移到单点交费，为dp提供了前提，且最后的总费用不变整个模型是一棵完全二叉树，设计树形dpdp[i,j,k]：在点i所管辖的所有用户中，有j个用户为A在i的每个祖先u上，如果na<nb，则标0，否则标1，这个数列可以用二进制表示，用k记录在这种情况下的最少花费状态转移方程：其实就是将j个用户分配给i的左右子节点，并更改kdp[i,j,k]=min{dp[i.lt,u,k+%s],dp[i.rt,j-u,k+%s]}+%s表示在数列上加入节点i的标号，i.lt、i.rt分别表示i的左右子节点边界：当i是叶节点时，可以根据k算出i与其它用户配对收费时所要交的费用，再根据i的初始情况加上AB的转化费用复杂度分析：设m=2n粗略看来，空间复杂度是O(m3)，时间复杂度是O(m4)，对于本题的数据可以同时MLE和TLE了如果你看到这样复杂度就想别的方法了，那我只能同情你了，因为这只是很粗略的复杂度分析把根节点看做第0层，叶节点就是第n层，对于任意的第i层，A用户的个数最多只有2n-i，而祖先结点只有i个，即k最大只有2i把dp[i,j,k]的后两维合并成一维，空间复杂度其实只有O(m2)再看时间复杂度，对于第i层，有2i个节点，每个节点的状态数是O(m)的，状态转移的复杂度是O(2n-i)，所以每层的复杂度是O(m2)总共有n层，所以状态转移的时间复杂度是O(m2n)考虑边界，如果是朴素的计算费用，即枚举所有用户(O(m))，再算出LCA(O(n))，复杂度是O(mn)边界数高达O(m2)，这样计算边界的复杂度就是O(m3n)！加一些预处理，提前算出所有点的LCA，复杂度是O(m2n)设dpx[i,j]表示第i个用户，在向上数第j个祖先节点处配对收费时所要交的费用，dpx可以在O(m2n)的时间内计算出来计算每个边界时可以根据k在O(n)时间内计算出配对费用，这样计算边界的复杂度降到O(m2n)至此空间复杂度和时间复杂度都降到了可以承受的地步，在具体实现时，要用记忆化搜索和二进制的位运算ps.说了一大堆，感觉不如直接看我的程序#2：生日快乐(happybirthday)这次NOI唯一一道做得比较满意的题目，算法和标准算法完全一样，得分90数据结构就是二叉树，为了使之平衡，这里用treap（当然也可以用splay，不过好像treap比splay快一些）为了记录每个元素排序后的位置，每个节点加num记录该节点为根的子树上的节点总数每次收到一个礼物，将它插入到treap中，根据num可以得到它的位置pl然后根据男生或女生得到要吃掉的礼物的位置（pl±L），根据num确定该节点s如果s不存在或者没有果冻，那么tell(-1)否则将s从treap中删除（先把s移到叶节点，然后删除），改变s的果冻数，然后重新插入到treap中注意在操作中更改num的值时间复杂度是O(nlogn)ps.重新编了一下，最后一个数据仍然TLE，大概我的treap写垃圾了- -b#3：千年虫(worm)用一个小时看出来是用dp，用一个小时优化方程，交上去以后才发现：方程写错了后来听人说这道题和HNOI的某道题一样，抓狂，后悔没做省选题……如果你语文够强，在分析完题目的描述以后应该可以得到这样的结论：以一边为例，则千年虫的外形是一个类似梳子的样子（事实上，HNOI那道题好像就是叫梳子），就是一段高，一段低而我们要做的，就是添加尽量少的方块，使得外形满足上诉的样子，这样很容易想到dp设dp[i,j,s]表示前i行，第i行的状态是s（s=0，第i行处于凹的一段；s=1，第i行处于凸的一段），且第i 行的最终高度是j的状态下最小添加的方块数dp[i,j,s]=min{dp[i-1,j,s],dp[i-1,k,1-s](s=1,k<j s=0,k>j)}+(j-h[i])，其中h[i]是第i行的原始高度时间复杂度是O(n3)的，根据状态转移方程可以把复杂度降到O(n2)但是对于本题的极限数据，这样的复杂度仍然不能令人满意bamboo的BT方法：其实就是减少需要计算的状态量，我将其理解为建立在贪心基础上的dp对于第i行，设它的初始高度为a[i]，最终高度为b[i]能够证明的是：b[i]的取值范围只能是[a[j],a[j]+2]（|j-i|≤2）证明过程非常繁琐，大体思想就是分情况讨论，对于每种情况，或者找到确定的j，或者说明不是最优解（证明过程请参加讲题大会时的ppt，因为情况太多，我只是大概的证明了处在凹的一段）这样对于第i行只需要计算常数个最终长度，而对于每个状态的决策也只有常数个，所以复杂度是O(n)下载：worm.pptDay2：#1：最大获利(profit)NOI历史上第一道网络流的题目（为什么偏偏让我赶上了- -b）这道题和《算法艺术》317页那道题几乎一样，郁闷的发现自己看过，更郁闷的是NOI的时候忘了建立模型，将每个用户和中转站看作点，另外添加源点s，汇点t添加下列边：①s到中转站i，容量为P i②用户i到中转站A i和B i，容量为∞③用户i到t的边，容量为C i考虑这个模型的割割边不可能是②中的边，这保证了解的合法性属于①的割边表示付出的代价属于③的割边表示损失的利益显然割的量越小越好，这样这道题就转换成一个最小割的问题根据最大流最小割定理，设sum=∑C i，我们只要求出该网络的最大流maxflow，则sum-maxflow就是最大获利至此我们已经分析出了这道题的模型，但是，让我们看一下9、10两个BT数据吧，你会发现，即使用目前最快的HLPP也会严重TLE可能你也听说过要用贪心来做一个初始流，然后在这个基础上求最大流但其实不是随便贪都可以的，事实上，对于最后两个点的出解时间，在很大程度上取决于贪心的初始解与最优解的逼近程度这样的话就需要一个比较好的贪心，这里介绍一下ZhY大牛的贪心砍掉s和t，将模型缩减为一个二分图，并设cp[i]=第i个点到s或t的那条边的容量，degree[i]=∑cp[j](j 与i相邻)每次找到一个degree最小的点i，按照degree递增的顺序处理每个与它相邻的点j，在连接i,j的边上进行增广具体实现时需要用heap大概思想就是这样，至于为什么这样我也不太清楚（看的ZhY的C++的程序，按照这个思想编的，可是贪心的结果与ZhY的还是有一些差距）接下来，在求得初始流以后该如何求最大流呢？HLPP仍然严重TLE （汗）BFS求最短增广路，最大数据用时6.xx sDFS多路增广（具体实现请参见我的程序），仅仅是能卡着点过（关闭其它耗内存的东西 2.xx s，开一个wmplayer就TLE）#2：聪明的导游(guide)这道题向GHY大牛请教了一种超级BT的方法首先看最后两个数据，不难发现是一棵树对于一棵树，最优解就是这棵树上的最长路径对这个问题存在最优方法：从任一点e出发，找到e的最远点s，在从s出发，找到s的最远点t，则s到t的路径上所有点就是所求证明略过（可以参见《信息学奥林匹克竞赛－国际国内分类试题精解（上册）》78页）现在的问题是，对于一个任意图（数据1-8），如何求得最优解如果可以去掉一些边，使任意图变成一棵树，则可以用上诉方法来求最优解一个大致的算法产生了：在原图的基础上随机生成一棵树，然后求这棵树上的最优解，取其中最优的输出考虑以下两种树：显然第一种树的最优解优于第二种树在用DFS生成树的过程中加入一些贪心因素，优先扩展度小的节点在此基础上加入一些随机因素：随机确定根节点对于度数相同的节点，随机交换顺序注意这里节点的度数应不包括后向边，这就要求在DFS的过程中动态更新节点的度数ps.用这种方法应该可以得满分，但我的程序只拿到99分（第2个点9分）#3：神奇口袋(bag)这是第二试最简单的一道题，也是这次NOI最简单的一道考察的只是很简单的数学知识+高精度乘法，可惜看错题了，哭简单一些的描述就是每次随机选择一种颜色的球，将数量+d整个大框架就是乘法原理，对于每次取球，如果没有在x i中，那么这次操作称为“自由取球”，否则将颜色y i的球的数量a/此时球的总数作为乘数乘到结果中，并将颜色y i的球的数量+d，称作“定向取球”可以证明，自由取球对任意球被取到的几率P i没有影响证明很简单，就不说了这样就可以忽略掉所有的自由取球操作，即每一步都是定向取球剩下的就只是高精度乘法了对于最后分数化简的问题，因为分子分母最多只有20000，所以只要建立一个20000以内的素数表连高精度除法都不需要，只要先将分子分母都化简掉再高精度乘起来输出就行了。

NOIP2006 Solutions2006届中国信息学奥林匹克联赛提高组解题报告by FaLLeNs问题一能量项链/Energy核心算法动态规划(原型石子合并问题)时间复杂度O(n3)空间复杂度O(n2)编码复杂度<50行实测时间<0.1s分析记head[i]为第i颗能量珠的首标记，也同时是它前面那颗能量珠的尾标记。

记录Energy[i,j]为从以Head[i]为首标记的能量珠开始顺时针数到以Head[j]为尾标记的能量珠为止所有能量珠组成的串合并后放出的最大能量。

那么对于Energy[i,j]，若先合并从以Head[i]为首标记的能量珠开始顺时针数到以Head[k]为尾标记的能量珠为止的串，在合并以Head[k]为首标记的能量珠开始顺时针数到以Head[j]为尾标记的能量珠为止的串，然后将这两颗合并后的能量珠合并，放出的能量为Energy[i,k]+Energy[k,j]+Head[i]*Head[k]*Head[j]。

也就是说，状态转移方程为Energy[i,j]=Max{Energy[i,k]+Energy[k,j]+Head[i]*Head[k]*Head[j]} (i<=k<=j (i<j), k<i or k>j (i>=j))。

计算Energy[i,j]时，只会用到含有能量珠数目比它少的串在数组中的值，所以可以以串的能量珠数目为顺序规划，即按照k|(k+i) mod n=j的顺序进行规划。

评论如果枚举将能量项链变为串的开链位置，需要约n/2倍计算量，得到一个O(n4)的时间复杂度。

这是不需要的。

一个较优的贪心近似算法是每次找首标记最小的能量珠与它前面的能量珠合并。

对于NOIP中30%数据是正确的。

一个典型的反例是n=4,Head={10,3,2,3}，贪心算法得到3*2*3+10*3*3+10*10*3=408，而最优解为10*3*2+10*2*3+10*10*3=420。

[洛⾕P1062NOIP2006普及组]数列⾸先题⾯是这样的：给定⼀个正整数 k(3≤k≤15) ,把所有k的⽅幂及所有有限个互不相等的k的⽅幂之和构成⼀个递增的序列，例如，当 k=3 时，这个序列是：1,3,4,9,10,12,13,…因为所有的底数k都是相同的，所以⾃然要想到把他们的指数分离出来~~。

例如这样然后把指数分离出来：0,1,0+1,2,0+2,1+2,0+1+2,3....这时候看可能没什么头绪，但是再看⼀遍题⽬，你会发现题⽬中强调了两个字qwq——————— 递增。

也就是说我们在确定第n项时，要从之前确定的n-1项中选出⼀项：⼤于第n-1项但是⼩于⽬前能⽣成的任意⼀项，所以很容易想到：每确⽴⼀个数，就从数列的第⼀项开始逐个加上这⼀项，就造成了递增的效果。

但是这样做还有很⼤的缺陷，因为在前n-1项中，难免会有重复的项，举个最简单的例⼦：0，1，0+1，2，0+2，1+2；如果确⽴了第三项（0+1）的时候，对前⾯2项进⾏加法操作，明显会造成重复，并且不符合题⽬要求（递增和互不相等的⽅幂）。

那么这个算法就要进⾏改进。

在这⾥定义⼀下：单独数：就是不是由加法操作得到的数（k的n次⽅那种qwq）合成数：由单独数+合成数或由合成数+合成数组成的数所以对于每⼀个合成数都有单独数的参与，我们想，可不可以先预处理出k的1-n次⽅，显然⼀个快速幂就可以了，那么再想想，如果每读⼊到⼀个单独数，就可以⽤这个单独数按照刚才的⽅式来得到后⾯的n-1项。

经过验证显然是可以的。

如样例：k=3，n=100时：⽤f[i]代表第i项，有：令v=每⼀个单独数f[i]f[++i]=k(1 to n) v+f[k]⾄此这个题⽬的分析就好了.....下⾯是代码~#include<bits/stdc++.h>#define re register#define ull unsigned long longusing namespace std;int k,n,p;ull a[1000],f[2000000];inline int read() //读⼊优化{int k=1;int sum=0;char c=getchar();for(;'0'>c || c>'9';c=getchar())if(c == '-') k = -1;for(; '0' <= c && c <= '9'; c = getchar())sum = sum * 10 + c - '0';return sum * k;}inline void out(int x) //输出优化{if(x < 0) { putchar('-'); x *= -1; }if(x > 9) out(x / 10);putchar(x % 10 + '0');}inline ull quick_pow(int r,int k) //快速幂{ull base=r,ans=1;while(k!=0){if(k&1) ans=ans*base;base=base*base;k/=2;}return ans;}int main(){//freopen("sequence.in","r",stdin);//freopen("sequence.out","w",stdout);k=read();n=read();a[0]=1;a[1]=k;for(re int i=2;i<=n;i++) a[i]=quick_pow(k,i); //预处理k的1-n（保险）次幂for(re int i=1;i<=n;i++){f[i]=a[p];p++; //对于每⼀个单独数的赋值ull tmp=f[i]; //记录v值（单独数）int h=i; //确⽴i-1项（避免后来i的更新）if(i>1){{for(re int j=1;j<h;j++) {f[++i]=tmp+f[j];if(i>=n){cout<<f[n]; //输出 return 0;}}}}out(f[n]);return 0;}。