首页 > 代码库 > [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*/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] 普及组