首页 > 代码库 > [NOIP2003] 普及组

[NOIP2003] 普及组

 

乒乓球

模拟

 1 /*By SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=15000; 9 char s[50];10 int a[mxn],b[mxn];//11分制胜负计数11 int c[mxn],d[mxn];//21分制计数 12 int main(){13     bool flag=1;14     int i,j;15     int r1=1,r2=1;//比赛局数 16     while(scanf("%s",s)!=EOF && flag){17         int n=strlen(s);18         for(i=0;i<n;i++){19             if(s[i]==E){20                 flag=0;21                 break;22             }23             if(s[i]==W){24                 a[r1]++;c[r2]++;25                 if(a[r1]>=11 && a[r1]-b[r1]>=2)r1++;26                 if(c[r2]>=21 && c[r2]-d[r2]>=2)r2++;27             }28             if(s[i]==L){29                 b[r1]++;d[r2]++;30                 if(b[r1]>=11 && b[r1]-a[r1]>=2)r1++;31                 if(d[r2]>=21 && d[r2]-c[r2]>=2)r2++;32             }33         }34     }35     for(i=1;i<=r1;i++)printf("%d:%d\n",a[i],b[i]);36     cout<<endl;37     for(i=1;i<r2;i++)printf("%d:%d\n",c[i],d[i]);38     printf("%d:%d",c[r2],d[r2]);39     return 0;40 }

 

数字游戏

DP 枚举分组 f[k组][前i个]=最值

 1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 using namespace std; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}11     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}12     return x*f;13 }14 int n,m;15 int a[120];16 int smm[120];17 int fmx[120][20];18 int fmi[120][20];19 int mxans=0,minans=1e8;20 void dp(int b[]){21     memset(fmx,0,sizeof fmx);22     memset(fmi,0x2f,sizeof fmi);23     int i,j;24     for(i=1;i<=n;i++)smm[i]=smm[i-1]+b[i];25     for(i=1;i<=n;i++){26         fmx[i][1]=fmi[i][1]=(smm[i]%10+10)%10;27     }28     fmi[0][0]=fmx[0][0]=1;29     int k;30     for(k=2;k<=m;k++){31         for(i=k;i<=n;i++){32             for(j=k-1;j<i;j++){33                 fmx[i][k]=max(fmx[i][k],fmx[j][k-1]*(((smm[i]-smm[j])%10+10)%10));34                 fmi[i][k]=min(fmi[i][k],fmi[j][k-1]*(((smm[i]-smm[j])%10+10)%10));35             }36         }37     }38     mxans=max(mxans,fmx[n][m]);39     minans=min(minans,fmi[n][m]);40     return;41 }42 int main(){43     n=read();m=read();44     int i,j;45     for(i=1;i<=n;i++){46         a[i]=read();47         a[n+i]=a[i];48     }49     for(i=0;i<n;i++)dp(a+i);50     printf("%d\n%d\n",minans,mxans);51     return 0;52 }

 

 

卡塔兰数

C(2*n,n)/(n+1)

 1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 #include<string> 8 using namespace std; 9 int n;10 long long ans=1;11 int main(){12     int i,j;13     scanf("%d",&n);14     int ed=n*2;15     for(i=n+1;i<=ed;i++){16         ans=ans*i/(i-n);17     }18     ans/=(n+1);19     printf("%lld\n",ans);20     return 0;21 }

 

 

 

麦森数

位数直接计算:log(10,2^n)

数字用高精度乘法模拟

 1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdio> 5 using namespace std; 6 int la; 7 int t=1; 8 unsigned int n=0;//指数  9 struct node{10     int v[2000];11     int s;12 }a,b,c;13 node multiple(const node a,const node b );14 void pbi(node &c,unsigned int n1)//底数 指数15 {16     if(n1==0||n1==1){17         c.s=1;18         c.v[0]=n1+1;19         return;20     }21     pbi(c,n1/2);22     c=multiple(c,c);23     if(n1%2==1){24         b.s=1;25         b.v[0]=2;26         c=multiple(b,c);27     }28  }29 30 node multiple(const node a,const node b ){ //高精度乘法部分 31     int i,j,x=0;32     if(a.s==1&&a.v[0]==0)return a;33     if(b.s==1&&b.v[0]==0)return b;34     const int L=500;35     node c1={0};36     for(i=0;i<L && i<a.s;i++){37         for(j=0;j<L && j<b.s;j++){38             c1.v[i+j]+=a.v[i]*b.v[j];39             c1.v[i+j+1]+=c1.v[i+j]/10;40             c1.v[i+j]%=10;41         }42         c1.s=i+j;43         if(c1.v[i+j]!=0)c1.s++;44     }45     if(c1.s>500) c1.s=500;46     return c1;47 }48 int main(){49     int i;50     cin>>n;51     int p=ceil(n*log10(2));//位数 52     printf("%d\n",p);53     pbi(c,n);54     c.v[0]-=1;55     if(c.s>500) c.s=500;56     for (int i=499;i>=0;i--)//mx 57     {58         printf("%d",c.v[i]);59         if (i%50==0)//50位的倍数时回车 60             cout<<endl;61     }62     return 0;63 }

 

 

/*By SilverN*/#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>usingnamespacestd; int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int n,m; int a[120]; int smm[120]; int fmx[120][20]; int fmi[120][20]; int mxans=0,minans=1e8; void dp(int b[]){ memset(fmx,0,sizeof fmx); memset(fmi,0x2f,sizeof fmi); int i,j; for(i=1;i<=n;i++)smm[i]=smm[i-1]+b[i]; for(i=1;i<=n;i++){ fmx[i][1]=fmi[i][1]=(smm[i]%10+10)%10; } fmi[0][0]=fmx[0][0]=1; int k; for(k=2;k<=m;k++){ for(i=k;i<=n;i++){ for(j=k-1;j<i;j++){ fmx[i][k]=max(fmx[i][k],fmx[j][k-1]*(((smm[i]-smm[j])%10+10)%10)); fmi[i][k]=min(fmi[i][k],fmi[j][k-1]*(((smm[i]-smm[j])%10+10)%10)); } } } mxans=max(mxans,fmx[n][m]); minans=min(minans,fmi[n][m]); return; } int main(){ n=read();m=read(); int i,j; for(i=1;i<=n;i++){ a[i]=read(); a[n+i]=a[i]; } for(i=0;i<n;i++)dp(a+i); printf("%d\n%d\n",minans,mxans); return0; }

[NOIP2003] 普及组