ans[i][j]

i號選手在位置j行動的結果。

預處理，將每位選手能夠直接到達黑洞的點

ans[1][(n-a[1][i]+n) % n] = -1; 表示必贏的點
把這些點加入到隊列，作為BFS的起點
對于必贏點，敵人能夠到達必贏點的點標記ans[敵人][能到該點（必贏）的點]++；
當修改后ans[選手][點]==step_num[本選手] 表示能到的點都是敵人的必贏點，那么本點必輸，加入隊列。
對于必輸點，敵人能夠到達必輸點的點是必贏點，如果沒被加入到隊列，那么敵人必贏點加入隊列，標記為-1；

結果輸出：
==-1必贏
==step_num[本選手] 必輸
其余loop

1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 using namespace std; 8 int a[3][11111]; 9 int ans[3][11111]; 10 struct dd 11 { 12 int id; 13 int b; 14 }; 15 queue <dd> Q; 16 int main() 17 { 18 int n; 19 int s[3]; 20 dd D; 21 cin >> n; 22 cin >> s[0]; 23 24 for (int i = 1; i <= s[0]; i++) 25 scanf("%d", & a[0][i]); 26 cin >> s[1]; 27 for (int i = 1; i <= s[1]; i++) 28 scanf("%d", & a[1][i]); 29 30 memset(ans, 0, sizeof(ans)); 31 for (int i = 1; i <= s[0]; i++) 32 { 33 ans[0][(n - a[0][i] + n) % n] = -1; 34 D.b = 0; 35 D.id = (n - a[0][i] + n) % n; 36 Q.push(D); 37 } 38 for (int i = 1; i <= s[1]; i++) 39 { 40 ans[1][(n - a[1][i] + n) % n] = -1; 41 D.b = 1; 42 D.id = (n - a[1][i] + n) % n; 43 Q.push(D); 44 } 45 while (!Q.empty()) 46 { 47 D = Q.front(); 48 Q.pop(); 49 int b = D.b; 50 int id = D.id; 51 if (ans[b][id] == -1) 52 { 53 for (int i = 1; i <= s[!b] ; i++) 54 { 55 int from = (id - a[!b][i] + n) % n; 56 57 if ((ans[!b][from] != -1) && ans[!b][from] != s[!b]) 58 { 59 ans[!b][from]++; 60 if (ans[!b][from] == s[!b]) 61 { 62 D.b = !b; 63 D.id = from; 64 Q.push(D); 65 } 66 } 67 68 } 69 } 70 else 71 { 72 for (int i = 1; i <= s[!b] ; i++) 73 { 74 int from = (id - a[!b][i] + n) % n; 75 if ((ans[!b][from] != -1) && ans[!b][from] != s[!b]) 76 { 77 D.b = !b; 78 D.id = from; 79 ans[!b][from] = -1; 80 Q.push(D); 81 } 82 } 83 } 84 } 85 for (int i = 1; i < n - 1; i++) 86 if (ans[0][i] == -1) cout << "Win" << " "; 87 else if (ans[0][i] == s[0]) cout << "Lose" << " "; 88 else cout << "Loop" << " "; 89 if (ans[0][n - 1] == -1) cout << "Win" << endl; 90 else if (ans[0][n - 1] == s[0]) cout << "Lose" << endl; 91 else cout << "Loop" << endl; 92 for (int i = 1; i < n - 1; i++) 93 if (ans[1][i] == -1) cout << "Win" << " "; 94 else if (ans[1][i] == s[1]) cout << "Lose" << " "; 95 else cout << "Loop" << " "; 96 if (ans[1][n - 1] == -1) cout << "Win" << endl; 97 else if (ans[1][n - 1] == s[1]) cout << "Lose" << endl; 98 else cout << "Loop" << endl; 99 100 }

?

轉載于:https://www.cnblogs.com/HITLJR/p/6613061.html

總結

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

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