2009NOIP普及组复赛解题报告

NOIP2009xx组复赛试题解题报告xx1、多项式输出本题只是一个基本知识点考核的一个题目，主要是看参赛选手的细心程度，无算法体现。

先定义一个系数的数组a[105]。

首先这一题解题的大的方向需要考虑两点，多项式系数a[i]大于零和小于零两种情况，因为系数为零时不输出该项，而大于零的要求输出含有“+”号，小于零的直接输出。

然后在分项进行处理：第一项要单独处理，在处理第一项时有3种情况如下：If (a[i]==1)Else if (a[i]==-1)Else if (a[i]!=0)接着对第二项到第n-1项进行处理这里在循环里面处理又有（a[i]>0 && a[i]!=1）（a[i]==1）（a[i]<0&& a[i]!=-1）（a[i]==-1）这四种情况分别讨论。

然后对a[n-1]项进行处理，同上面的循环里的处理方法只要注意幂指数为1的时候不需要输出就可以了，省略幂指数。

最后对常数项处理，分两种情况，a[n]>0和a[n]<0两种情况分别讨论最终即可解出本题。

参考程序如下：#include"stdio.h"main(){FILE *fin,*fout;int i,a[105],n;fin=fopen("poly.in","r");fout=fopen("poly.out","w");fscanf(fin,"%d",&n);for(i=0;i<=n;i++)fscanf(fin,"%d",&a[i]);if(a[0]==1)fprintf(fout,"x^%d",n);else if(a[0]==-1)fprintf(fout,"-x^%d",n);else if (a[0]!=0)fprintf(fout,"%dx^%d",a[0],n);for(i=1;i<n-1;i++){if(a[i]>0 && a[i]!=1) fprintf(fout,"+%dx^%d",a[i],n-i);if (a[i]==1)fprintf(fout,"+x^%d",n-i);if(a[i]<0 && a[i]!=-1)fprintf(fout,"%dx^%d",a[i],n-i);if (a[i]==-1)fprintf(fout,"-x^%d",n-i);}if(a[n-1]>0 && a[n-1]!=1)fprintf(fout,"+%dx",a[n-1]);if(a[n-1]==1)fprintf(fout,"+x");if(a[n-1]<0&&a[n-1]!=-1)fprintf(fout,"%dx",a[n-1]);if(a[n-1]==-1)fprintf(fout,"-x");if(a[n]>0)fprintf(fout,"+%d",a[n]);if(a[n]<0)fprintf(fout,"%d",a[n]);fclose(fin);fclose(fout);}2、分数线划定本题就是一个基本的简单排序题目，由于数据范围比较小，不需要用到快排或者其他排序，只要会一种基本的排序即可，比如用最熟悉的冒泡就可以完成该题的所有测试数据。

Noip2009复赛普及组1．多项式输出(poly.pas/c/cpp)【问题描述】给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。

2. 多项式中只包含系数不为0 的项。

3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系数为负，则多项式以“-”号开头。

4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。

紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。

如果x 的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果x 的指数为0，则仅需输出系数即可。

5. 多项式中，多项式的开头、结尾不含多余的空格。

【输入】输入文件名为poly.in，共有2 行第一行1 个整数，n，表示一元多项式的次数。

第二行有n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空格隔开。

【输出】输出文件poly.out 共1 行，按题目所述格式输出多项式。

【输入输出样例1】poly.in5100 -1 1 -3 0 10poly.out100x^5-x^4+x^3-3x^2+10【输入输出样例2】poly.in3-50 0 0 1poly.out-50x^3+1【数据范围】1 ≤n ≤100，多项式各次项系数的绝对值均不超过100。

(score.pas/c/cpp)【问题描述】世博会志愿者的选拔工作正在A 市如火如荼的进行。

为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。

面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150% （向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

1、潜伏者program spy;varv: array['A'..'Z'] of boolean; p, q: array['A'..'Z'] of char; a, b: string;j: char;i: integer;procedure stop;beginwriteln('Failed');close(input);close(output);halt;end;beginassign(input, 'spy.in');reset(input);assign(output, 'spy.out'); rewrite(output);readln(a);readln(b);fillchar(v, sizeof(v), 0);for i := 1 to length(a) do beginv[a[i]] := true;p[a[i]] := b[i];q[b[i]] := a[i];end;for j := 'A' to 'Z' doif not v[j] then stop;for i := 1 to length(a) do beginif p[a[i]] <> b[i] then stop; if q[b[i]] <> a[i] then stop; end;readln(a);for i := 1 to length(a) do write(p[a[i]]);writeln;close(input);close(output);end.2、Hankson的趣味题思路1：根据最大公约数的定义，X必定为最大公约数的倍数，那么我们可以去枚举a1的倍数，然后去验证最大公约数和最小公倍数是否符合条件。

