SG函數： 給定一個有向無環圖和一個起始頂點上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進行移動，無法移 動者判負。事實上，這個游戲可以認為是所有Impartial Combinatorial Games的抽象模型。也就是說，任何一個ICG都可以通過把每個局面看成一個頂點，對每個局面和它的子局面連一條有向邊來抽象成這個“有向圖游戲”。下 面我們就在有向無環圖的頂點上定義Sprague-Garundy函數。首先定義mex(minimal excludant)運算，這是施加於一個集合的運算，表示最小的不屬於這個集合的非負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 在我的理解中，sg函數就是一個對有向無環圖dfs的過程，在處理nim博弈時，多個石堆可以看成多個sg函數值的異或。 例題： POJ2311 Cutting Game 典型的sg博弈，找後繼狀態。題意是給出一個n*m的紙片，每次剪成兩部分，誰先剪到1*1就勝利。這就是一個找後繼的題目，每次剪成的兩部分就是前一狀態的後繼，只要將兩個部分的sg值異或起來就是前一狀態的sg值。 [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) #define N 1000000007 using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int sg[201][201]; int dfs(int a,int b)//sg函數的一般寫法 { if(sg[a][b]>=0) { return sg[a][b]; } int i,map[201],r;//map標記數組一定要在dfs內部定義，不然會出現錯誤 mem(map,0); FOR(2,(a/2),i) { r=dfs(i,b)^dfs(a-i,b);//後繼的異或得到前一狀態的sg值 map[r]=1; } FOR(2,(b/2),i) { r=dfs(a,i)^dfs(a,b-i); map[r]=1; } FOR(0,200,i) { if(map[i]==0) { return sg[a][b]=i;//mex公式的應用 } } } int main() { int n,m,sum; mem(sg,-1); while(scanf("%d%d",&n,&m)!=EOF) { sum=dfs(n,m); if(sum>0) { printf("WIN\n"); } else { printf("LOSE\n"); } } return 0; } POJ2425 A Chess Game 題意是給你一個拓撲圖，一個起點上的n個棋子，兩個玩家交替移動棋子，誰無法移動誰輸，典型的sg函數運用。套用模板就行了。此題數據量較大，加入了輸入優化後刷到了第一版第四名，nice! [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) #define N 1000000007 using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int vis[1001][1001],sg[1001]; int n; int dfs(int x)//典型的sg過程 { int i; if(sg[x]!=-1) { return sg[x]; } int f[1001]; mem(f,0); For(0,n,i) { if(vis[x][i]!=-1) { f[dfs(i)]=1; } } i=0; while(f[i]) { i++; } return sg[x]=i; } int main() { int i,j,k,t,x,p,sum; while(scanf("%d",&n)!=EOF) { mem(vis,-1); mem(sg,-1); For(0,n,i) { RD(k); if(k==0) { sg[i]=0; } For(0,k,j) { RD(t); vis[i][t]=1;//建圖 } } while(1) { RD(x); if(x==0) { break; } sum=0; For(0,x,i) { RD(p); sum^=dfs(p); } if(sum!=0) { printf("WIN\n"); } else { printf("LOSE\n"); } } } return 0; } POJ2068 Nim 題意是圓桌上有2n個人，奇數一隊，偶數一隊，每個人都有一個拿走棋子的最高限額，問你最後1對能否獲勝。 還是用強大的sg函數過的，記錄下每個狀態的sg。 [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #include <queue> #include<map> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int n,s,m[22],sg[22][8200],sum; int dfs(int x,int y) { if(sg[x][y]!=-1) { return sg[x][y]; } int i,j; FOR(1,m[x],i) { if(y-i<0) { break; } if(x+1>=2*n) { j=0; } else { j=x+1; } if(dfs(j,y-i)==0) { return sg[x][y]=1; } } return sg[x][y]=0; } int main() { int i; while(1) { RD(n); if(n==0) { break; } RD(s); For(0,2*n,i) { RD(m[i]); } mem(sg,-1); FOR(0,2*n,i) { sg[i][0]=1; } sum=dfs(0,s); if(sum==0) { printf("0\n"); } else { printf("1\n"); } } return 0; } POJ3537 Crosses and Crosses 題意：給出一個1*n的矩形，上面有n個方格，現有兩人分別在上面畫×，誰先能畫出三個×相連就贏了。這就是一個sg函數的母問題轉化為子問題的題目，由於在第x位置畫了×後，則就轉變成(x-3)個格子畫×和(n-x-2)個格子畫×。。。這就能不斷的分解下去，最後將所有sg值異或起來就是正解了。 [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #include <queue> #include<map> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int sg[2001]; int dfs(int x) { if(x<0) { return 0; } if(sg[x]>=0) { return sg[x]; } int i,y; bool v[2001]={false}; FOR(1,x,i) { y=dfs(i-3)^dfs(x-i-2);//找後繼（經典） v[y]=true; } for(i=0;;i++) { if(v[i]==false) { return sg[x]=i; } } } int main() { int n,sum; mem(sg,-1); while(scanf("%d",&n)!=EOF) { sum=dfs(n); if(sum) { printf("1\n"); } else { printf("2\n"); } } return 0; } POJ2599 A funny game 記憶化搜索，這題的博弈味道不濃，更多的是搜索。題意是給一個圖，兩人輪流移動，走過的節點不能再走。水題，dfs+標記就行。 [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<vector> #include<stack> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<=b;++i) #define For(a,b,i) for(i=a;i<b;++i) #define N 1000000007 using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int n,v[1001][1001],vis[1001]; int dfs(int x) { int i; FOR(1,n,i) { vis[x]=1; if(v[i][x]&&!vis[i]) { if(!dfs(i)) { vis[x]=0; return i; } } vis[x]=0; } return 0; } int main() { int m,i,a,b; while(scanf("%d%d",&n,&m)!=EOF) { mem(v,0); mem(vis,0); FOR(1,n-1,i) { RD(a); RD(b); v[a][b]=v[b][a]=1; } i=dfs(m); if(i!=0) { printf("First player wins flying to airport %d\n",i); } else { printf("First player loses\n"); } } return 0; }
