相當經典的一題SG value
難點在於看出此題每個格子是獨立的遊戲,這需要透過模型轉換和數學歸納法證明。
不妨先接受這個結論,那麼我們變成要求每個是'1'的格子的SG value的XOR,怎麼求呢?
注意到N,M都<=50,那麼最多就只有N*M個格子,每個格子最多有N*M個轉移,所以如果直接用定義去計算SG value的話也只需要O(N^2*M^2),時間上是可以忍受的。
最後一個細節是如何輸出先手的第一步,這可以在計算SG時同步完成,但是我採用的懶人方法就是在要輸出的時候重新枚舉一次,反正複雜度還是O(N^2*M^2)~~輕鬆過~~
yee~~
#include<bits/stdc++.h> using namespace std; const int maxn=50+5; const int maxm=50+5; int SG[maxn][maxm]; int getSG(int i,int j) { if(i==0 || j==0) return 0; if(SG[i][j]!=-1) return SG[i][j]; set<int> S; for(int ip=0;ip<i;ip++) for(int jp=0;jp<j;jp++) S.insert(getSG(i,jp)^getSG(ip,j)^getSG(ip,jp)); for(int ans=0;;ans++) if(!S.count(ans)) return SG[i][j]=ans; } char s[maxn][maxm]; int main() { freopen("coins.in","r",stdin); freopen("coins.out","w",stdout); memset(SG,-1,sizeof SG); // for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) printf("SG[%d][%d]:%d\n",i,j,getSG(i,j)); int N,M,SGall=0; scanf("%d%d",&N,&M); for(int i=1;i<=N;i++) { scanf("%s",&s[i][1]); for(int j=1;j<=M;j++) if(s[i][j]=='1') SGall^=getSG(i,j); } // printf("SGall=%d\n",SGall); printf("%s\n",SGall!=0?"Ann":"Betty"); if(SGall) for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(s[i][j]=='1') for(int ip=0;ip<i;ip++) for(int jp=0;jp<j;jp++) if((SGall^getSG(i,j)^getSG(i,jp)^getSG(ip,j)^getSG(ip,jp))==0) {printf("%d %d\n%d %d\n",i,j,ip,jp);return 0;} }
沒有留言:
張貼留言