期待分数：50。

程序1：vara0,a1,b0,b1,i,j,n,k,x,tot:longint;function gcd(a,b:longint):longint;beginif b=0 then exit(a) else exit(gcd(b,a mod b));end;beginreadln(n);for k:=1 to n dobegintot:=0;readln(a0,a1,b0,b1);for i:=1 to (b1 div a1) dobeginx:=i*a1;if b1 mod x=0 thenif gcd(a0,x)=a1 thenif (b0*x) div (gcd(b0,x))=b1 then begin inc(tot); end;end;writeln(tot);end;end.思路2：根据最小公倍数和最大公约数分解质因数指数的特殊关系进行优化。

Noip2007普及组复赛答案1——奖学金typeaa=recordy,s,w:integer;end;bb=recordf,h:integer;end;var a:array[1..300]of aa;b:array[1..5]of bb;n,i,j,k,t:integer;f:boolean;beginreadln(n);for i:=1 to 5 dowith b[i] do beginf:=0;h:=0;end;for i:=1 to n do beginwith a[i] do read(y,s,w);j:=1;f:=true;t:=a[i].y+a[i].s+a[i].w;while (j<=5)and f do beginif (t>b[j].f)or((t=b[j].f)and(a[i].y>a[b[j].h].y)) then begin for k:=5 downto j+1 do beginb[k].f:=b[k-1].f;b[k].h:=b[k-1].h;end;b[j].f:=t;b[j].h:=i;f:=false;end else if (t=b[j].f)and(a[i].y=a[b[j].h].y) then beginfor k:=5 downto j+2 do beginb[k].f:=b[k-1].f;b[k].h:=b[k-1].h;end;b[j+1].h:=i;b[j+1].f:=t;f:=false;end;j:=j+1;end;for i:=1 to 5 dowith b[i] do writeln(h,' ',f);end.Noip2007普及组复赛答案2——纪念品var a:array[1..30000]of byte;b:array[1..30000]of boolean;w,n,i,zu,k,ma,t:integer;beginreadln(w);readln(n);for i:=1 to 30000 do b[i]:=true;for i:=1 to n do read(a[i]);zu:=0;for i:=1 to n do beginma:=0;t:=0;if b[i] then for k:=i+1 to n doif (a[i]+a[k]<=w)and(a[i]+a[k]>ma)and b[i] and b[k] then begin ma:=a[i]+a[k];t:=k;end;if t<>0 then beginb[i]:=false;b[t]:=false;zu:=zu+1;end;end;for i:=1 to n do if b[i] then zu:=zu+1;writeln(zu);end.Noip2007普及组复赛答案3——守望者的逃离var maxs,mintime,t,m,s,t1,m1,s1:longint;procedure aa(m1,s1,t1:integer);beginif (s1>0)and(t1>0) then begins1:=s1-m1 div 10*60;t1:=t1-m1 div 10;m1:=m1 mod 10;m1:=m1+4;t1:=t1-1;aa(m1,s1,t1);m1:=m1-4;aa(m1,s1,t1);end else beginif maxs<s-s1 then maxs:=s-s1;if (t1>=0)and(mintime>t-t1) then mintime:=t-t1;end;end;beginreadln(m,s,t);maxs:=0;mintime:=2000000;t1:=t;m1:=m;s1:=s;aa(m1,s1,t1);if maxs<s then beginwriteln('No');writeln(maxs);end else beginwriteln('Yes');writeln(mintime);end;end.(pascal语言)Noip2007普及组复赛答案4——Hanoi双塔问题2007年11月21日星期三18:40var a:array[1..62]of integer;i,j,n:integer;f:boolean;beginreadln(n);for i:=2 to 62 do a[i]:=0;a[1]:=2;for i:=2 to n do beginfor j:=1 to 62 doa[j]:=a[j]*2;a[1]:=a[1]+2;for j:=1 to 62 doif a[j]>9 thenbegina[j+1]:=a[j+1]+1;a[j]:=a[j] mod10;end;end;f:=false;for i:=62 downto 1 dobeginif a[i]<>0 thenf:=true;if f then write(a[i]);end;writeln;end.(pascal语言)Noip2007普及组复赛答案4——Hanoi双塔问题2007年11月21日星期三18:40var a:array[1..62]of integer;i,j,n:integer;f:boolean;beginreadln(n);for i:=2 to 62 do a[i]:=0;a[1]:=2;for i:=2 to n do beginfor j:=1 to 62 doa[j]:=a[j]*2;a[1]:=a[1]+2;for j:=1 to 62 doif a[j]>9 thenbegina[j+1]:=a[j+1]+1;a[j]:=a[j] mod10;end;end;f:=false;for i:=62 downto 1 dobeginif a[i]<>0 thenf:=true;if f then write(a[i]);end;writeln;end.问题转述：给出一个一元多项式各项的次数和系数，按照规定的格式要求输出该多项式。

