NOIP2009普及组复赛试题解题报告

1、NOIP2009 普及组复赛试题解题报告许建峰1、多项式输出 本题只是一个基本知识点考核的一个题目， 主要是看参赛选手的细心程度， 无算法体现。 先定义一个系数的数组 a105 。 首先这一题解题的大的方向需要考虑两点，多项式系数 ai 大于零和小于零两种情况， 因为系数为零时不输出该项，而大于零的要求输出含有“+”号，小于零的直接输出。然后在分项进行处理： 第一项要单独处理，在处理第一项时有 3 种情况如下： If (ai=1)Else if (ai=-1)Else if (ai!=0) 接着对第二项到第 n-1 项进行处理 这里在循环里面处理 又有( ai0 & ai!=1 ) (ai=1

2、 ) ( ai0 和 an0 两种情况分别讨论最终即可解出本 题。参考程序如下：#includestdio.h main()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)fprin tf(fout,xA%d, n);else if(a0=-1)fprin tf(fout,-xA%d, n);else if (a0!=0) fprintf(fout,%dxA%d,a0,n

3、);for(i=1;i0 & ai!=1) fprintf(fout,+%dxA%d,ai,n-i);if (ai=1) fprintf(fout,+xA%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、分数线划定本题就是一个基本的简单排序题目， 由于数据范围比较小， 不需要用到快排或者其他排 序，只要会一种基本的排序即可，

4、比如用最熟悉的冒泡就可以完成该题的所有测试数据。首先定义两个数组一个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)aj+1=t;numj+1=t;t=aj; aj=aj+1; t=numj; numj=numj+1;for(i=0;i=ak-1)s+;fprintf(fout,%d %dn,