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]<temp2)) do inc(i);
   while (a[j,1]<temp1) or ((a[j,1]=temp1) and (a[j,2]>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.


细胞分裂
问题转述：
给出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.


第一次写解题报告，如有错误，请多包涵。