T1玩具谜题
Solution
这一年唯一一道良心题，直接加上在取个模就可以了。
Code
#include<iostream> #include<cstdio> using namespace std; int a[100009],n,m,tag,num,now; char b[100009][109]; int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;++i) scanf("%d%s",&a[i],&b[i]); now=0; for(int i=1;i<=m;++i) { scanf("%d%d",&tag,&num); if(tag==a[now]) now=((now-num)%n+n)%n; else now=(now+num)%n; } cout<<b[now]; return 0; }
T2天天爱跑步
https://www.cnblogs.com/ZH-comld/p/9384690.html
T3换教室
Solution
对于路径的问题，弗洛伊德跑一下就可以了。
对于这道题，比较朴素的想法是设dp[i][j][0/1]表示在i天，申请了j次，现在的位置（前一天是否申请成功）。
但这样是有问题的，因为不能体现出申请的时候的成功与失败结果。
写起来也是有问题的，甚至没有办法初始化。。。。
所以我们要算出每次走的路径的期望，所以我们设dp[i][j][0/1]表示在i时刻，一共申请了j次，有没有提交申请。
转移的话枚举上一次是否申请了，边权要乘上上一次成功的概率和这次成功的概率。
Code
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int c[2009],d[2009],n,m,v,e,u,o; double dis[309][309],dp[2009][2009][2],k[2009],ans,w; int main() { cin>>n>>m>>v>>e; ans=1e20; for(int i=1;i<=v;++i) for(int j=1;j<=v;++j) dis[i][j]=1e15; for(int i=1;i<=n;++i) scanf("%d",&c[i]); for(int i=1;i<=n;++i) scanf("%d",&d[i]); for(int i=1;i<=n;++i) scanf("%lf",&k[i]); for(int i=1;i<=v;++i)dis[i][i]=0; for(int i=1;i<=e;++i) { scanf("%d%d%lf",&u,&o,&w); if(w<dis[u][o])dis[u][o]=w,dis[o][u]=w; } for(int l=1;l<=v;++l) for(int i=1;i<=v;++i) for(int j=1;j<=v;++j) dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]); for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) dp[i][j][0]=dp[i][j][1]=1e15; /* for(int i=1;i<=v;++i) for(int j=1;j<=v;++j) printf("%.2lf ",dis[i][j]);*/ dp[1][1][1]=dp[1][0][0]=0; w=1; for(int i=2;i<=n;++i) for(int j=0;j<=m;++j) { dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+dis[c[i-1]][c[i]]*(w-k[i-1])+dis[d[i-1]][c[i]]*k[i-1]); if(j>=1)dp[i][j][1]=min(dp[i-1][j-1][0]+dis[c[i-1]][c[i]]*(w-k[i])+dis[c[i-1]][d[i]]*k[i],dp[i-1][j-1][1]+dis[c[i-1]][c[i]]*(w-k[i-1])*(w-k[i])+dis[c[i-1]][d[i]]*(w-k[i-1])*k[i]+dis[d[i-1]][c[i]]*(k[i-1])*(w-k[i])+dis[d[i-1]][d[i]]*k[i-1]*k[i]); } for(int i=0;i<=m;++i) ans=min(min(ans,dp[n][i][0]),dp[n][i][1]); printf("%.2lf",ans); return 0; }
T4组合数问题
Solution
也是一道良心题，n平方求组合数对k取个模，求一个前缀和，每次询问可以做到O（1）回答。
Code
#include<iostream> #include<cstdio> using namespace std; int y[2009][2009],t,k,n,m; long long dp[2009][2009]; int main() { scanf("%d%d",&t,&k); y[1][1]=1; for(int i=2;i<=2002;++i) for(int j=1;j<=i;++j) y[i][j]=(y[i-1][j-1]+y[i-1][j])%k; /* for(int i=1;i<=10;++i) { for(int j=1;j<=min(i,10);++j) cout<<y[i][j]<<" "; cout<<endl; }*/ for(int i=1;i<=2002;++i) for(int j=1;j<=i;++j) if(i!=j)dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(y[i][j]==0); else dp[i][j]=dp[i][j-1]; while(t--) { scanf("%d%d",&n,&m); if(m>n)m=n; printf("%lld ",dp[n+1][m+1]); } return 0; }
T5蚯蚓
观察到先被切断的一定比后切段的长度大，开三个队列维护即可。
#include<iostream> #include<cstdio> #include<algorithm> #define N 7000002 #define inf 0x7f7f7f7f using namespace std; typedef long long ll; ll ji; double u,v; int n,m,q,tt,h[3],t[3],a[3][N],num,tag,x,y; bool cmp(int a,int b){ return a>b; } int main(){ scanf("%d%d%d%lf%lf%d",&n,&m,&q,&u,&v,&tt); for(int i=1;i<=n;++i)scanf("%d",&a[0][i]); sort(a[0]+1,a[0]+n+1,cmp); h[0]=1;t[0]=n;h[1]=h[2]=1;t[1]=t[2]=0; for(int i=1;i<=m;++i){ num=-inf; for(int j=0;j<3;++j) if(h[j]<=t[j]&&a[j][h[j]]>num){ num=a[j][h[j]]; tag=j; } if(!(i%tt))printf("%lld ",num+ji); num+=ji; h[tag]++; x=num*(double)u/v; y=num-x; a[1][++t[1]]=x-q-ji; a[2][++t[2]]=y-q-ji; ji+=q; } printf(" "); for(int i=1;i<=n+m;++i){ num=-inf; for(int j=0;j<3;++j) if(h[j]<=t[j]&&a[j][h[j]]>num){ num=a[j][h[j]]; tag=j; } h[tag]++; if(!(i%tt))printf("%lld ",num+ji); } return 0; }
T6愤怒的小鸟
直接dp复杂度过高无法接受。
我们每次取出一个状态钦定里面第一个0和我枚举的点组成一条抛物线，他们的代价我可以n^2预处理处理出来。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define N 20 #define eps 1e-8 using namespace std; int ji[N][N],n,m,dp[1<<18],t,ma; double x[N],y[N],a,b; inline int get(int i) { for(int j=0;j<n;++j) if(!(i&(1<<j)))return j+1; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]); memset(ji,0,sizeof(ji)); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) { if(fabs(x[i]-x[j])<eps)continue; a=(y[i]*x[j]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j])); if(a>-eps)continue; b=y[i]/x[i]-a*x[i]; for(int k=1;k<=n;++k) if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps)ji[i][j]|=(1<<k-1); // cout<<i<<" "<<j<<" "<<ji[i][j]<<endl; } ma=(1<<n)-1; memset(dp,0x3f,sizeof(dp)); dp[0]=0; for(int i=0;i<ma;++i) { int u=get(i); for(int j=u+1;j<=n;++j) if(!(i&(1<<j-1))) { if(ji[u][j])dp[i|ji[u][j]]=min(dp[i|ji[u][j]],dp[i]+1); dp[i|(1<<j-1)]=min(dp[i|(1<<j-1)],dp[i]+1); } dp[i|(1<<u-1)]=min(dp[i|(1<<u-1)],dp[i]+1); } cout<<dp[ma]<<endl; } return 0; }