电子科大第五届程序设计竞赛决赛题目浅析刘歆决赛题目和初赛不同，我以提点为主。各位同学不必强求看懂每一个题的分析、把每个题做出。有些题是要你的内力到了一定程度以后才能真正理解的。看书、做题、提高自己的实力才是关键。等你的实力提升以后，再来看这些题，你会发现很多题都是可以迎刃而解的。题目可以在HYPERLINK"http://acm.tju.edu.cn/toj/contest/contest68.html"http://acm.tju.edu.cn/toj/contest/contest68.html看，你也可以在天大的OJ上提交。AASimpleProblem(Author：郭志彪)难度：***满足f(a,k)=0等价于a具有N的全部素因子。因为平方可使素因子数增多并最后>=N的相应素因子数，而平方本身不会产生新的素因子。求模可以最后来做，因为(amodN)*bmodN=a*bmodN。设N的全部素因子乘积（每个只取一次）为P，那么a一定是P的倍数。答案是N/P+1。BBus(Author：文成明)难度：**动态规划f[k,0]=max(f[k+1,0],f[k+2,1])+Akf[k,1]=max(f[k+1,1],f[k+2,0])+Bkf[k,0](或f[k,1])分别表示第k天开始，这一天选择Ａ（或Ｂ）的最大值。最后取max(f[0,0],f[0,1])。CTheQueen’NewNecklaces(Author：朱泓丞)难度：****用到Burnside定理。Burnside定理说的是，不同的项链数等于置换群中每个置换的不动点（在置换下不变的方案）个数的和。这里置换就是一种排列，把一种着色方案映射到另一种，这两种方案是相同的。置换群可以简单理解为这些置换的集合（不过置换的连接产生的新置换也要包含在这个集合中）。根据题意，旋转产生的方案是相同的，用置换来表达，就是所有的排列(aiai+1…a1…ai-1)。一共有n个这样的置换，n是题目中所有颜色数的总和。把这些排列都写成循环节的形式，它们的一个特点是所有的循环节大小相等。假设某个排列的循环节大小是m，方案在该排列下不变当且仅当每个循环节的元素颜色相同。如果某种颜色的个数Ci不是循环节大小m的倍数，那显然是不可能实现的，反之，一定能实现。依次考虑每种颜色Ci，假如Ci/m=k，那么有C(a,k)种方法选择出k个循环节，给他们染上颜色Ci，其中a是当前剩下循环节个数，然后a=a-k继续下一种颜色的计算。把所有排列(aiai+1…a1…ai-1)这样处理一遍即可。由于答案很大，必须使用高精度，即把十进制整数每一位存在数组中，自己实现加减乘除运算。朱泓丞的标程和我的标程都是使用４位十进制整数放到数组中的一个Entry。其中高精度部分不必深究（尤其第一个程序，前面贴的是高精度模版），搞清楚本题的计数原理才是重点。你可以研究标程中的高精度代码，但请不要把它用作自己的高精度模版。DErdosNumber(Author：刘歆)难度：**直接BFS。以Erdos为起始点扩展一棵宽度优先树，两个节点有边当且仅当这两个作者合作。每个节点在树中到Erdos的距离就是它的Erdos数。注意题目有个陷阱：输入的合作关系里边可能没有Erdos这个人，但是查询中可能会有Erdos，这时应当输出0而不是infinity。很多队伍都栽到了这个陷阱中，有些队最后改过来了，有些队没有。我自己写标程的时候一开始都犯了这个错.EErdos’Travel(Author：刘歆)难度：****期望可以相加，即使它们不独立。只需要树中一条路径的平均长度乘以R。树中一条路径的平均长度等于树中所有路径的长度和再除以n*(n-1)。这只需要求出从每个节点出发的路径长度和再把所有节点加起来。而这可以树形DP完成，先计算出有向树中儿子方向的路径长度和，再加上父亲方向的。FFareySequence(Author：朱泓丞)难度：*（天大同步赛难度是***）校赛n<=500，直接枚举+排序。如果n<=3000，暴力是不行的。可以对Stern-Brocot树作一次DFS，复杂度和输出复杂度相同。这里有我的一篇帖子HYPERLINK"http://blog.tianya.cn/blogger/post_show.asp?idWriter=0&Key=0&BlogID=397009&PostID=5576076"http://blog.tianya.cn/blogger/post_show.asp?idWriter=0&Key=0&BlogID=397009&PostID=5576076讲到了Stern-Brocot树。GPlayground(