这就是现在联赛的难度么，，，这谁顶得住啊
数据量不大，模拟就行，这题给我感觉有点像 负负得正 的意思，比如朝内的左边等于朝外的右边
所以我设朝内为1，朝外为-1； 右为1，左为-1，然后就可以愉快的模拟啦
#include<bits/stdc++.h> using namespace std; int n,m; struct node{ int to; char s[15]; }pr[100100]; int main(){ // freopen("toy.in","r",stdin); // freopen("toy.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ cin>>pr[i].to>>pr[i].s; if(pr[i].to==0)pr[i].to=1; else pr[i].to=-1; } int now=1; for(int i=1;i<=m;i++){ int ai,si; scanf("%d%d",&ai,&si); if(ai==0)ai=-1; now=(now+si*pr[now].to*ai+n)%n; if(now==0)now=n; } cout<<pr[now].s; return 0; }
这，，，居然是B题，，，
考试时的暴力只拿了25分，hh，没办法，除了暴力真想不出其他办法了
正解可以用差分+lca+桶，也可以用树链剖分（啥玩意完全没听过）
但，，，，题解完全看不懂，，，
依然没有代码的第三天，，，，
这题我完全是被一大堆输入数据和蜜汁概率给整蒙了，又想到是第三题于是蜜汁感到恐惧，，，只有边打暴力边骂辣鸡题目
我的暴力连样例都没过居然骗了16分你敢信？
正解：动态规划，概率期望
完全没往动规上面去想过，，，
其实看懂了题还是不难的
洛谷上看到一篇题解讲的挺好的，于是我就把它搬运过来了，，
一、当前教室没有申请 如果前一教室有申请： f[i][j][0]=min(f[i-1][j][1]f[i][j][0]=min(f[i−1][j][1] （1）成功：+k[i-1]*dis[d[i-1]][c[i]]+k[i−1]∗dis[d[i−1]][c[i]] （2）失败：+(1-k[i-1])*dis[c[i-1]][c[i]]+(1−k[i−1])∗dis[c[i−1]][c[i]] 如果前一教室没有申请：,f[i-1][j][0],f[i−1][j][0],一定是前后均失败：+dis[c[i-1]][c[i]])+dis[c[i−1]][c[i]]) 二、当前教室有申请 如果前一教室有申请：f[i][j][1]=min(f[i-1][j-1][1]f[i][j][1]=min(f[i−1][j−1][1] （1）前后均成功：+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i−1]∗k[i]∗dis[d[i−1]][d[i]] （2）前成功、后失败：+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+k[i−1]∗(1−k[i])∗dis[d[i−1]][c[i]] （3）前失败、后成功：+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1−k[i−1])∗k[i]∗dis[c[i−1]][d[i]] （4）前后均失败：+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]+(1−k[i−1])∗(1−k[i])∗dis[c[i−1]][c[i]] 如果前一教室没有申请：,f[i-1][j-1][0],f[i−1][j−1][0] （1）后成功：+k[i]*dis[c[i-1]][d[i]]+k[i]∗dis[c[i−1]][d[i]] （2）后失败：+(1-k[i])*dis[c[i-1]][c[i]])+(1−k[i])∗dis[c[i−1]][c[i]])
以后遇到这种题应该不至于全程懵逼吧，，，，应该，，，，
#include<bits/stdc++.h> #define inf 999999999 using namespace std; int n,m,v,e,c[10010],d[10010],a[2005][2005]; double k[10010],ans,f[2005][2005][2];//前i个时间点，共申请了j次，第i个时间点否/是进行了申请。 int main(){ // freopen("classroom.in","r",stdin); // freopen("classroom.out","w",stdout); scanf("%d%d%d%d",&n,&m,&v,&e); 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++) for(int j=1;j<i;j++)a[i][j]=a[j][i]=inf; for(int i=1;i<=e;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x][y]=a[y][x]=min(a[x][y],z); } for(int k1=1;k1<=v;k1++) for(int i=1;i<=v;i++) for(int j=1;j<i;j++) if (a[i][j]>a[i][k1]+a[k1][j]) a[j][i]=a[i][j]=a[i][k1]+a[k1][j]; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++)f[i][j][0]=f[i][j][1]=inf; f[1][0][0]=0; f[1][1][1]=0; for(int i=2;i<=n;i++) for(int j=0;j<=m;j++){ f[i][j][0]=min(f[i-1][j][1]+k[i-1]*a[d[i-1]][c[i]]+(1-k[i-1])*a[c[i-1]][c[i]], f[i-1][j][0]+a[c[i-1]][c[i]]); if(j!=0) f[i][j][1]=min(f[i-1][j-1][1]+k[i-1]*k[i]*a[d[i-1]][d[i]]+k[i-1]*(1-k[i])*a[d[i-1]][c[i]]+(1-k[i-1])*k[i]*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]], f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]]); } ans=inf; for(int i=0;i<=m;i++) ans=min(ans,min(f[n][i][0],f[n][i][1])); printf("%.2lf",ans); return 0; }