SGU 解题表格.doc

IOI2004中国国家集训队第一轮训练泛做报告表格SGUhttp:/acm.sgu.ru/ 请大家尽量仔细的填写下列表格。基本要求是自己越推荐的题目应该写得越多。如果觉得没什么意思就只写算法大意（一两行即可）和时空性能。推荐的题目不用太多，否则就没有比较意义了。加红的是我比较推荐的题目，可以先看，不过由于我自己看得并不是很仔细，想得也不深入，可能会有错误的推荐或者漏掉好题，只是起到一个参考作用。 请注意：如果题目没什么新意一定不要在推荐程度里加五星。凡是有加五星的都代表有一定的闪光点。需要剪切的，这里提供一堆：）编号题目名称题目和简要算法描述时空性能推荐程度备注106The equation先求出方程ax+by=c的任意一组解x1,y1然后所有解可以表示为x+I*b/(a,b),y-I*b/(a,b)，求出I的范围即可知共有多少组解。需要判断一些特殊情况，比如a=0，b=0等等。O(logn)O(1)107987654321 problem首先，如果一个数平方的末n位数字只与该数字的本身的末n位数字有关，则本题当n9时，只要算出n=9时的答案，再不断地乘以10即可。Np2-p3-.pm如果在剩下的点中，有一点可以连向p1，则找到了一条长度为m+1的链。如果pm可以连向剩下点中的某一点，则同样到找了一条长度为m+1的链。如果p1，pm均无法找到可以连的点，根据抽屉原理，一定存在一个q(1=qm)，使得pm可以连向pq且p1可以连向pm+1，那么，原来的链就变成一个环，只要在环上任意引一条边连向剩下点的边即可得到一个长度为m+1的链。O(N2)O(N2)125Shtirlits我们仅考虑n=3的情况有以下几种方法（1） 可以枚举相邻两点的大小关系，得到一种可行的大小关系后，再进行拓扑排序，将排序后的点依次标权即可。（2） 可以枚举以下的几个点1234这时，角落上的以及中间的点取值基本可以确定。不过取值存在着相等和小于两种情况，因此，还需要枚举一下。对于n大一点的情况，暂时还没想到有效算法。O(1)O(1)对于n比较大的情况，目前没有多项式算法126Boxes设两个盒子各有a个球和b个球，则经过一次移动后，第一个盒子有(2*a)%(a+b)个球，第二个盒子有(2*b)%(a+b)个球。那么，问题实际上为2k*a=0 (mod (a+b)，则如果(a+b)/gcd(a+b,a)是2个整数倍问题有解，否则问题有解。并且可以证明解不超过log(a+b)+1O(log(a+b)O(1)根据推出的结论来看，直接模拟也是可行的。130Circle类似卡特兰数，用递推求解。也可以直接用公式。O(N)O(N)132Another Chocolate Maniac类似于炮兵阵地的动态规划 记录两行的全部状态即可。考虑的情况很多134Centroid求图的中心点。首先，从叶子结点开始依次向上处理，计算出以每个结点为根的子树的大小。然后，来枚举即可，因为可以用平摊复杂度O(1)的时间求出删除每个结点后各个连通分量的结点数。O(N)O(N)137Funny Strings构造开始时，0-n-1每个位置上的数均为k/n另位置0上的数-1，位置n-1上的数+1接着，我们要求一个长度为k%n的链。因为gcd(k%n,n)=1，所以只需求一个数i，满足(k%n)*i%n=n-1 即可（肯定存在）之后，将位置j*i%n上的数全部改为+1即可。可以证明，求出来的数列符合条件。O(N)O(N)138Games of Chess贪心每次找到度最大的点，再不断地和度最小的点比赛，直到其不是度最大的点为止。再让其输给现在度最大点。如此下去。需要判断一下边界情况。O(N2)O(N2)140Integer Sequences先考虑a1,a2，如果gcd(a1,a2)=1,则显然a1,a2可以组成任何数，否则，将给a1，a2配上系数并成一个数,使得k1a1+k2a2=gcd(a1,a2)，再处理gcd(a1,a2),a3，如此下去.O(NlogN)O(N)141Jumping Joe数论题142Keyword因为总长度 nexti这一段是已经染过色了。从最后一个染色的矩形开始，依次染色，分别处理每一行，处理过(j，i)后，可以直接跳到(j，nexti)，中间的部分不再处理，然后，修改next数组。这样做的复杂度是O(N2*log*n)，因为后者一般不超过5，所以可以看成常数。O(Nlogn2)O(Nlogn2)178Golden Chain枚举+计算。179Brackets light构造从右往左扫描，找到一个右括号，满足该括号左边的左括号与右括号之差不超过其右边的括号总数。将该右括号改为坐括号，再把后面的括号改为()的形式。O(N)O(N)182Open the brackets枚举+构造。将所有的210种情况的表达式的值都算出来，再构造一个表达式作为结果输出。比如(a,b,c)=(F,T,F)表达式为真，则!a&b&!c=1，所以可以把结果为真的变量取值写成这种形式再用|连起来作为等价式。例如只有当(a,b,c)=(T,F,T) 或 (T,T,F) 或 (T,T,T)时a&(b|c)的值才为真。所以a&(b|c)的等价式可以为a&!b&c|a&b&!c|a&b&c。183Painting the balls动态规划。O(NM)O(N)185Two shortest费用流。每条路的流量上界为1，然后，求一个流量为2的最小费用流即可。如果，流的总费用不是最短路径的2杯，则问题无解，否则，就是答案。最短路径为流量为1时的总代价。O(N4)O(N2)187Twist and whirl分成一段段后处理189Perl-like substring字符串处理190Dominoes匹配。首先对棋盘进行黑白染色，如果黑点ai和白点bj在棋盘上想邻，就在二部图ai，bj间连一条有向边，然后，求二部图的最大匹配，如果是一个完备匹配，就找到了一个覆盖。O(N3)O(N2)191Exhibition模拟192RGB离散化后统计O(N2logN)O(N2)193Chinese Girls Amusement实际上就是求一个k，满足k=wij，我们要求的就是满足这些不等式的ai，bi，且sigma ai+sigma bi最小。这个问题可以用最佳匹配来解决。构造一个二部图，左边的点代表a，右边的点代表b，如果ai+bj=wij，则在ai，bj间连一条权值为wij的无向边，可以证明，该二部图的最佳匹配值就是所求的最小值。O(N3)O(N2)207Robbers先贪心，再调整O(N)O(N)208Toral TicketsPolya定理数学方法210Beloved sons这题可以用最佳匹配来做，不过这样就没有充分利用题目的性质。因为从一个点连出去的边权值都是一样的。所以，我们可以先根据每点的权值排序，再从权值大的点开始扩展，用km算法求图的最大匹配即可。可以证明这样是正确的。O(N3)O(N2)改用最大匹配，时空复杂度没有降低，但实际效果好了很多211Strange Counter维护两个2之间最少有一个0当插入位置上的数为2，则将该位置上的数改为1，然后将其下一位+1当插入位置上的数为1，则找到该位置之后出现的第一个2的位置q。这时分三种情况讨论（1） 如果后面没有2，就将该位置改为0，该位置的下一个位置+1。（2） 如果找到的2恰好与该位置相邻，将该位置改为2，将下个位置改为0，再将下下个位置+1。（3） 其他情况下，将该位置改为0，将下个位置+1，再将位置q改为0，将位置q+1改为2。当插入位置上的数为1，同样找到该位置之后出现的第一个2的位置q。分两种情况讨论：（1）如果后面不存在2，直接将该位置加1（2）否则将该位置加1，位置q改为0，位置q+1 加1不错的题目212Data Transmission网络流。这题与一般的流相比有两个比较重要的性质1 图是分层的2 找到一个流后不需要加倒边则可以利用这两个性质，将增广流的复杂度降到O(L)这样总的复杂度是O(KL)，仍然很高。可以用贪心法求一遍初流，这样实际效果就很好了。213Strong Defence最短路径。设最短路径长度为T，则如果染色数T，那么必定存在一种颜色，不属于最短路径，把该颜色删去，就不能把图断开，不满足题目条件，所以ans=T。接着，构造出ans=T的方案，显然，这就是最优方案。构造方法也比较简单，对于任意一条边(i,j)如果mindis(i)=mindis(j)+1，则(i,j)的颜色为mindis(i,j)，这里，mindis(p)代表第1点到第n点的最短路径。O(N2)O(N2)214Weird Dissimilarity动态规划。记f(i,j)为已经匹配到了a串字符i与b串字符j的最优值。求f(I,j)时分三种情况讨论.1 直接用ai配bj，则w=f(i-1,j-1)+dis(ai,bj)2 i与其他字符匹配，则w=f(i-1,j)+min(ai)3 j与其他字符匹配，则w=f(i,j-1)+min(aj)这里，min(c)表示min(dis(c,c1),c1属于字符集。216Royal Federation从叶子结点开始，一层层往上处理。如果当前树上结点总数不超过3b，就直接输出。否则，对每个正在处理的结点，分三种情况处理：（1） 该结点以及其子树的结点总数小于b，则该结点不做任何处理。（2） 该结点以及其子树的结点总数在b与2b之间，则将这些结点作为一个省输出，然后将这些点从树上删除。（3） 该结点以及其子树的结点总数超过2b，这时需要做进一步处理。首先， 选出它的部分子树，满足这些子树的总结点数在b-2b之间（选择可以用最简单的贪心，按顺序选，直到满足条件为止，因为所有子树的结点数都不超过b，所以这种选法肯定能找到解的）然后，将这些子树当作一个省，而把正在处理的这个结点作为capital。最后将这些子树从树中删去。再回到开始，分三种情况处理该结点。O(N)O(N)217Two Cylinders积分。F(x)=sqrt(r12-x2)*sqrt(r22-x2)区间0,min(sqrt(r1),sqrt(r2)的平均值。精度很高的枚举也行218Unstable Systems最大最小匹配。先构造二分图，然后二分答案k，根据k构造新图。如果边(ai,bj)的权值小于等于k，则在新图中保留边（ai,bj）,然后对新图进行最大匹配，如果是完全匹配，则找到一组解。O(N3logQ)O(N2)219Syncrograph首先，先求出图的所有极大强连通分量，把每个强连通分量缩成一个点。可以证明，处于同一个强连通分量中的点，要么同为alive，要么都不是。如果强连通分量a能通过有向边连向强连通分量b，那么就在a b两点间连一条有向边，然后，对新图拓扑排序。依次处理排序后的每个强连通分量。在处理某个强连通分量时，首先考虑其它强连通分量对其的影响。如果有一个强连通分量b可以连向该分量（因为已经进行了拓扑排序，所以b肯定在之前处理过了），若b是not alive，则显然a是 not alive；如果连向该分量的其它分量均是alive，则需单独考虑该分量。设一个队列queue,如果该连通分量不存在某点可以fire，则该分量为not alive，否则把可以fire的点加如队列。然后对队列中的每个点依次fire一次，并将其从队列中删去，每次fire之后，可能使某些原先不能fire点可以fire，把这些点加入队列，直到队列为空停止。如果所有的点均进出队列一次，则该连通分量为alive，否则为not ailve。O(N+M)O(N+M)220225(little chess piece series)220，221 bishops首先，黑格和白格互相不影响，所以单独考虑。5425435435135上面是一个5*5的棋盘。数字表示阶段。也就是说，从两端往中间推。设f(i,j)为阶段i已经放了j个bishops的方案总数，则