NOIP2009复赛答案

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 (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 then
if i=1 then write('x')
else write('x^',i);
end;
writeln;
close(input);
close(output);
end.

分线划定

问题转述：
给出录取人数及所有面试者成绩，考号。求出分数线和实际录取人数，并按成绩降序，若成绩相同则考号升序的规则输出录取人考号与成绩。
分析：
双关键字排序。由于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] 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 iif 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.

细胞分裂

问题转述：
给出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 maxend;

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.

道路游戏
问题转述：
有一条环形路，路上有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]]

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.