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

NOIP2009普及组复赛试题解题报告孙禹达1、多项式输出(poly)问题描述：给定n和n+1个整数，求对应表达式。解题思路：送分的水题，主要注意细节处理问题，其中有以下几点细节：1.系数为1不输出系数，为-1要输出负号。2.系数为0不输出。3.一次项不输出^1。4.开头若为负数要输出负号。处理好这些细节，AC应该很容易。建议时间：15-25min。一般第一个题可能都很快写完，但是作为水题是不可以丢分的，所以花大约10分钟写完后再花10分钟调试，如果耽误时间过多不利于写之后的难题。2、分数线划定（score）问题描述：给出录取人数n及所有面试者成绩和考号。求出分数线和实际录取人数，以成绩从大到小排序，若成绩相同则考号从小到大的规律输出录取人考号与成绩。解题思路：主要考察排序，看数据范围5=n=5000，对应任何一种排序都可以轻松AC，但是对于难度系数不高的题还是要注意细节问题，首先是分数线问题，先对成绩进行排序（这个时候也可以顺便对考号排序），将m*1.5得到的结果对应向下取整，那么这个人的成绩就是分数线，但是这个分数线内可能有重分的现象出现，所以根据题的要求要把这些人全部算上得出实际人数，然后按照顺序输出即可，如果前面没有对考号进行排序则应再将考号排序。建议时间：15-25min。没有任何考察难点，所以在保证不失分的情况下尽量节省时间，将该拿的分拿到即可，此题不用纠结于排序的方式，挑最熟练的写，只要可以得分写的猥琐点也没有事（我就是冒泡，写的非常简单但是节省时间）。3、细胞分裂（cell）问题描述：给出m1，m2以及若干个个si，求si^amodm1^m2=0中a的最小值。若无解，输出-1。解题思路：首先一看就能想出暴力的方法，就是枚举。这样的得分是50分，如果暂时想不出思路可以先把暴力写完，能拿的分先拿上。然后观察题，发现m1^m2的值非常大，无法对其进行计算，所以要通过一些数学手段来简化这个式子。对于m1^m2，先不看m2，将m1进行因式分解，采用素数表的方法即可，如果写求素数的函数要注意条件，比如写for(inti=2;i=sqrt(n);i++)这种写法就不算太好，对于sqrt函数的调用次数很多，不如写成for(inti=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点上得到的最大金币数。coin[i,j]为i时间j号路得金币数。cost[k]代表在k点购买机器人花费的金币数。其中1=k=n。step[i,j]代表f[i,j]的状态时机器人已经走的步数。past[j]为j之前的点。即past[i]=i-1(2=i=n)past[1]=n。对于每个阶段，它的上一个阶段的最优值是确定的，所以只需要计算出本阶段的最优值作为下一阶段的上一阶段的最优值（程序中的nowmax和pastmax）。首先处理出时间为1时候的情况：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]nowmax)nowmax=f[1][j];}pastmax=nowmax;然后DP，将时间放在外层，每次初始化本阶段最优解为一个很小的负数（因为可能会有负数，所以不能为0），然后里层是道路，对应第j条路有两种情况，这个机器人可以走下去或者已经走到极限p了，要报废了（step[i-1][past[j]]==p时）。如果要报废了的话就必须立刻有一个新的机器人出现（长江后浪推前浪，把前一个机器人报废在沙滩上--残忍）。而这个时候机器人所走的步数就会重新初始化为1（step[i][j]=1），而且要把购买机器人的代价与在购买机器人的j位置在i时间的金币收了（f[i][j]=pastmax-cost[past[j]]+coin[i][past[j]];），然后更新最优解。如果这个机器人走下去又会遇到两种情况，第一种是走了这个点不合适（pastmax-cost[past[j]]f[i-1][past[j]]），因为本身f这个数组就是储存最优解的，所以出现这种状况只能是买机器人之后，所以重置机器人状态（新的开始，走的步数变成1）+买机器人的代价+拿金币（step[i][j]=1;f[i][j]=pastmax-cost[past[j]]+coin[i][past[j]];）。而其他情况就是将走的步数+1（step[i][j]=step[i-1][past[j]]+1）并且把金币捡起来更新最优值。(f[i][j]=f[i-1][past[j]]+coin[i][past[j]];）这样DP下去就可以得到最终结果。用step数组代替了原来的走的步数的状态，从三种状态变成的两种状态，但是相应的也多了一个递推式，这样就不会有超时的问题了。建议时间：？？？min基本想完全AC这道题，就要在前面节省出很多时间，所以这个题的时间就是答完前三道题并且保证对的情况下剩下的时间，不用对这个题太执着，因为本身题的难度不低，所以如果有大量空闲时间的话就做，要是力不从心果断放弃。总结：前面说得那么细，就不多说了，呵呵~~样例程序（C++）：1.多项式输出（poly）#includeiostream#includefstream#includecstring#includecstdiousingnamespacestd;intabs(inta){returna0?a:-a;}intmain(){freopen(poly.in,r,stdin);freopen(poly.out,w,stdout);intc;cinc;inta[c+1];for(inti=0;i=c;i++){cina[i];}if(abs(a[0])==1){if(a[0]==1){coutx^c;}if(a[0]==-1){cout-x^c;}}else{couta[0]x^c;}for(inti=c-1;i=0;i--){if(a[c-i]==0){continue;}if(i==1){if(abs(a[c-i])==1){if(a[c-i]0){cout'+''x';}if(a[c-i]0){cout'-''x';}}elseif(a[c-i]0){cout'+'a[c-i]'x';}if(a[c-i]0){couta[c-i]'x';}}elseif(i==0){if(a[c-i]0){cout'+'a[c-i];}if(a[c-i]0){couta[c-i];}}elseif(abs(a[c-i])==1){if(a[c-i]0){cout'+'x^i;}if(a[c-i]0){cout'-'x^i;}}else{if(a[c-i]0){cout'+'a[c-i]x^i;}if(a[c-i]0){couta[c-i]x^i;}}}coutendl;}2、分数线划定（score）#includeiostream#includecstring#includecstdio#includecstdlibusingnamespacestd;structpeople{intnum;intscore;people(){num=0;score=0;}};intcmp(constvoid*a,constvoid*b){people*q=(people*)a;people*p=(people*)b;if(q-score!=p-score)returnp-score-q-score;if(q-score==p-score){if(q-num=p-num)returnq-num-p-num;if(p-numq-num)returnq-num-p-num;}}intmain(){freopen(score.in,r,stdin);freopen(score.out,w,stdout);intn,m,t=0,tt=0;cinnm;peoplea[5001];for(inti=0;in;i++){cina[i].numa[i].score;}qsort(a,n,sizeof(a[0]),cmp);tt=(int)m*1.5-1;for(inti=0;in;i++){if(a[i].scorea[tt].score){t=i;break;}}couta[tt].score''tendl;for(inti=0;it;i++){couta[i].num''a[i].scoreendl;}}3、细胞分裂（cell）#includeiostream#includecstdio#includecstringusingnamespacestd;#defineMAXN100000boolonce[MAXN];intprime[10000],k=0;voidget(){inti,j;memset(once,1,sizeof(once));for(i=2;iMAXN;i++){if(once[i]){prime[k++]=i;j=i;while(j+iMAXN){j+=i;once[j]=0;}}}once[0]=once[1]=0;return;}intmain(){intn,m1,m2,nfac,i,s,si,ans,maxs,temp;intfac[100],facexp[100];freopen(cell.in,r,stdin);freopen(cell.out,w,stdout);get();scanf(%d%d%d,&n,&m1,&m2);nfac=0;for(i=0;prime[i]*prime[i]=m1;i++)if(m1%prime[i]==0){s=0;while(m1%prime[i]==0){s++;m1/=prime[i];}fac[nfac]=prime[i];facexp[nfac]=s;nfac++;}if(m11){fac[nfac]=m1;fa