NOIP2009复赛模拟-普及组3（常州一中）3小时，400分一、游戏[问题描述]Atlantis Island沉没以前，传说中的猫老大和King是好朋友……King很喜欢赌博，这次King和老朋友猫老大多年不见，于是便邀请猫老大来玩一个游戏,猫老大应邀参加了。

King 拿出了n块黄金(0<n<10^1000002)，猫老大暗自想：咋来这么多钱的……,现在King和猫老大轮流从黄金中拿走一些,每人每次拿走的块数是2的次方(例如1,2,4,8,16……)谁能拿走最后一个黄金，谁就获胜。

现在King让猫老大先拿,双方都使用最好的策略来玩的话，谁能取得胜利呢?现在请你来帮助猫老大,他能胜利吗?[输入]一行一个数n(0<n<10^1000002)。

[输出]第一行:如果King必胜则输出“King will win.”；否则输出“MaoLaoDa will win.”。

如果是猫老大必胜的话，则再在第二行输出他第一次拿的数量，输出最小值。

[样例1]atlantis.in8atlantis.outMaoLaoDa will win.2[样例2]atlantis.in3atlantis.outKing will win.二、储蓄[问题描述]光光的手上有n元钱。

光光想利用这n 元钱去储蓄，以得到更多的钱。

光光于是就每天出入银行存取款。

光光每天需要做两件事情：存款与取款。

光光先取款（如果有到期的定期），然后给出存款额与存期、利率。

存期的单位是天，利率表示总共能得到的利率，也就是取的钱=存款额*(1+利率)，每次都去尾取整。

利率单位是百分之一。

如果定期到帐，则随时还到光光手中。

光光每天必须去且只能去一趟银行。

但由于光光乱来，所以有时候会出现存款没钱。

这时候需要你输出一行“ERROR”，并且省略掉这一行。

否则输出一行“OK”。

光光想要知道，他到第k天存钱之后还有多少现金在自己手中。

[输入]输入文件bank.in，包含：第1行：n和k，其中k代表光光总共跑银行的天数。

noip2009复赛普及组解题报告多项式输出问题转述：给出一个一元多项式各项的次数和系数，按照规定的格式要求输出该多项式。

分析：普及组的水题。

多项式大家应该很熟悉，输出的时候注意一下几点即可：1. 最高次项为正的话开头无加号。

2. 系数为0不输出。

3. 一次项输出x，并非x^1。

4. 非常数项系数为1或-1时直接输出正负号，但是常数项需要输出该数字。

其中除第三项外其它均可在样例中检查出错误，但是若没想到第三点那么就只能得到50分了。

程序：var i,k,n:longint;beginassign(input,'poly.in');reset(input);assign(output,'poly.out');rewrite(output);readln(n);for i:=n downto 0 dobeginread(k);if k=0 then continue;if (k>0) and (i<>n) then write('+');if i=0 then write(k)else if (abs(k)<>1) then write(k) else if k=-1 then write('-');if i<>0 thenif i=1 then write('x')else write('x^',i);end;writeln;close(input);close(output);end.---------------------------------------------------------------------分数线划定问题转述：给出录取人数及所有面试者成绩，考号。

求出分数线和实际录取人数，并按成绩降序，若成绩相同则考号升序的规则输出录取人考号与成绩。

noip普及组复赛答案【篇一：noip普及组复赛入门测试(答案+测试数据)】class=txt>新龟兔赛跑比赛即将举行，此次龟兔赛跑比赛的规则与以往有所不同，不再考察兔子和乌龟谁在最短的时间内跑完规定的路程，而是考察谁在规定时间内跑的路程更长，且兔子和乌龟跑步都是匀速的。

