NOIP2009普及组解题报告 V1.0.doc

NOIP2009普及组复赛试题解题报告 孙禹达 多项式输出(poly) 问题描述： 给定n和n+1个整数，求对应表达式。 解题思路： 送分的水题，主要注意细节处理问题，其中有以下几点细节： 1.系数为1不输出系数，为-1要输出负号。 2.系数为0不输出。 3.一次项不输出^1。 4.开头若为负数要输出负号。 处理好这些细节，AC应该很容易。 建议时间： 15-25 min。 一般第一个题可能都很快写完，但是作为水题是不可以丢分的，所以花大约10分钟写完后再花10分钟调试，如果耽误时间过多不利于写之后的难题。 2、分数线划定（score） 问题描述： 给出录取人数n及所有面试者成绩和考号。求出分数线和实际录取人数，以成绩从大到小排序，若成绩相同则考号从小到大的规律输出录取人考号与成绩。 解题思路： 主要考察排序，看数据范围5=n=5000，对应任何一种排序都可以轻松AC，但是对于难度系数不高的题还是要注意细节问题，首先是分数线问题，先对成绩进行排序（这个时候也可以顺便对考号排序），将m*1.5得到的结果对应向下取整，那么这个人的成绩就是分数线，但是这个分数线内可能有重分的现象出现，所以根据题的要求要把这些人全部算上得出实际人数，然后按照顺序输出即可，如果前面没有对考号进行排序则应再将考号排序。 建议时间： 15-25min。 没有任何考察难点，所以在保证不失分的情况下尽量节省时间，将该拿的分拿到即可，此题不用纠结于排序的方式，挑最熟练的写，只要可以得分写的猥琐点也没有事（我就是冒泡，写的非常简单但是节省时间）。 3、细胞分裂（cell） 问题描述： 给出m1，m2以及若干个个si，求si^a mod m1^m2=0中a的最小值。若无解，输出-1。 解题思路： 首先一看就能想出暴力的方法，就是枚举。这样的得分是50分，如果暂时想不出思路可以先把暴力写完，能拿的分先拿上。 然后观察题，发现m1^m2的值非常大，无法对其进行计算，所以要通过一些数学手段来简化这个式子。对于m1^m2，先不看m2，将m1进行因式分解，采用素数表的方法即可，如果写求素数的函数要注意条件，比如写for(int i=2;i=sqrt(n);i++)这种写法就不算太好，对于sqrt函数的调用次数很多，不如写成for(int i=2;i*i=n;i++)相比前者会好一些。然后会得到一些质数元素和这些元素对应的幂数，而m1^m2这个数如果也分解成这种形式就是把每个元素的幂数全部乘以m2，这样会得到m1^m2因式分解的结果，如果对于si可以整除m1^m2的话，首先si因式分解的元素种类要和m1因式分解的相同，如果不相同的话就直接跳过计算下一个数。如果相同的话，要计算最大分裂的次数（即为分裂时间），因为要满足si能够整除m1^m2，所以要保证si分解后的每一个元素的幂数都大于等于m1^m2分解的同种元素的幂数，求得所有的a之中取最大的一个就是这种细胞最快开始试验的时间，再将所有结果作比较，将其中最小的输出即为答案。如果没有符合条件的就输出-1。 建议时间： 40-50min。 对于这种题先把暴力那些肯定能得分的程序写出来，然后进行分析，因为一般最后一题较难，所以这题不用节省时间，要在保证得分的情况下尽量多得，要是对最后一题实在没思路把所有精力放到这题上换来AC也是可行的。 即对应m1种元素个数/si中元素个数后向上取整。最后更新答案即可。 4、道路游戏（game） 问题描述： 有一条环形路，路上有n个点，第i个点和第i+1个点有边相连（第n个点与第1个点有边相连）。每个点都可以花费不同的代价生产一个机器人，且机器人可以顺时针走不多于p步（每走一步消耗一单位时间），并捡起此时路上的金币。最多只能有一个机器人存在于路上。不同的时间每条路上金币数不同。求最后能够得到的最大金币数。（即捡起的金币数减去生产机器人需要的金币数）。 解题思路： 这个题相比于之前的题就难了很多，很明显的可以看出来是一道DP题，但是注意数据范围2=n=1000，1=m=1000所以只有设计出O（mn）或者更优的算法才可以通过。 用f[i,j]存储i时间在j点上得到的最大金币数。oin[i,j]为i时间j号路得金币数。ost[k]代表在k点购买机器人花费的金币数。其中1=k=n。step[i,j]代表f[i,j]的状态时机器人已经走的步数。past[j]为j之前的点。即past[i]=i-1(2=i=n) past[1]=n。for(j=1;j=n;j++) { step[1][j]=1; f[1][j]=pastmax-cost[past[j]]+coin[1][past[j]]; if(f[1][j]now