題目鏈接：http://codeforces.com/problemset/problem/786/A

---

這個題出做$DIV2$的$C$以及$DIV1$的A會不會難了一點啊...

?

做法和題解并不一樣，只是很懂題解中記憶化搜索的時候怎么判斷的$LOOP$

我們都知道組合游戲中一個狀態(tài)所有的后繼如果都是贏的那么這個狀態(tài)是輸?shù)?#xff0c;一個狀態(tài)只要有一個后繼是輸?shù)哪敲催@個狀態(tài)就是贏的。

但是這個題目中有$LOOP$的情況，考慮將一個點拆為兩個，分別表示第一個人和第二個人在這個點是必勝還是必敗(也就是答案)，如果判斷不出來就是$LOOP$

因為$LOOP$不好處理，所以考慮不是記憶化$DFS$,而是按照反向邊逆向遞推，這個遞推過程滿足拓撲序就可以了。

---

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 #include<queue> 9 using namespace std; 10 #define maxn 7010 11 #define llg long long 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,ans[2][maxn],N1,N2,a[maxn],b[maxn],se[2][maxn],du[2][maxn]; 14 15 struct node 16 { 17 llg v1,v2; 18 }f[2][maxn]; 19 20 struct data 21 { 22 llg x,y; 23 }; 24 25 queue<data>dl; 26 27 inline int getint() 28 { 29 int w=0,q=0; char c=getchar(); 30 while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 31 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; 32 } 33 void work() 34 { 35 ans[0][1]=ans[1][1]=2; 36 data w; 37 w.x=0,w.y=1; 38 dl.push(w); w.x=1; 39 dl.push(w); 40 while (!dl.empty()) 41 { 42 w=dl.front(); dl.pop(); 43 llg x=w.x,y=w.y; 44 if (!x) 45 { 46 for (llg i=1;i<=N2;i++) 47 { 48 llg wz=(y-b[i]+n-1)%n+1; 49 du[1][wz]--; 50 if (ans[1][wz]) continue; 51 if (ans[x][y]==2) 52 { 53 ans[1][wz]=1; 54 data nw; nw.x=1,nw.y=wz; 55 dl.push(nw); 56 du[1][wz]=-1; 57 } 58 if (du[1][wz]==0) 59 { 60 ans[1][wz]=2; 61 data nw; nw.x=1,nw.y=wz; 62 dl.push(nw); 63 du[1][wz]=-1; 64 } 65 } 66 } 67 else 68 { 69 for (llg i=1;i<=N1;i++) 70 { 71 llg wz=(y-a[i]+n-1)%n+1; 72 du[0][wz]--; 73 if (ans[0][wz]) continue; 74 if (ans[x][y]==2) 75 { 76 ans[0][wz]=1; 77 data nw; nw.x=0,nw.y=wz; 78 dl.push(nw); 79 du[0][wz]=-1; 80 } 81 if (du[0][wz]==0) 82 { 83 ans[0][wz]=2; 84 data nw; nw.x=0,nw.y=wz; 85 dl.push(nw); 86 du[0][wz]=-1; 87 } 88 } 89 } 90 } 91 } 92 93 int main() 94 { 95 yyj("C"); 96 cin>>n; 97 cin>>N1; 98 for (llg i=1;i<=N1;i++) a[i]=getint(); 99 cin>>N2; 100 for (llg i=1;i<=N2;i++) b[i]=getint(); 101 102 for (llg i=1;i<=n;i++) 103 { 104 du[0][i]=N1,du[1][i]=N2; 105 } 106 107 work(); 108 for (llg i=2;i<=n;i++) 109 { 110 if (ans[0][i]==1) printf("Win "); 111 if (ans[0][i]==2) printf("Lose "); 112 if (ans[0][i]==0) printf("Loop "); 113 } 114 printf("\n"); 115 for (llg i=2;i<=n;i++) 116 { 117 if (ans[1][i]==1) printf("Win "); 118 if (ans[1][i]==2) printf("Lose "); 119 if (ans[1][i]==0) printf("Loop "); 120 } 121 return 0; 122 }

?

轉載于:https://www.cnblogs.com/Dragon-Light/p/6609684.html

總結

以上是生活随笔為你收集整理的Codeforces 786 A. Berzerk的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。