由于兔子的坏习惯，它总喜欢把比赛的总时间t小时中的k小时拿来睡觉。

现在给你比赛的总时间t、兔子的睡觉时间k、兔子的速度u、乌龟的速度v，需要你求出该次比赛谁最后获胜。

输入第一行为一个整数x，表示有x组输入数据。

每组数据只有一行，包括4个数t、k、u、v (1 ≤ t≤ 300，0 ≤ k ≤ t，1 ≤ u ≤ 100，1 ≤ v ≤ 100)。

对于每组数据，输出只有一个数，如果兔子获胜则输出-1，如果乌龟获胜则输出1，如果同时到达则输出0。

允许输入一组数后立即输出对应的结果。

样例输入：21 12 16 2 6 3样例输出：1-1varv,u,t,k,n,i:integer;beginreadln(n);for i:=1 to n do beginreadln(t,k,u,v);if v*tu*(t-k) then writeln(1);if v*tu*(t-k) then writeln(-1);if v*t=u*(t-k) then writeln(0);end;end.1、输入：26 2 6 28 6 8 2输出：-12、输入：2300 280 60 20120 0 12 13输出：113、输入：3100 20 50 30100 50 45 25100 80 27 17输出：-1114、输入：3150 77 29 23127 11 22 13139 22 13 7输出：1-1-1二、小球路程（文件名：xqlc.pas ）已知小球从100米高度自由下落，落地后反弹起，又落地，又弹起，??。

每次弹起的高度都是上一次高度的一半。

NOIP2009普及组复赛解题报告NFLS QMD第一题多项式输出1、摘要时间复杂度:O(n)空间复杂度:O(n)2、题目大意输入一个n次多项式各项的系数，按要求输出多项式3、算法分析先将不为0的系数和对应的次数存入a数组和b数组，然后依次输出。

要注意以下几点：①系数绝对值为1的情况②指数为1或0的情况③首项加号不必输出4、参考程序program poly;varn,i,g,xx:integer;a,b:array[0..200]of integer;function x(n:integer):string; //处理项的x^n部分varst1:string;beginif n=0 then x:='';if n=1 then x:='x';if n>1 thenbeginstr(n,st1);x:='x^'+st1;end;end;procedure flag(t:integer); //处理每项的符号beginif t>0 then write('+')else write('-');end;beginassign(input,'poly.in');reset(input);assign(output,'poly.out');rewrite(output);readln(n);g:=0;for i:=n downto 0 do //保存系数非零的项beginread(xx);if xx<>0 thenbeging:=g+1;a[g]:=xx;b[g]:=i;end;end;for i:=1 to g dobeginif i=1 then //处理首项的情况beginif abs(a[1])>1 then write(a[1]);if a[1]=-1 then write('-');endelsebeginflag(a[i]);if(b[i]=0)or(abs(a[i])<>1)then write(abs(a[i])); end;write(x(b[i]));end;writeln;close(input);close(output);end.第二题分数线划定1、摘要核心算法思想：排序时间复杂度：O(Nlog2N)空间复杂度：O(N)2、题目大意给出n个分数和编号(编号互不相同)，按分数从大到小取前[m*150%]个(可能有重分情况)，输出实际数目，最低分数以及按顺序排列的分数、编号。

全国信息学奥林匹克联赛（NOIP2009）复赛提高组（请选手务必仔细阅读本页内容）三．编译命令（不包含任何优化开关）五．注意事项1、文件名（程序名和输入输出文件名）必须使用小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU 1.9GHz，内存1G，上述时限以此配置为准。

各省在自测时可根据具体配置调整时限。

1.潜伏者(spy.pas/c/cpp)【问题描述】R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。

历经艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1、S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所的内容均由大写字母‘A’—‘Z’构成（无空格等其他字母）。

2、S国对于每个字母规定了对应的“密字”。

加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

3、每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。

“密字”可以和原字母相同。

例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。

现在，小C通过内线掌握了S国网络上发送的一条加密信息及其对应的原信息。

小C 希望能通过这条信息，破译S国的军用密码。

小C的破译过程是这样的：扫描原信息，对于原信息中的字母x（代表任一大写字母），找到其在加密信息中的对应大写字母y，并认为在密码里y是x的密字。

如此进行下去直到停止于如下的某个状态：1、所有信息扫描完毕，‘A’—‘Z’所有26个字母在原信息中均出现过并获得了相应的“密字”。

2、所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

3、扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S过密码的编码规则）。

例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。