?

【題目鏈接】?http://codeforces.com/problemset/problem/786/A

?

【題目大意】

　　有兩個人，每個人有一個數集，里面有一些數，現在有一個環，有個棋子放在1，
　　有個不確定位置的終點，兩個人輪流從自己的數集中選擇一個數，作為這個棋子移動的步數
　　問終點在不同位置，不同人先手的時候誰能贏，或者游戲陷入循環

?

【題解】　

　　我們從st_0_0=st_1_0=0開始倒著推導，
　　如果一個狀態是必敗態，那么它的前繼節點一定是必勝態
　　如果一個點的所有后繼都是必勝態，那么這個節點一定是必敗態。
　　每當一個點被其必勝后繼推導到，那么其度數減一，當度數為0時則表示其為必敗態
　　我們根據這些結論倒著推導每個狀態的答案并記錄，最后按順序輸出即可。

?

?

【代碼】

#include <cstdio> #include <vector> #include <cstring> #include <string> using namespace std; const int N=100010; int n,sg[2][N],d[2][N],k,x; vector<int> g[2]; int dfs(int k,int pos,int v){int &ret=sg[k][pos];if(~ret)return ret;ret=v;if(v==0){for(int i=0;i<g[k^1].size();i++){int x=g[k^1][i];int j=(pos+n-x)%n;if(j==0)continue;dfs(k^1,j,1);}}else{for(int i=0;i<g[k^1].size();i++){int x=g[k^1][i];int j=(pos+n-x)%n;if(j==0)continue;if(--d[k^1][j]==0)dfs(k^1,j,0);}}return ret; } int main(){scanf("%d",&n);for(int i=0;i<2;i++){scanf("%d",&k);g[i].clear();while(k--){scanf("%d",&x);g[i].push_back(x);}for(int j=1;j<n;j++)d[i][j]=g[i].size();}memset(sg,-1,sizeof(sg));dfs(0,0,0);dfs(1,0,0);string s[3]={"Loop","Lose","Win"};for(int k=0;k<2;k++){for(int i=1;i<n;i++){printf("%s%c",s[sg[k][i]+1].c_str(),i+1==n?'\n':' ');}}return 0; }

轉載于:https://www.cnblogs.com/forever97/p/codeforces786a.html

總結

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

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