T1 玩具谜题 简单模拟。
#include<bits/stdc++.h> using namespace std; int n,m,num,ans,p; string s[100010]; bool f[100010]; int main(){ //freopen("toy.in","r",stdin); // freopen("toy.out","w",stdout); cin>>n>>m; for(int i=0;i<n;++i) cin>>f[i]>>s[i]; while(m--){ cin>>p>>num; if (p==f[ans]) ans-=num; else ans+=num; if (ans<0) ans+=n; else if (ans>=n) ans-=n; } cout<<s[ans]; }T2 天天爱跑步 玄学数链剖分，学了来贴代码。 T3 换教室 比较容易想的dp，建个三位数组，状态的话第一维存上课时间，第二维存当前教室，第三维0 1表示当前教室是否申请，转移就四种情况，一种是上个教室不申请，这个教室申请，一种是上个教室不申请，这个教室申请，一种是上个教室和这个教室都申请，最后是两个教室都不申请。前两种都只有两种可能性，因为申请成功和不成功是独立事件，所以成功和不成功是对立事件，所以可以直接用1减去申请成功的可能性。而都申请的情况下，有四种可能性，分别列出来（很恶心），都不申请的情况就只有一种可能性。然后因为数据比较小，直接可以用Floyd处理最短路，注意dp数组的初始化，最后求出最小值。
#include<bits/stdc++.h> using namespace std; int n,m,v,e,x,y,z; int c[2010],d[2010],f[310][310]; double k[2010],dp[2010][2010][2],ans=1e9; int main(){ freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); cin>>n>>m>>v>>e; memset(f,0x3f3f3f,sizeof(f)); for(int i=1;i<=n;++i){ cin>>c[i]; } for(int i=1;i<=n;++i){ cin>>d[i]; } for(int i=1;i<=n;++i){ cin>>k[i]; } for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) for(int k=0;k<=1;++k){ dp[i][j][k]=1e9; } dp[0][0][0]=0; for(int i=1;i<=e;++i){ cin>>x>>y>>z; if(f[x][y]>z) f[y][x]=f[x][y]=z; } for(int i=1;i<=v;i++){ f[i][i]=f[i][0]=f[0][i]=0; } f[0][0]=0; for(int x=1;x<=v;++x) for(int i=1;i<=v;++i) for(int j=1;j<=v;++j){ f[i][j]=f[j][i]=min(f[i][j],f[i][x]+f[j][x]); } /* for(int i=1;i<=v;i++){ for(int j=1;j<=v;++j) printf("%d ",f[i][j]); cout<<endl; }*/ for(int i=1;i<=n;++i) for(int j=0;j<=min(m,i);++j){ if(j) dp[i][j][1]=dp[i-1][j-1][0]+f[c[i-1]][d[i]]*k[i]+f[c[i-1]][c[i]]*(1-k[i]);//上个教室不选这个选 if(j>1){ dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+f[d[i-1]][d[i]]*k[i-1]*k[i]+f[c[i-1]][d[i]]*(1-k[i-1])*k[i]+f[d[i-1]][c[i]]*(1-k[i])*k[i-1]); }//上个选这个也选 if(j) dp[i][j][0]=min(dp[i-1][j][0]+f[c[i-1]][c[i]],dp[i-1][j][1]+f[c[i-1]][c[i]]*(1-k[i-1])+f[d[i-1]][c[i]]*k[i-1]);//这个教室不选上个选 else dp[i][j][0]=dp[i-1][j][0]+f[c[i-1]][c[i]];//没得选 安排 } for(int i=0;i<=n;++i){ ans=min(ans,min(dp[n][i][0],dp[n][i][1])); } printf("%.2lf\n",ans); }又是编译错误。。。。这两天真的是，下次我再打错freopen我是狗，很蠢啊两次200+都直接水爆，交之前一定要检查输入输出文件！！！
T1 组合数问题 简单数论，手推之后发现是个杨辉三角，然后试了几个数据发现不对，查了发现边界都是0，所以只需要注意单独处理边界就行了。
//orz #include<bits/stdc++.h> using namespace std; int t,k,n,m; int ans[2010][2010],a[2010][2010],b[2010][2010]; void init(){ a[0][0]=1; for (int i=1;i<=2001;++i){ a[i][0]=1; for (int j=1;j<=i;++j){ a[i][j]=(a[i-1][j]+a[i-1][j-1])%k; if (a[i][j]==0){ b[i][j]=1; } } } for (int i=1;i<=2001;++i) for (int j=1;j<=2001;++j){ ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+b[i][j]; } } int main(){ //freopen("problem.in","r",stdin); // freopen("problem.out","w",stdout); cin>>t>>k; init(); for (int i=1;i<=t;++i) { scanf("%d%d",&n,&m); printf("%d\n",ans[n][m]); } }T2 蚯蚓 题意很简单，用数组的三维一维存未切的，一维存切了之后第一段，一维存切了之后第二段，然后模拟切的过程就行了。结果只有65分，然后看题解发现需要单调队列优化。其实很容易证明，因为蚯蚓x切了之后每秒增长2p，而蚯蚓y未切每秒增长p，又因为x比y长所以x先切，所以在y切了后是肯定没有x切后的长的，所以满足单调性。（然而还是没a。。。）
//orz #include<bits/stdc++.h> using namespace std; int n,m,q,u,v,t,maxx,ans,sum,l; int a[4][10000100],now[4],Left[4],b[10001000]; double p; bool cmp(int a,int b){ return a>b; } int main(){ // freopen("earthworm.in","r",stdin); // freopen("earthworm.out","w",stdout); cin>>n>>m>>q>>u>>v>>t; p=(double)u/v; now[1]=now[2]=now[3]=1; Left[1]=n; for(int i=1;i<=n;++i){ scanf("%d",&a[1][i]); } sort(a[1]+1,a[1]+1+n,cmp); for(int i=1;i<=m;++i){ ans=-1e9; sum++; for(int j=1;j<=3;++j) if(now[j]<=Left[j]) if(ans<a[j][now[j]]){ ans=a[j][now[j]]; maxx=j; } ans+=l; l+=q; now[maxx]++; a[2][++Left[2]]=((int)double(ans*p))-l; a[3][++Left[3]]=(ans-(int)double(ans*p))-l; if(sum==t){ printf("%d ",ans); sum=0; } } cout<<endl; sum=0; for(int i=1;i<=n+m;++i){ ans=-1e9; sum++; for(int j=1;j<=3;++j) if(now[j]<=Left[j]) if(ans<a[j][now[j]]){ ans=a[j][now[j]]; maxx=j; } now[maxx]++; if(sum==t){ printf("%d ",ans+l); sum=0; } } }T3 愤怒的小鸟
结果真的是状压dp，刚好碰到我复习的盲点了，本来想今天再复习状压dp（真没怎么学懂），然后一点都打不出来，只能直接骗样例。
