求2012十八届NOIP普及组初赛试题（有选择题也行）最快者加分
第十八届全国青少年信息学奥林匹克联赛初赛
普及组参考答案
一、单项选择题（共20题，每题1.5分，共计30分）
1 2 3 4 5 6 7 8 9 10
A B A B C C B C A A
11 12 13 14 15 16 17 18 19 20
B D B C C D C A C B
二、问题求解（共2题，每题5分，共计10分）
1. 5
2. 2880
三、阅读程序写结果（共4题，每题8分，共计32分）
1. 10
2. 6
3. 14
4. ACBBADAD
四、完善程序（前2空每空2分，后8空每空3分，共计28分）以下各程序填空可能还有一些等价的写
法，各省赛区可请本省专家审定和上机验证，可以不上报CCF NOI科学委员会检查。
Pascal语言
1 ① 0
② y[j] y[j]）
③
inc(f[i])
（或f[i] := f[i] + 1）
④ f[i] >= max_f（或max_f <= f[i]，两种答案均必须有等号）
⑤ ans := i
2 ① false
② used[data[i]] := false
③ j
④ n
⑤ break
其中，false可以用0代替。
求 GDOi2005标程
POJ(注：北大程序设计在线测评、仅向亲们解释、内行人请无视)又挂了、不知搞什么。于是我开始着手做ZOJ(浙大的、)，发现水题挺多的、不过英文比ural(俄罗斯的、貌似题目质量很高)好理解多了。现在不努力不行了、经过这次GDOI、我算深刻地认识到差距了。
』』这次GDOI题目虽然比往年简单一些、但是涉及的算法内容还是比较广的、第一天跟第二天的算法大概包括最简单的O(NlogN)以下的排序、动态规划、搜索+剪枝、哈希、离散化、最小生成树、哈夫曼树、最短路径、 最大流最小割、优先队列etc. 暂时只记得这些…其中动态规划和网络流这部分、是我十分生疏的。而其他我比如熟悉的算法也并没有拿多少分。我认为主要原因是对细节的处理不够、还有是编程能力有待提高。想到和标程一样的算法思路、可就是得分很低、明显是编程能力的问题。本质还是做题太少。明年、我将迎来OI生涯最后一次GDOI、不能再贪玩了。加油！
』』2010。相信很成为竞争最激烈的一年。剩下这一年、有很多东西需要放下。绝不能再留下任何遗憾。
noip2009普及组复赛解题报告
多项式输出
问题转述：
给出一个一元多项式各项的次数和系数，按照规定的格式要求输出该多项式。
分析：
普及组的水题。多项式大家应该很熟悉，输出的时候注意一下几点即可：
1. 最高次项为正的话开头无加号。
2. 系数为0不输出。
3. 一次项输出x，并非x^1。
4. 非常数项系数为1或-1时直接输出正负号，但是常数项需要输出该数字。
其中除第三项外其它均可在样例中检查出错误，但是若没想到第三点那么就只能得到50分了。
程序：
var i,k,n:longint;
begin
assign(input,'poly.in');reset(input);
assign(output,'poly.out');rewrite(output);
readln(n);
for i:=n downto 0 do
begin
read(k);
if k=0 then continue;
if (k>0) and (in) then write('+');
if i=0 then write(k)
else if (abs(k)1) then write(k) else if k=-1 then write('-');
if i0 then
if i=1 then write('x')
else write('x^',i);
end;
writeln;
close(input);
close(output);
end.
2009-11-28 12:03 回复
自杀猫
0位粉丝
3楼
分数线划定
问题转述：
给出录取人数及所有面试者成绩，考号。求出分数线和实际录取人数，并按成绩降序，若成绩相同则考号升序的规则输出录取人考号与成绩。
分析：
双关键字排序。由于n在5000左右，为了确保不TLE所以需要使用快排等nlogn的排序。之后将指针指向计划录取的最后一名，并滑动至与其相同分数的最后一人。则指针之前为实际录取的面试者。
程序：
type arr=array[1..2] of longint;
var i,j,n,m:longint;
a:array[1..5001] of arr;
procedure swap(var a,b:arr);
var c:arr;
begin
c:=a;a:=b;b:=c;
end;
procedure qsort(l,r:longint);
var i,j,temp1,temp2:longint;
begin
i:=l;j:=r;temp1:=random(r-l+1)+l;
temp2:=a[temp1,2];temp1:=a[temp1,1];
repeat
while (a[i,1]>temp1) or ((a[i,1]=temp1) and (a[i,2]<temp2)) do inc(i);
while (a[j,1]temp2)) do dec(j);
if i<=j then
begin
swap(a[i],a[j]);
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
begin
randomize;
assign(input,'score.in');reset(input);
assign(output,'score.out');rewrite(output);
readln(n,m);
m:=trunc(m*1.5);
for i:=1 to n do readln(a[i,2],a[i,1]);
a[n+1,1]:=0;
qsort(1,n);
i:=m;
while a[i+1,1]=a[i,1] do inc(i);
writeln(a[i,1],' ',i);
for j:=1 to i do
writeln(a[j,2],' ',a[j,1]);
close(input);close(output);
end.
2009-11-28 12:04 回复
自杀猫
0位粉丝
4楼
细胞分裂
问题转述：
给出m1，m2以及若干个个si，求si^a mod m1^m2=0中a的最小值。若无解，输出-1。
分析：
数学题。由于m1<=30000,m2<=10000，根本无法直接计算，所以需要通过数学分析得出答案。如果一个数能够整除另一个数，那么这个数因数分解后一定有另一个数所有的元素，且每个元素个数均大于等于另一个数相同元素的个数。因此我们可以先对m1进行因数分解，并将对应元素的个数乘以m2。之后读入每个数，判断该数因数分解后是否有m1中所有的元素。如果有的话，则计算该细胞最大的分裂次数，即对应m1种元素个数/si中元素个数后向上取整。最后更新答案即可。
注意因数分解中1比较特殊，所以要单独判断一下。
程序：
type arr=array[1..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;
begin
i:=1;
link:=0;
repeat
inc(i);
if k mod i=0 then
begin
inc(link);
a[link,1]:=i;
a[link,2]:=0;
while k mod i=0 do
begin
inc(a[link,2]);
k:=k div i;
end;
end;
until k=1;
end;
procedure main;
var i,z,max:longint;
begin
max:=-1;
read(k);
for i:=1 to total do
begin
if k mod a[i,1]0 then exit;
z:=0;
while k mod a[i,1]=0 do
begin
inc(z);
k:=k div a[i,1];
end;
if (a[i,2]+z-1) div z>max then max:=(a[i,2]+z-1) div z;
end;
if max<ans then ans:=max;
end;
begin
assign(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 a[i,2]:=a[i,2]*m2;
for i:=1 to n do
main;
if ans=maxlongint then writeln(-1) else writeln(ans);
close(input);
close(output);
end.
2009-11-28 12:05 回复
自杀猫
0位粉丝
5楼
道路游戏
问题转述：
有一条环形路，路上有n个点，第i个点和第i+1个点有边相连（第n个点与第1个点有边相连）。每个点都可以花费不同的代价生产一个机器人，且机器人可以顺时针走不多于p步（每走一步消耗一单位时间），并捡起此时路上的金币。最多只能有一个机器人存在于路上。不同的时间每条路上金币数不同。求最后能够得到的最大金币数。（即捡起的金币数减去生产机器人需要的金币数）。
分析：
题目描述极其恶心，整理好思绪之后便应该能想出本题是动态规划。由于高达1000的m，n，所以只能设计时间复杂度为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。
注意这个动规是三维的，但是因为上一阶段的最优值是不变的，所以我们只需要在计算本阶段的最优值之后顺便保存一个最大的，作为下一阶段的上一阶段最优值即可。
程序：
var i,j,k,n,m,p,pastmax,nowmax:longint;
coin,f,step:array[0..1000,0..1000] of longint;
cost,past:array[1..1000] of longint;
begin
assign(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
past[i]:=i-1;
past[1]:=n;
for i:=1 to n do
for j:=1 to m do
read(coin[j,i]);
for i:=1 to n do read(cost[i]);
pastmax:=0;
for i:=1 to m do
begin
nowmax:=-maxlongint;
for j:=1 to n do
begin
if step[i-1,past[j]]<p then
begin
if pastmax-cost[past[j]]>f[i-1,past[j]]
then begin step[i,j]:=1;f[i,j]:=pastmax-cost[past[j]]+coin[i,past[j]];end
else begin step[i,j]:=step[i-1,past[j]]+1;f[i,j]:=f[i-1,past[j]]+coin[i,past[j]];end;
end
else begin step[i,j]:=1;f[i,j]:=pastmax-cost[past[j]]+coin[i,past[j]];end;
if f[i,j]>nowmax then nowmax:=f[i,j];
end;
pastmax:=nowmax;
end;
writeln(nowmax);
close(input);
close(output);
end.
