NOIp2009普及组解题报告.doc

NOIP2009普及组复赛试题解题报告许建峰1、多项式输出本题只是一个基本知识点考核的一个题目，主要是看参赛选手的细心程度，无算法体现。先定义一个系数的数组a105。首先这一题解题的大的方向需要考虑两点，多项式系数ai大于零和小于零两种情况，因为系数为零时不输出该项，而大于零的要求输出含有“+”号，小于零的直接输出。然后在分项进行处理：第一项要单独处理，在处理第一项时有3种情况如下：If (ai=1)Else if (ai=-1)Else if (ai!=0)接着对第二项到第n-1项进行处理这里在循环里面处理又有（ai0 & ai!=1） （ai=1） （ai0和an0两种情况分别讨论最终即可解出本题。参考程序如下：#includestdio.hmain() FILE *fin,*fout; int i,a105,n; fin=fopen(poly.in,r); fout=fopen(poly.out,w); fscanf(fin,%d,&n); for(i=0;i=n;i+) fscanf(fin,%d,&ai); if(a0=1) fprintf(fout,x%d,n); else if(a0=-1) fprintf(fout,-x%d,n); else if (a0!=0) fprintf(fout,%dx%d,a0,n); for(i=1;i0 & ai!=1) fprintf(fout,+%dx%d,ai,n-i); if (ai=1) fprintf(fout,+x%d,n-i); if(ai0 & an-1!=1) fprintf(fout,+%dx,an-1); if(an-1=1) fprintf(fout,+x); if(an-10) fprintf(fout,+%d,an); if(an0) fprintf(fout,%d,an); fclose(fin); fclose(fout);2、分数线划定本题就是一个基本的简单排序题目，由于数据范围比较小，不需要用到快排或者其他排序，只要会一种基本的排序即可，比如用最熟悉的冒泡就可以完成该题的所有测试数据。首先定义两个数组一个a5005用来存放选手的成绩，一个数组num5005用来存放选手的参赛号。然后按选手成绩从高到低排序，如果成绩相同按小号在前，大号在后的顺序存放，然后输出1.5倍的m即可，这里要注意1.5*m要向下取整的方法。这时我们可以考虑使用强制类型转化int(1.5*m)的使用。然后计算出aint(1.5*m)的成绩，统计出所有大于等于该成绩的选手的人数。最后用循环输出所有成绩在分数线以上的选手就可以了。参考程序如下：#includestdio.hmain() FILE *fin,*fout; int n,m,a5005,num5005,i,j,t,k,s=0; fin=fopen(score.in,r); fout=fopen(score.out,w); fscanf(fin,%d%d,&n,&m); k=int(1.5*m); for(i=0;in;i+) fscanf(fin,%d%d,&numi,&ai); for(i=0;in-1;i+) for (j=0;jn-1-i;j+) if (ajnumj+1) t=aj; aj=aj+1; aj+1=t; t=numj; numj=numj+1; numj+1=t; for(i=0;i=ak-1) s+; fprintf(fout,%d %dn,ak-1,s); for(i=0;is;i+) fprintf(fout,%d %dn,numi,ai); fclose(fin); fclose(fout);细胞分裂问题转述：给出m1，m2以及若干个个si，求sia mod m1m2=0中a的最小值。若无解，输出-1。分析：数学题。由于m1=30000,m2=10000，根本无法直接计算，所以需要通过数学分析得出答案。如果一个数能够整除另一个数，那么这个数因数分解后一定有另一个数所有的元素，且每个元素个数均大于等于另一个数相同元素的个数。因此我们可以先对m1进行因数分解，并将对应元素的个数乘以m2。之后读入每个数，判断该数因数分解后是否有m1中所有的元素。如果有的话，则计算该细胞最大的分裂次数，即对应m1种元素个数/si中元素个数后向上取整。最后更新答案即可。注意因数分解中1比较特殊，所以要单独判断一下。程序：type arr=array1.30000,1.2 of longint;var ans,g,i,k,n,m1,m2,total:longint; a:arr;procedure factorization(k:longint;var a:arr;var link:longint);var i:longint;begini:=1;link:=0;repeat inc(i); if k mod i=0 then begin inc(link); alink,1:=i; alink,2:=0; while k mod i=0 do begin inc(alink,2); k:=k div i; end; end;until k=1;end;procedure main;var i,z,max:longint;beginmax:=-1;read(k);for i:=1 to total do begin if k mod ai,10 then exit; z:=0; while k mod ai,1=0 do begin inc(z); k:=k div ai,1; end; if (ai,2+z-1) div zmax then max:=(ai,2+z-1) div z; end;if maxans then ans:=max;end;beginassign(input,cell.in);reset(input);assign(output,cell.out);rewrite(output);ans:=maxlongint;readln(n);readln(m1,m2);if m1=1 then begin writeln(0);close(input);close(output);halt;end;factorization(m1,a,total);for i:=1 to total do ai,2:=ai,2*m2;for i:=1 to n do main;if ans=maxlongint then writeln(-1) else writeln(ans);close(input);close(output);end.道路游戏问题转述：有一条环形路，路上有n个点，第i个点和第i+1个点有边相连（第n个点与第1个点有边相连）。每个点都可以花费不同的代价生产一个机器人，且机器人可以顺时针走不多于p步（每走一步消耗一单位时间），并捡起此时路上的金币。最多只能有一个机器人存在于路上。不同的时间每条路上金币数不同。求最后能够得到的最大金币数。（即捡起的金币数减去生产机器人需要的金币数）。分析： 题目描述极其恶心，整理好思绪之后便应该能想出本题是动态规划。由于高达1000的m，n，所以只能设计时间复杂度为O(mn)的动规。此类问题的动规模型比较好想，即：其中fi,j为i时间在j点上得到的最大金币数。Coini,j为i时间j号路得金币数。Costk代表在k点购买机器人花费的金币数。其中1=k=n。stepi,j代表fi,j的状态时机器人已经走的步数。pastj为j之前的点。即pasti=i-1(2=i=n) past1=n。注意这个动规是三维的，但是因为上一阶段的最优值是不变的，所以我们只需要在计算本阶段的最优值之后顺便保存一个最大的，作为下一阶段的上一阶段最优值即可。程序：var i,j,k,n,m,p,pastmax,nowmax:longint; coin,f,step:array0.1000,0.1000 of longint; cost,past:array1.1000 of longint;beginassign(input,game.in);reset(input);assign(output,game.out);rewrite(output);filldword(step,sizeof(step) shr 2,maxlongint);readln(n,m,p);for i:=2 to n do pasti:=i-1;past1:=n;for i:=1 to n do for j:=1 to m do read(coinj,i);for i:=1 to n do read(costi);pastmax:=0;for i:=1 to m do begin nowmax:=-maxlongint; for j:=1 to n do begin if stepi-1,pastjfi-1,pastj then begin stepi,j:=1;fi,j:=pastmax-costpastj+coini,pastj;end else begin stepi,j:=stepi-1,pastj+1;fi,j: