题目翻译
有一个写着1~n的转盘,A和B各有一个数的集合a,b,他们分别可以将转盘的指针顺时针转动a[i]和b[j]格,先将指针转到1者胜。
对于每一个指针的初始位置以及先手情况,判断胜负。
题解
博弈论中有一个经典的结论:必胜态可以转移到必败态,必败态只能转移到必胜态。
我们知道1必败态,据此我们可以通过dfs或bfs来确定所有结点的状态,然后判断初始状态就行了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<queue> using namespace std; #define FILE "read" int n,cnt[2],a[2][7010],vis[2][7010],ans[2][7010]; queue<int>q; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } int main(){ n=read(); for(int i=0;i<=1;++i){ cnt[i]=read(); for(int j=1;j<=cnt[i];++j) a[i][j]=read(); } q.push(1); q.push(-1); ans[0][1]=ans[1][1]=-1; while(!q.empty()){ int x=q.front(),y=abs(x);q.pop();x=(x<0?0:1); for(int i=1;i<=cnt[x^1];++i){ int z=y-a[x^1][i]; if(z<=0) z+=n; if(ans[x][y]==-1) {if(ans[x^1][z]!=1)ans[x^1][z]=1,q.push(x?-z:z);} else{ if(ans[x^1][z]!=0) continue; vis[x^1][z]++; if(vis[x^1][z]==cnt[x^1]) ans[x^1][z]=-1,q.push(x?-z:z); } } } for(int i=0;i<=1;++i){ for(int j=2;j<=n;++j){ if(ans[i][j]==-1) printf("Lose "); else if(ans[i][j]==0) printf("Loop "); else printf("Win "); } printf("\n"); } return 0; }
|
本文标题:【CF#786A】Berzerk
文章作者:chty
发布时间:2017年03月24日 - 19时30分
最后更新:2018年03月02日 - 18时01分
许可协议:本文为博主原创,未经许可不得转载。