+1。显然{Fn}的通项式为Fn=2n。再把荷叶的作用考虑进去，得出利用n个石墩，m片荷叶可以过河的青蛙数为2n(m+1)。
∵arctan(1/a)=arctan(1/b)+arctan(1/c)
显然，1~n的每个数的约数个数之和，等于这些数中约数1的个数，加上约数2的个数……一直加到约数n的个数。即答案为
。然而，本题的数据组数达到了20000，而上述公式的复杂度为O(n)，在n可能达到999999的情况下，肯定会超时。怎么办呢？让我们来观察一下上面的公式都加了些什么。
把第一象限内所有满足x*y<=n的整点都描出来（右图示n=9的情况），则这些点的个数就是1~n的每个数的约数个数之和。而按上面的公式编出的循环程序在累加时，是一列一列地累加的。注意到图象右边很大一部分（绿点部分）每一列都只有极少数的点，因此循环在此浪费了大量时间。可不可以不累加这一部分呢？答案是肯定的！因为图象关于直线y=x对称，所以可以只累加一半。具体做法是，不从1累加到n，而只累加到trunc(sqrt(n))（红点组成的正方形一边上点的个数），这样就只累加了蓝点和红点的部分，累加和乘以2就是所有点数加上红点数（因为蓝点数和绿点数相等），再减去红点数，就得到答案了。这样，算法的复杂度成功地降为O(sqrt(n))。 本题很容易设计出朴素的DP算法：用cost[x]表示恰好照x张照片的花费，price[i]和count[i]表示每种照法的价格和照片数，则有cost[x]=min{cost[x-count[i]]+price[i]}，若无法正好取得x张照片，则cost[x]为无穷大。由于实际上Will照的照片可能稍多于k张，所以答案是cost[k]至cost[k+modulo-1]的最小值，其中modulo表示count[i]中的最大值。当然，计算过程需要用大小为modulo的滚动数组。
但这样做有一个显然的问题：k的值可以达到4*108，而这种算法的复杂度为O(kn)（n为照法数），必定TLE。那么如何减少计算量呢？注意到当需要的照片数足够多时，Will显然会尽量选择单价最低的照法。若用cheap表示单价最低的照法的编号（如有多个，取张数最小者），那么，当照片数到达一定数量以后，就会有cost[x]=cost[x-count[cheap]]+price[cheap]①。如果出现了这种情况，在cost数列以后的部分中每count[cheap]项取出一项，则取出的项恰构成一个等差数列，因此可直接将k缩小到略大于x的某一值（新旧k值应对模count[cheap]同余），计算出cost[k]至cost[k+modulo-1]的中的最小值，再利用等差数列的公式求出刚才跳过的部分的总价即可。
那么，从什么时候起可以保证cost数列以后的部分具有上述性质呢？有人说，在10000以后就可以基本保证这样了。然而，这并不保险。保险的做法是，如果在cost数列中发现连续count[cheap]项都满足①式，则可以大刀阔斧地砍去大量计算了。
在编程时我还发现了一个问题：如果各个count值的最大公约数大于1，那么cost数列中将会有不少无穷大项，这些项使得“连续count[cheap]项都满足①式”这一条件无法满足。解决方法是，在DP之前先求出各个count值的最大公约数g，然后用g除每个count值和k（若k mod g>0，则入上，即k:=k div g+ord(k mod g>0)）。 递推关系
（其中xi为常数）叫做k阶常系数线性递推关系，求满足此递推关系的数列的第n项的最正点的方法是矩阵乘法（简称矩乘），其复杂度为O(k3logn)。当然，这类数列通常增长都比较快，因此往往求的是第n项除以某个数的余数。先来讲一下矩阵乘法及矩阵幂的快速计算。两个矩阵可以相乘，当且仅当第一个矩阵的列数等于第二个矩阵的行数。由此亦可看出，矩乘没有交换律。现有两个矩阵A和B，A的大小为m*n，B的大小为n*p，则A*B的结果C是一个m*p的矩阵。它的每个元素满足
。矩乘的编程实现是十分简单的。计算矩阵幂，当然可以一次一次地乘。但是，由于矩乘满足结合律(A*B)*C=A*(B*C)，故可以用二分法计算矩阵幂。例如计算An时，若n为偶数，则An=An/2*An/2；若n为奇数，则An=A(n-1)/2*A(n-1)/2*A。
那么矩乘与矩阵幂在求满足k阶常系数线性递推关系的数列通项时有什么用呢？我们想办法构造一个矩阵A，使得[ap ap+1 ... ap+k-1]*A=[ap+1 ap+2 ... ap+k]。容易得出矩阵A有如下特征：
- 它的大小为k*k；
- 它的第k列为x1至xk，即递推关系中的系数；
- 第i(1<=i<k)列中除第i+1行元素为1外，其余元素均为0。
Fibonacci数列是满足k阶常系数线性递推关系的数列中比较简单的一个，它的k=2，x1=x2=1。由于它的递推关系的特殊性，本题的程序是有很大优化余地的，但我并没有进行优化，而是保留了矩乘的原始程序。
本题的实质就是输入n，判断Fibonacci数列的第n项（记作Fib[n]）是否为素数。由于Fib[n]的增长是极为迅速的，因此需要用Miller-Rabin算法来判断一个大整数是否为素数。
Miller-Rabin算法基于这样一个定理：把满足an-1 mod n=1的整数n叫做基于a的伪素数，那么，若一个数是伪素数，那么它有很大的概率是素数，而若一个数不是伪素数，它一定不是素数。Miller-Rabin的过程就是随机地选取若干个基，若对于每个基，n都是素数，则可以认为n是素数。
Miller-Rabin并不是一个确定算法。在只选一次基的情况下，一个合数是伪素数的概率的理论上界是1/4。但对于本题这么大的数据，Miller-Rabin算法出错的概率是微乎其微的（有人试过，大约是0.3%）。因此，只选一个基就可以AC了。如果觉得不保险，可以选取2-3个。
本题要求一个幂对一个数的余数，自然要用二分法。由于本题并不需要输出Fib[n]的值，因此本题的高精度可以不用十进制而用二进制（或2n进制，如我使用了32768进制）来实现，这样在求余数时可以避免试商，只需要进行移位和减法运算。
Miller-Rabin算法是很慢的，在本题规定的时限内用Miller-Rabin算法判断前500个Fib数是否为素数几乎不可能。但我们可能通过这样一条定理来省去不少Miller-Rabin测试：
若m是n的倍数，则Fib[m]是Fib[n]的倍数。
证明：当n<=2时，由于Fib[n]=1，结论显然成立。当n>=3时，设Fib[n+1] mod Fib[n]=x，则Fib[n+2] mod Fib[n]也等于x，由此可得Fib[n+i] mod Fib[n]=Fib[i]*x mod Fib[n]。所以Fib[n的倍数] mod Fib[n]=Fib[n] mod Fib[n]=0。
由此可以得出：当n>4时，若n为合数，则Fib[n]必为合数。因此本题的最终算法是这样的：
对于一个比较小的Fib数，不必用Miller-Rabin测试，直接使用普通的素数测试法即可。对于一个比较大的Fib数，先检查它的下标，若是素数再进行Miller-Rabin测试。
最后献上一条温馨提示：由于本题const的人比较多，因此n的范围在不断被扩大。猫老大说了，只要发现一个const的就加大一次数据范围。因此在程序中不要把maxn设为500，要留一点余地，比如设成1000哦:)
用sum[i,j]表示把从第i个字母开始的连续j个字母放到同一个键上的代价。这个数组可在平方级的时间内算出来。用cost[i,j]表示在i个键上放j个字母的最小代价，cut[i,j]表示在代价最小时，前i-1个键上放置的字母的个数。很容易写出状态转移方程：cost[i,j]=min{cost[i-1,k]+sum[k+1,j]},i-1<=k<=j-1，使cost[i,j]取最小值的最小的k（因为要求最后一个键上的字母尽可能多）就是cut[i,j]。这种DP的时间复杂度是立方级的。
但本题的时间复杂度还可以降至平方级。这需要用到下面这个不等式：cut[i-1,j]<=cut[i,j]<=cut[i,j+1]。这个不等式的直观理解就是：当键减少一个时，最后一个键上的字母数不会比原来少；当字母增加一个时，最后一个键上的字母同样不会比原来少。下面给出证明：
先证cut[i-1,j]<=cut[i,j]。我们采用反证法，即证若cut[i-1,j]>cut[i,j]，那么不等号右边对应的方案不是最优方案。右图表示四种不同的划分方案，每条线段表示j个字母，线段的第i段表示第i个键上的字母。我们把线段上标出的点称为分点。方案一为i-1个键，j个字母的最优划分方案，对应着不等号的左边；方案二为i个键，j个字母的某种划分方案，且满足cut[i-1,j]>cut[i,j]，它对应着不等号的右边。我们称线段的每一段（包括左分点，但不包括右分点）为一个区间。由于方案一中分点的个数比方案二少一个，故由抽屉原理，方案一中必存在这样一个区间，它在方案二中对应的位置有至少两个分点，而这个区间显然不是最后一个区间。设这一个区间为[A,B)，它在方案二中对应段上最右面两个分点称为a,b。我们仿照方案一、二构造了方案三、四。由于方案一是i-1个键，j个字母的最优划分方案，故cost1<cost3（用costi表示第i种方案中某些字母的代价，这里指所有字母的总代价）。然后我们比较cost3-cost1与cost2-cost4的大小：
对于绿色部分左边的部分，cost3=cost1，cost2=cost4，故cost3-cost1=cost2-cost4；
对于绿色部分右边的部分，cost3=cost2，cost1=cost4，故cost3-cost1=cost2-cost4；
对于绿色部分， cost3=cost2，cost1>cost4，故cost3-cost1<cost2-cost4。
三部分相加，得cost3-cost1<cost2-cost4。因为cost1<cost3，所以cost2>cost4，所以在i个键，j个字母的划分方案中，方案四比方案二优。证毕。
再证cut[i,j]<=cut[i,j+1]。同样采用反证法。右图表示四种不同的划分方案，方案一为i个键，j个字母的最优划分方案，对应着不等号的左边；方案二为i个键，j+1个字母的某种划分方案，且满足cut[i,j]>cut[i,j+1]，它对应着不等号的右边。方案四的代价与方案一的代价之差等于方案四中多出的一个字母的代价，方案二的代价与方案三的代价之差等于方案二中多出的一个字母的代价，显然前者小于后者，即cost4-cost1<cost2-cost3。又因为cost1<cost3，所以cost2>cost4，所以在i个键，j+1个字母的划分方案中，方案四比方案二优。证毕。
有了这个不等式以后，我们可以按照i递增，j递减的顺序来计算min和cut数组。这样计算每一个元素时，它所用到的元素（min[i-1,*],cut[i-1,j],cut[i,j+1]）都已求得。当然，在确定cut[i,j]的循环范围时，不要忘了i-1<=cut[i,j]<=j-1这一限制条件。下面进行时间复杂度分析。如果我们画一个直角坐标系，i轴向右，j轴向下，则每一个呈“捺”状的斜行对应的元素的cut值的范围恰好连成0..j-1，即计算每一个斜行的时间复杂度为线性的。这样的斜行的数量与问题规模同样成线性关系，因此DP的时间复杂度是平方级的。求sum数组的时间也是平方级的，故整个算法的复杂度仍为平方级。
把遗传特征看成一个有向图。找出一个包含所有特征的基因段，即遍历图中所有的边。显然，为了使基因段最短，我们应该用最少的笔数遍历图，因为每画一笔，经过的点数就要比边数多1。于是，我们只要求出整个图需要几笔画成，再加上图中的边数，就得到答案。
求一个图需要几笔画成，可以一个连通块一个连通块地计算。对于一个连通块，若它的每个点的入度和出度均相等，则它仅需一笔画成；否则，所需笔数为所有出度大于入度的点的出度与入度的差之和。
本题的模型是把起点、终点和所有的测量点看成一个图中的点，两点之间的边权为在这两点之间直线修路的费用，然后求从起点到终点的最短路。实际上这个模型是有问题的，因为有可能存在一种情况，转弯点设在山脚下，但并不在测量点。虽然题目禁止了这种方案，但我们可以将转弯点稍稍移动一下，使它离开山脚，但总费用的变化可以忽略。在此，我只能讲一下这个不完全正确的模型的解法。
求最短路用Dijkstra算法即可。关键的问题在于如何求在两点间直线修路的费用。为了求出这个费用，我们需要求出这条路在每座山内部的路程。对于一座山，我们可以求出路与山的各条边的交点。如果山的顶点也恰在路上，那么这些顶点也算在交点内。这些交点将路分成了若干段，现在我们要做的就是求出每一段是否在山内。扫描线法是容易想到了，但这种方法并不好，因为我们不能说一个是顶点的交点两侧的路段必定一个在山内，一个在山外。于是我们换一种思路：求出每一段的中点（其实段上非端点的任一点均可），判断这个中点是否在山内，以此断定这一段是否在山内。判断不在山的轮廓上的一点是否在山内，可以从这一点向远处一点（“远处”可以保证在山外）引线段，求这条线段经过的山的边数的奇偶性——若奇，则点在山内；若偶，则点在山外。为了保证这条线段不经过山的顶点，远处一点的坐标要选得不规则一些。上面的奇偶法只适用于不在山的轮廓上的点，因此在使用之前要判断点是否在边上（因为我们判断的点都不是交点，所以它不可能在顶点上），在边上的点认为在山外。
本题的运算量很大，所以要注意细节上的优化。尽量省略只使用一次的中间变量（如计算叉积、点积的函数只写一条语句），大约可以节省一半的运行时间。
由于给出了排序后方阵的最右一列，我们把这些字母排序（桶排即可）后自然可以得出方阵的最左一列。显然，方阵每一行的最后一个字母与第一个字母在原文中是相邻的（如果认为原文中最后一个字母与第一个字母也相邻的话）。我们自然产生了一种美好的设想：根据第一个字母就可以找到第二个字母，再根据第二个字母找到第三个字母……就这样按图索骥，就可以恢复出原文了！
对样例进行试验，成功。但这样做没有问题吗？有！看totoro这个单词：
| 构造字符串： totoro otorot toroto orotot rototo ototor | 将字符串排序： otorot orotot ototor rototo totoro toroto | 压缩结果： S'=ttrooo p=1 |
让我们来一下逆向思维：顺推不行，逆推行吗？答案是肯定的。所谓逆推，就是指当我们知道原文中某个字母在方阵中某一行的开头时，这一行末尾的字母就是原文中当前字母的上一个字母（把原文中最后一个字母看作第一个字母的上一个字母）。还以totoro为例：第一个字母是t。由于最左一列中相同字母是按它们本身在原文中的位置排列的，因此这个t必定是最左一列中最上面的t，即第五行的t。因此原文的最后一个字母是o。这个o自然应该是最左一列中最下面的o，即第三行的o。所以原文第五个字母是r，第四个字母是o，这个o在方阵中位于第二行第一列……哈，问题圆满解决。由于排序时运用了桶排，所以复杂度仅为O(n)。 宽搜求最短路。 开一个大小与模具相等的数组，存储每个位置被挖去的深度。然后一步一步地模拟刀片的运动，刀片每到一个在模具范围内的位置，就检查一下刀片的深度是否大于已挖去的深度。
输入中的中括号是完全没有用的。本题的一个模块是读入数字。由于分号的结束符作用，我们不必开设缓冲区存储数字后的下一个字符。哈哈，知道Pascal中为什么每条语句后面都要有分号了:) 由目标状态开始，逆用移动规则，用BFS求出变换到每个状态所需的步数，然后问哪个状态就答哪个好了。为了存储每个状态的步数，需要给每个状态编一个号。我们不妨把0至8这九个数的所有排列按字典序排序，然后从0开始编号。求一个排列的编号可以如下进行：（为简便起见，以五个数的排列24103为例）
2 4 1 0 3 //第一个数比2小的5个数的排列共有2*4!=24个
3 1 0 2 //把2去掉，剩下的数中比2大的都减小1，就成了一个0~3的排列。第一个数比3小的4个数的排列共有3*3!=18个
1 0 2 //第一个数比1小的3个数的排列共有1*2!=2个
0 1 //第一个数比0小的2个数的排列共有0*1!=0个
所以，排列24103的编号为24+18+2+0=44。
另外献上一点温馨提示：UNSOLVABLE的布局是不存在的。
本题没有什么统一的公式，所以还是要老老实实地分情况讨论。
首先枚举项数n。项数的最小值为3。那么最大值呢？我们来看极端情况：各项和一定时，欲使项数尽可能大，应使每项尽可能小。那么数列就应该是1,2,3……因此，若设各项和为n，应有n*(n+1)/2=s。把n=sqrt(s*2)代入，左边大于右边，因此方程的正根小于sqrt(s*2)，故可用trunc(sqrt(s*2))作为n的最大值。
在项数确定了的情况下，我们可以求出数列每项的平均数m=s*2/n以及最大的公差d=trunc((m-1)/((n-1)/2))（公差最大时首项为1，且m与1的差是(n-1)/2个公差）。下面还要对n分奇偶讨论：
- 当n为奇数时，m就是数列的中间一项，故m必须为整数。这时，满足条件的数列个数为d。
- 当n为偶数时，m为数列中间两项的平均值，它可以是整数，也可以是整数点五的形式。
- 若m是整数，则公差必为偶数。此时满足条件的数列个数为d div 2。
- 若m是整数点五，则公差必为奇数。此时满足条件数列个数为(d+1) div 2。
此题的模型就是：给定一棵带权无根树，求把它的任一条边的权改为0后，树中的最长路的最小长度。
105的数据规模启示我们使用DP算法。为了DP方便，我们以1号顶点为根，把无根树转化为有根树。我对每个顶点x定义了如下函数（哇，好多啊@:(）：
- down1[x],down2[x],down3[x]：在以x为根的子树中，从x出发的最长路长度、次长路长度、第三长路长度。要求这三条路无公共边。
- below[x]：在以x为根的子树中的最长路长度。注意这条最长路不一定经过x。
- cbelow1[x],cbelow2[x]：x的孩子的below值中最大的一个和次大的一个。
- up[x]：在原树中去掉以x为根的子树（但保留x结点）后，从x出发的最长路长度。
- above[x]：在原树中去掉以x为根的子树及x与它父亲结点之间的边后，剩余部分的最长路长度。
DP总共进行两次。第一次自底向上进行，求出每个顶点的down1,down2,down3,below,cbelow1和cbelow2函数值；第二次自顶向下进行，求出每个顶点的up和above函数值，顺便算出答案。
在第一次DP中，当处理到顶点x时，可以按如下方法求出x的一些函数值：
- 对于x的每一个孩子y，求出x,y之间边的长度与down1[y]之和。这些和中最大的三个就是down1[x],down2[x]和down3[x]。
- 由于DP是自底向上进行的，x的所有孩子的below值中最大的两个就是cbelow1[x]和cbelow2[x]。
- below[x]为cbelow1[x]与down1[x]+down2[x]中的较大值。前者表示以x为根的子树中的最长路不经过x，后者表示经过x。
- 求up[y]。up[y]对应的路径的第一条边必然是(x,y)（长度记为L），然后有两种可能：
- 一种是继续往上走，这时up[y]=L+up[x]；
- 还有一种是往下走。如果往下走，则不可以沿着(x,y)再回来，于是若down1[x]=L+down1[y]，则up[y]应等于L+down2[x]，否则就等于L+down1[x]。
- 求above[y]。有两种情况：
- 一种情况是above[y]对应的路径不经过x。这时，它的长度可能是above[x]，也可能是cbelow1[x]（当cbelow1[x]<>below[y]时）或cbelow2[x]（当cbelow1[x]=below[y]时）。
- 另一种情况是above[y]对应的路径经过x。这时，可以把由x出发的最长的两条路连起来。候选的路径长度有：up[x],down1[x],down2[x]。当然，如果down1[x]或down2[x]中有一个等于L+down1[y]，那么它就没有资格了，而用down3[x]来替代。取候选路长中的最大值和次大值相加，即得above[y]。
- 求把(x,y)的权修改为0后整棵树中的最长路长度。有三种情况：
- 这条路经过(x,y)，这时路长为up[y]-L+down1[y]（注意up[y]-L不可以用up[x]代替，因为从x开始可以往下走）；
- 这条路在(x,y)上方，这时路长为above[y]；
- 这条路在(x,y)下方，这时路长为below[y]。
用线段树等树形结构，可以轻松地在1M内存以内解决问题，但它的时间复杂度为O(nlogd)，经测试，运行完所有数据需要将近2s。而实际上本题的内存限制是很松的。所以我们采用时空复杂度均为O(n)的队列解决本题。
开两个队列，一个叫做大队，一个叫做小队。如果一个深度满足它是从它所在位置到“当前段”末尾的最大值（最小值），那么它就属于大队（小队）。另外附加一条规则：如果大队或小队中有若干个深度相同，那么仅保留位置最靠前的那一个。容易看出，大队中深度是递减的，小队中的深度是递增的。
当“当前段”向右延伸一个位置的时候，就把这个新的深度加到两个队列末尾。这时，大队或小队的单调性可能被破坏。如果发生了这种情况，就把单调性被破坏的队列的倒数第二个元素删除，直至单调性重新成立为止。现在检查一下“当前段”是否满足要求。若大队队首元素（就是“当前段”中的最大深度）与“当前段”尾的深度之差超过限制，那么就不断地删除大队队首元素直至满足要求，同时把“当前段”首指针移到最后删除的那个深度所在位置的下一个位置。若小队队首元素与“当前段”尾的深度之差超过限制，则可用类似的办法进行处理。计算“当前段”的长度，与最优解比较。 DP，并用斜率优化法优化到O(n)。有关斜率优化法的原理请参看1171，在此只对本题进行数学推导。
逆推。用T[i]表示第i项工作以后的工作所需的总时间，F[i]表示第i项工作以后的工作的总处理成本因素。设从0时间开始做第i项工作以后的工作所需的总成本为cost[i]，则有状态转移方程：
cost[n]=0
cost[i]=min{(S+T[i]-T[j])*F[i]+cost[j]}(i<j<=n)
cost[0]为所求。
决策a比决策b优(a>b)的充要条件是：
(S+T[i]-T[a])*F[i]+cost[a]<(S+T[i]-T[b])*F[i]+cost[b]
<=> cost[a]-cost[b]<(T[a]-T[b])*F[i]
<=> (cost[a]-cost[b])/(T[a]-T[b])>F[i] (∵T[a]<T[b])
定义(cost[a]-cost[b])/(T[a]-T[b])为决策a、b间的斜率。维护一个决策队列，使它满足相邻元素间的斜率递增。当阶段为i时，先将决策i+1加入队尾，通过不断删除队列倒数第二个元素来维护它斜率的单调性。然后若队首两元素间的斜率小于F[i]，则说明队首决策现在不是、将来也不会是最优决策，故将其删除。当队首两元素间斜率大于等于F[i]时，队首元素就是当前的最优决策了。
下文中，把输入的图称作G，选定的生成树称作S，S中的边叫做树边，其余的边叫做非树边。
为什么要修改某些边的权值呢？这是因为，把一条非树边Y加入S后，S中会出现一个环，而这个环上的某一条树边X的权值(w[X])可能比Y的权值(w[Y])大。为了使S成为最小生成树，就必须减小X的权值，增大Y的权值，以使w[X]<=W[Y]。如果把w[X]的变化量（当然是减小量）记作d[X]，把w[Y]的变化量（当然是增加量）记作d[Y]，那么我们可以列出不等式：w[X]-d[X]<=w[Y]+d[Y]，即d[X]+d[Y]>=w[X]+w[Y]。
对于什么样的边对(X,Y)，需要列这样的不等式呢？这样的边需要满足的条件是：把Y加入S后，X在形成的环上。也就是说，X在S中Y的两个顶点间的路径上。对于任一条非树边Y，为了找出需要与它列不等式的所有树边X，我们需要把S看成一棵有根树，求出Y的两个端点u、v的最近公共祖先a。分别从u和v向上走到a，对路上满足w[X]>w[Y]的边X都列出一个不等式。这一步求最近公共祖先，由于数据规模很小，朴素算法就可以，当然也可以用效率更高的Tarjan算法，详见1068题。
现在我们得到了一个不等式组，我们需要求出使所有变化量之和最小的一组解。观察这组不等式，发现它们与求二分图最大权匹配（参见1148题）时顶标所满足的条件形式完全相同。而求出最大权匹配后，顶标之和确实达到了最小。因此我们建立一个二分图B，把每条树边看成一个X顶点，每条非树边看成一个Y点。如果一个X点与一个Y点之间列了不等式，那么B中它们之间的边权就是不等式的右边，即它们在G中的权值之差；如果没有列，那么B中它们之间的边权为0。如果X点数与Y点数不相等，则补齐，并让它与所有异种点之间的边权全为0。然后用KM算法求出B的最大权匹配，这时匹配边的总权值（也就是所有顶点的顶标和）就是最小代价。同时，我们还求出了一种修改权值的方案：每个点的顶标就是它对应的G中的边的权值的变化量。
其实，上面“补齐”的顶点若是X顶点（一般情况下非树边比树边多得多），则它们根本不必考虑，因为它们即使匹配上了，对权和的贡献也只是0。因此，匹配完原有的X顶点就可以停止了。
长郡中学的王俊提出了一种更简单的算法。他把求最大权匹配的问题转化为求最大匹配。他的思路是：题目中只要求求出最小代价，并没有要求求出修改方案，因此把边上的权值转移到点上。他建立了一个新的二分图B'，以所有的树边为X顶点，所有边（包括树边与非树边）为Y顶点。X顶点及边均无权值，Y顶点的权值为G中的边权。B'中的边是这样连的：B中每一条权不为0的边在B'中都有对应的边，另外每个代表树边的Y顶点都与代表同一树边的X顶点之间连一条边。这样做以后，B的完备匹配与B'的最大匹配之间就建立了一一对应的关系，且对应的两个匹配的权和之和为原图中所有树边的权值之和：
- 如果B的匹配中与某个X顶点相连的边权为0，那么B'中这个X顶点就匹配与自己代表同一树边的Y顶点。B中这条边的权值为0，B'中这条边的权值为这个顶点代表的树边本身的权值，其和为树边本身的权值。
- 如果B的匹配中与某个X顶点相连的边权不为0，那么B'中这个X顶点仍匹配B中X匹配的Y顶点。B中这条边的权值为w[X]-w[Y]，B'中这条边的权值为w[Y]，和仍为w[X]，即树边的权值。
（注：我的程序用的是王俊的算法，但X顶点和Y顶点被交换了过来。） 首先要突破一个思维定势：同一种商品如果要买多个，其实不必同时购买。这样我们就可以得出一种购买策略：先把需要买的东西各买一件，然后用最低的优惠价购买剩下的商品。后一步显然很简单，所以，题目转化为如何用最少的钱购买每种所需商品各一件。为叙述方便，下文中所说的“商品”都是指需要购买的商品，设这些商品共n种。
我们建立一个有向图G，图中有0至n共n+1个顶点。1至n号顶点各代表一种商品。从0向每个顶点引一条边，边权为这种商品的原价。另外，如果商品A可以优惠商品B，就从A到B引一条边，边权为优惠价。理想的情况是每种商品都以最低价购买，因此我们把通往1至n号每个顶点的权最小的边挑出来组成G的子图H。子图H具有这样一个性质：每个顶点的入度均为1。如果H可以进行拓扑排序，那么我们就可以根据这个拓扑序来以最低价购买每种商品了，总费用就是H中所有边的权和。
那么现在的问题就是H中有圈怎么办。如果H中有圈，那么圈上的物品是不可能均以最低价购买的，必然有一个最低价要被放弃。那么放弃哪一个呢？我们通过把缩圈来确定。缩圈的方法如下：
- 首先把圈上所有边的权值都累加到总费用中。
- 然后把起点A在圈外，终点B在圈内的边的权值减少一个值，这个值等于圈内指向B的权值。
- 最后把圈缩成一点C。现在C的入度变成了0，为使H的性质依然成立，我们需要找出G中指向C的权最小的边，并把这条边加入H中。
计算（i为左子树的结点数）。有了c数组，便很容易求出输入的序号表示的二叉树有几个结点，在有这么多结点的树中它的序号（从0开始）是多少。然后枚举左子树的结点数，又很容易求出它的左右子树各有几个结点，在相同结点数的子树中它们的序号各是多少。递归下去即可求出整个树了。 只存第一个人的牌可以节省内存（如果这也算技巧的话）。 每个杂务的完成时间等于它的所有先行杂务的完成时间的最大值加上它本身需要的时间。答案就是所有杂务完成时间的最大值。 首先运用一点技巧：把输入序列中相邻且配对的括号全都去掉，一直去到不能再去为止。这一步可以减小一般数据的规模。
然后进行DP。设f[i,j]为简化后字符串中第i个字符至第j个字符构成的子串需要添加的括号数。
- 当i>j时我们规定f[i,j]=0。
- 当i=j时显然有f[i,j]=1。
- 当i<j时，我们可以把这个字符串分为两段分别处理，因此f[i,j]为所有f[i,k]+f[k+1,j]中的最小值，这里i<=k<j。另外，如果第i个字符和第j个字符恰好配对，那么可以就让它们配对，即f[i,j]还可以等于f[i+1,j-1]。
另外注意：输入中可能有空串，因此程序结尾处的until seekeof一定要改为until eof，否则空串就会被忽略掉。
P.S.如果谁有O(n2)或者更优的算法，请告诉我。
先解释一下题意：工厂每天都有一定的产品需求量，这些产品可以当天生产，也可以调用以前的库存。第n天的产品如果当前生产，那么生产每吨产品的花费就是cost[n]；如果在第m天生产后存储到第n天，那么每吨产品的总花费就是cost[m]+s*(n-m)。
算法是很简单的。设第n天每吨产品的最小花费为best[n]，则best[n]=min{cost[i]+s*(n-i)}(1<=i<=n)。显然best的递推式为best[1]=cost[1],best[n]=min{cost[n],best[n-1]+s}(n>1)。
下面的叙述中省略取模运算。
用DP进行预处理。设f[n,k]为有k个逆序对的n个数的排列的数目。当k<0或k>n*(n-1)/2时，规定f[n,k]=0。计算非0的f[n,k]时，考察数n的位置。如果它是最后一个数，那么它与其它数构成了0个逆序对；如果它是倒数第二个数，则它构成了1个逆序对……如果它是第1个数，则它构成了n-1个逆序对。故有
。
为计算方便，我们设s[n,k]为f[n,0]至f[n,k]的累加和（k<0时s[n,k]=0），这样状态转移方程便化为s[n,k]=s[n-1,k]-s[n-1,k-n]。我们不必计算f数组而可以直接计算s数组，当提问f[n,k]时，输出s[n,k]-s[n,k-1]。
注意到当a+b=n*(n-1)/2时，f[n,a]=f[n,b]。因此，数组的第二维下标的最大值不必设为maxn*(maxn-1)/2，而只需设为此值的一半。这样会节省一半的空间和一定的时间。你可以看一下本题的状态，我是第一个用少于1M的内存解决问题的:)
设输入的数的二进制表示中最右边的一组连续的1有n个，则把这组1前面的那一个0改成1，这一组1本身改为0，并把整个数的最后n-1位改为1。
用二进制数表示每个错误存在与否的状态，以及每个补丁的使用条件和使用效果，可以用位运算简便地求出每个状态可以使用哪些补丁及使用后的新状态编号。于是问题转化为求一个有向图中某两点间最短路的问题。可采用用堆优化的Dijkstra算法，复杂度为O(nlogn+nm)（n为状态总数，m为补丁数）。
宽搜求最短路。由于每个任一时刻至少有一个杯子是空的或满的，所以状态可以用一个二元组表示：(0,x)表示第1个杯子空，(1,x)表示第1个杯子满，(2,x)表示第2个杯子空，(3,x)表示第2个杯子满；四种情况的x均表示另一个杯子中的水量。两杯都空的特殊状态用(0,0)或(2,0)表示均可，两杯都满的情况类似。
把体重超过独木舟最大载重量一半的人叫做胖子，其余的人叫做瘦子。首先把所有的人按体重排序（当然用桶排，因为人可能很多，而体重的可能值却很少）。按体重递减的顺序处理每一个胖子，如果有瘦子可以跟他同乘一条船，则把他们安排到同一条船上，否则只好让胖子独坐一条船了。当胖子处理完后，剩下的瘦子就可以一对一对地上船了。
首先，同一队中的人必须满足一个条件：吃饭越慢的越排在前面。简单证明一下：假设两个人打饭的时间分别为a、b，吃饭的时间分别为c、d，其中c<d。假设第一个人排在前面，则第一个人吃完饭的时刻为a+c，第二个人吃完饭的时刻为a+b+d，这两个时刻的较大值为a+b+d（因为c<d）。如果把他们的位置对换，则两个时刻分别为b+d和b+a+c。显然这两个都小于a+b+d。因此我们先把所有人按吃饭时间降序排列。
然后使用DP算法。用buy[i]和eat[i]分别表示第i个人打饭和吃饭所需时间，sum[i]表示前i个人打饭所需的时间之和。设time[i,j]表示前i个人排队，第一队的总打饭时间为j时，最后一个人吃完饭的最早时刻。如果(i,j)是一种不可能的状态，则time值为无穷大。初始时只有time[0,0]为0，其余皆为无穷大。求time[i,j]时，对第i个人所排的队分情况讨论：
- 当j>=buy[i]且time[i-1,j-buy[i]]不等于无穷大时，第i个人可以排第一队。这时最后一个吃完饭的人可能就是第i个人，也可能不是。如果是，则他吃完饭的时刻就是j+eat[i]；如果不是，则其余i-1个人吃完饭的时刻就是time[i-1,j-buy[i]]（很巧妙的）。这两个时刻的较大值就是所有i个人吃完饭的时刻，记作t1（如果第i个人不可以排第一队，则t1为无穷大）。
- 当time[i-1,j]不等于无穷大时，第i个人可以排第二队。如果最后一个吃完饭的人就是第i个人，则他吃完饭的时刻就是sum[i]-j+eat[i]，否则其余i-1个人吃完饭的时刻就是time[i-1,j]。这两个时间的较大值就是所有i个人吃完饭的时刻，记作t2（如果第i个人不可以排第二队，则t2为无穷大）。
| 
| 如图，把四面体放到坐标系中，使B点与原点重合，C点落在x轴正半轴上，D点位于xOy平面且y坐标为正，A点z坐标为正。B、C坐标很容易写出。利用两点间距离公式及BD、CD的长度，可以解出D点坐标。再利用两点间距离公式及AB、AC、AD的长度，可以解出A点坐标。四面体的体积就是dnz/6。 |
因为2*2=4，所以2和4的效果是一样的。那么问题就是尽量多分2还是多分3的问题。由于2^3<3^2，所以尽量多分3是正确的选择。如果人数是3的倍数，那么就全分成3人组；如果人数除以3余2，那么就把剩下2人分为一组；如果余1，那么就拿出4人分成一组。