网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
noip吧 关注：25,171贴子：642,107

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.



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


赞一个，希望能加注释，另开贴发注释版的话，会加精的


本帖因“辛苦，特此支持”而被加精。


快试试吧，
可以对自己使用挽尊卡咯~
◆
◆
气死了
机子出问题
读不进
花掉一小时
都没自己测一下
完了
一等奖。。。。。。


加个c++版本第一题#include<fstream>
using namespace std;
ifstream cin;
ofstream cout;
int main(){  
cin.open("poly.in");  
cout.open("poly.out");  
int n;  
cin>>n;  
int a[n+1];  
int s=n;  
for(int i=0;i<n+1;i++)cin>>a[i];  
if(a[0]>0){  
if(a[0]!=1)cout<<a[0]<<"x^"<<n;  
else cout<<"x^"<<n;}  
if(a[0]<0){     
if(a[0]!=-1)cout<<a[0]<<"x^"<<n;     
else cout<<"-x^"<<n;     
}  
n--;  
for(int i=1;i<s;i++){  
if(a[i]>0){  
if(a[i]!=1)cout<<"+"<<a[i]<<"x^"<<n;  
else cout<<"+x^"<<n;}  
if(a[i]<0){     
if(a[i]!=-1)cout<<a[i]<<"x^"<<n;     
else cout<<"-x^"<<n;     
}  
n--;   
}  
if(a[s+1]>0)cout<<"+"<<a[s+1];  
if(a[s+1]<0)cout<<a[s+1];  
return 0;}
大家也踊跃发吧！


第二题
#include<fstream>
#include<stdlib.h>
using namespace std;
ifstream cin("score.in");
ofstream cout("score.out");
struct student
{
     int k,s;
};
int comp(const void *a,const void *b)
{
     student *c=(student *)a,*d=(student *)b;
     if(c->s!=d->s)return d->s-c->s;
     return c->k-d->k;
}
int main()
{
     int i,j,n,m;
     student a[5001];
     cin>>n>>m;
     for(i=0;i<n;i++)
         cin>>a[i].k>>a[i].s;
     m=m+m/2;
     qsort(a,n,sizeof(student),comp);
     for(j=m-1;j<n;j++)
         if(a[j].s==a[m-1].s)
             m=j+1;
         else
             break;
     cout<<a[m-1].s<<' '<<m<<endl;
     for(i=0;i<m;i++)
         cout<<a[i].k<<' '<<a[i].s<<endl;
     return 0;
}



第三题
#include<fstream>
#include<cmath>
using namespace std;
ifstream cin("cell.in");
ofstream cout("cell.out");
bool zhishu(int n)
{
     int i;
     bool f=true;
     for(i=2;i<=sqrt(n);i++)
         if(n%i==0)
         {
             f=false;
             break;
         }
     return f;
}
int main()
{
     int b[30001],c[30001],d[30001],i,j,k,n,m1,m2,min,max,s[10001];
     cin>>n>>m1>>m2;
     for(i=0;i<n;i++)
         cin>>s[i];
     memset(b,0,sizeof(b));
     memset(d,0,sizeof(d));
     for(i=2;i<=m1;i++)
     {
         if(m1%i==0&&zhishu(i))
         {
             while(m1%i==0)
             {
                 b[i]++;
                 m1/=i;
             }
             d[k++]=i;
             for(j=0;j<n;j++)
                 if(s[j]%i!=0)
                     s[j]=-1;
         }
         b[i]*=m2;
     }
     min=2000000001;
     for(i=0;i<n;i++)
     {
         if(s[i]==-1)
             continue;
         max=0;
         memset(c,0,sizeof(c));
         for(j=0;j<k;j++)
             while(s[i]%d[j]==0)
             {
                 c[d[j]]++;
                 s[i]/=d[j];
             }
         for(j=0;j<k;j++)
             if(b[d[j]]>=c[d[j]])
                 if(((b[d[j]]+c[d[j]]-1)/c[d[j]])>=max)
                     max=(b[d[j]]+c[d[j]]-1)/c[d[j]];
         if(max<min)
             min=max;
        
     }
     if(min<2000000001)
         cout<<min;
     else
         cout<<-1;
     cout<<endl;
     return 0;
}



真是太震撼了，虽然第4题我也想到用动归，但编了一半就云里雾里了。
这是我的QQ：1149901132
如果有兴趣的话，可以跟我在QQ讨论C
注：如果想加我的话要注明“百度 noip吧”（最好再加上姓名）


太高明了，不愧为高中生，我才初一....


快试试吧，
可以对自己使用挽尊卡咯~
◆
◆
第四题，你局部最优了，但好像剩下次数没最优。
就是说你f【i，j】得到了最优，但剩下次数没跟上来，不行吧


第四题
#include<fstream>
using namespace std;
ifstream cin("game.in");
ofstream cout("game.out");
int coin[1005][1005],cost[1005],f[1005][1005],step[1005][1005],past[1005],i,j,k,m,n,p,pastmax=0,nowmax;
int main()
{
     cin>>n>>m>>p;
     for(i=0;i<n;i++)
         for(j=0;j<m;j++)
             cin>>coin[j][i];
     for(i=0;i<n;i++)cin>>cost[i];
     memset(f,0,sizeof(f));
     memset(step,0xfffff,sizeof(step));
     for(i=1;i<n;i++)past[i]=i-1;
     past[0]=n-1;
     nowmax=-0xfffff;
     for(j=0;j<n;j++)
     {
         step[0][j]=1;
         f[0][j]=pastmax-cost[past[j]]+coin[0][past[j]];
         if(f[0][j]>nowmax)nowmax=f[0][j];
     }
     pastmax=nowmax;
     for(i=1;i<m;i++)
     {
         nowmax=-0xfffff;
         for(j=0;j<n;j++)
         {
             if(step[i-1][past[j]]<p)
             {
                 if(pastmax-cost[past[j]]>f[i-1][past[j]])
                 {
                     step[i][j]=1;
                     f[i][j]=pastmax-cost[past[j]]+coin[i][past[j]];
                 }
                 else
                 {
                     step[i][j]=step[i-1][past[j]]+1;
                     f[i][j]=f[i-1][past[j]]+coin[i][past[j]];
                 }
             }
             else
             {
                 step[i][j]=1;
                 f[i][j]=pastmax-cost[past[j]]+coin[i][past[j]];
             }
             if(f[i][j]>nowmax)nowmax=f[i][j];
         }
         pastmax=nowmax;
     }
     cout<<nowmax<<endl;
     return 0;
}



扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
分享到: