關于sg函數：
———————————————————————
Sprague-Grundy定理（SG定理）：
遊戲和的SG函數等于各個遊戲SG函數的Nim和。這樣就可以将每一個子遊戲分而治之，進而簡化了問題。而Bouton定理就是Sprague-Grundy定理在Nim遊戲中的直接應用，因為單堆的Nim遊戲 SG函數滿足 SG(x) = x。
SG函數：
首先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表示最小的不屬于這個集合的非負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
對于任意狀态 x ， 定義 SG(x) = mex(S),其中 S 是 x 後繼狀态的SG函數值的集合。如 x 有三個後繼狀态分别為 SG(a),SG(b),SG(c)，那麼SG(x) = mex{SG(a),SG(b),SG(c)}。 這樣 集合S 的終态必然是空集，是以SG函數的終态為 SG(x) = 0,當且僅當 x 為必敗點P時。
【執行個體】取石子問題
有1堆n個的石子，每次隻能取{ 1, 3, 4 }個石子，先取完石子者勝利，那麼各個數的SG值為多少？
SG[0]=0，f[]={1,3,4},
x=1 時，可以取走1 - f{1}個石子，剩餘{0}個，是以 SG[1] = mex{ SG[0] }= mex{0} = 1;
x=2 時，可以取走2 - f{1}個石子，剩餘{1}個，是以 SG[2] = mex{ SG[1] }= mex{1} = 0;
x=3 時，可以取走3 - f{1,3}個石子，剩餘{2,0}個，是以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
x=4 時，可以取走4- f{1,3,4}個石子，剩餘{3,1,0}個，是以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
x=5 時，可以取走5 - f{1,3,4}個石子，剩餘{4,2,1}個，是以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
以此類推…..
x 0 1 2 3 4 5 6 7 8….
SG[x] 0 1 0 1 2 3 2 0 1….
———————————————————————–
int sg[N];
bool hash[N];
void sg_solve(int *s,int t,int N) //N求解範圍 S[]數組是可以每次取的值，t是s的長度。
{
int i,j;
memset(sg,0,sizeof(sg));
for(i=1;i<=N;i++)
{
memset(hash,0,sizeof(hash));
for(j=0;j<t;j++)
if(i - s[j] >= 0)
hash[sg[i-s[j]]] = 1;
for(j=0;j<=N;j++)
if(!hash[j])
break;
sg[i] = j;
}
} ————————————————————————–
其他：
ｓｇ函數的值，個人了解是ｉ結點對應的必敗點（錯誤的了解）
經驗證sg函數的最大值和set[]的元素個數密切相關，最大就是n
訓練5題：
lightoj 1296 Again Stone Game
hdu 1848 Fibonacci again and again
hdu 1536 S-Nim
LightOJ 1315 Game of Hyper Knights
lightOJ 1199 Partitioning Game
lightoj 1296 Again Stone Game（sg博弈）
http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1296
大意：n堆石子，每次可以從其中一堆取出１－ｋ個，ｋ是不大于該堆石子個數一半的數字。不能取的人輸。求解兩人博弈結果。
分析：
每一堆石子的個數可達到1e9。計算每一個ｓｇ函數存儲下來肯定不行，所有打表找找ｓｇ結果的規律。
打表sg[i]：
0]=0; sg[1]=0;
for(int i=2;i<=15;i++){
int sta[20],top=0,L=i>>1;
for(int j=1;j<=L;j++){
sta[top++]=sg[i-j];
}
for(int j=0;j<=i;j++) {
bool tag=0;
for(int k=0;k<top;k++) if(j==sta[k]){ tag=1; break; }
if(tag==0) { sg[i]=j; break; }
}
} | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 2 | 1 | 3 | 4 | 2 | 5 | 1 | 6 | 3 | 7 |
可以發現當ｉ是偶數sg[i]=i/2, 當ｉ是奇數時，sg[i]=sg[i/2]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e3+10;
int calc(int n){
if((n&1)==0) return n/2;
return calc(n/2);
}
int main()
{
//freopen("cin.txt","r",stdin);
int t,n,a,ca=1;
cin>>t;
while(t--){
scanf("%d",&n);
int ans=0,a;
for(int i=0;i<n;i++){
scanf("%d",&a);
ans=ans^calc(a);
}
if(ans)printf("Case %d: Alice\n",ca++);
else printf("Case %d: Bob\n",ca++);
}
return 0;
} hdu 1848 Fibonacci again and again（sg）
http://acm.hdu.edu.cn/showproblem.php?pid=1848
大意：3堆石子每次取石子的個數是菲波那切數列元素，最後取完所有石子的人為赢家。
分析：sg函數的簡單應用
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int s[1005],len;
int sg[1005];
bool tag[1005];
void calc_sg(){
int i,j;
s[0]=1; s[1]=2;
for(i=2;i<1005;i++) {
s[i]=s[i-2]+s[i-1];
if(s[i]>1000) { len=i; break; }
}
for(i=1;i<=1000;i++){
memset(tag,0,sizeof(tag));
for(j=0;j<len;j++){
if(i<s[j]) break;
tag[sg[i-s[j]]]=1;
}
for(j=0;j<=1000;j++) if(tag[j]==0) break;
sg[i]=j;
}
}
int main()
{
calc_sg();
int m,n,p;
while(cin>>m>>n>>p){
if(m+n+p==0) break;
int ans=sg[m]^sg[n]^sg[p];
if(ans) puts("Fibo");
else puts("Nacci");
}
return 0;
} hdu 1536 S-Nim (sg)
http://acm.hdu.edu.cn/showproblem.php?pid=1536
背景故事——nim遊戲：
Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows:
The starting position has a number of heaps, all containing some, not necessarily equal, number of beads.
The players take turns chosing a heap and removing a positive number of beads from it.
The first player not able to make a move, loses.
Arthur and Caroll really enjoyed playing this simple game until they recently learned an easy way to always be able to find the best move:
Xor the number of beads in the heaps in the current position (i.e. if we have 2, 4 and 7 the xor-sum will be 1 as 2 xor 4 xor 7 = 1).
If the xor-sum is 0, too bad, you will lose.
Otherwise, move such that the xor-sum becomes 0. This is always possible.
It is quite easy to convince oneself that this works. Consider these facts:
The player that takes the last bead wins.
After the winning player’s last move the xor-sum will be 0.
The xor-sum will change after every move.
現在每一次不能取非0任意數，求解勝利和失敗的情況判别：
标準SG函數的應用。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e4+10;
int s[105];
int sg[N];
bool tag[N];
void calc_sg(int n){
memset(sg,0,sizeof(sg));
int i,j;
for(i=1;i<N;i++){
memset(tag,0,sizeof(tag));
for(j=0;j<n;j++)
if(i-s[j]>=0) tag[sg[i-s[j]]]=1;
for(j=0;j<N;j++)
if(tag[j]==0) break;
sg[i]=j;
}
}
int main()
{
//freopen("cin.txt","r",stdin);
int n;
while(cin>>n&&n){
for(int i=0;i<n;i++){
scanf("%d",&s[i]);
}
calc_sg(n);
int t,m,num,ans;
scanf("%d",&t);
for(int i=0;i<t;i++){
scanf("%d",&m);
ans=0;
for(int j=0;j<m;j++){
scanf("%d",&num);
ans=ans^sg[num];
}
if(ans)printf("%c",'W');
else printf("%c",'L');
}
puts("");
}
return 0;
} LightOJ 1315 Game of Hyper Knights（sg博弈）
http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1315
大意：在如圖的方格中進行兩人博弈，棋子的走法有６種，不能走的人算輸。
分析：遞歸類博弈。我隻能說這題很神奇，我下面的tag數組設成全局的死活過不了，設成局部瞬間過了。因為棋子的走法隻有６種，是以ｓｇ函數隻有６種值0-5
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1005,L=10;
int xx[6]={-2,-3,-2,-1,-1,1};
int yy[6]={1,-1,-1,-2,-3,-2};
int sg[N][N];
bool vis[N][N];
//int sta[L],top;
int calc_sg(int x,int y){
if(vis[x][y]) return sg[x][y];
bool tag[L];
memset(tag,0,sizeof(tag));
for(int i=0;i<L;i++) tag[i]=0;
for(int i=0;i<6;i++){
int tx=x+xx[i];
int ty=y+yy[i];
if(tx>=0 && ty>=0) tag[calc_sg(tx,ty)]=1; //sta[top++]=calc_sg(tx,ty);
}
vis[x][y]=1;
for(int i=0;i<L;i++){
if(tag[i]==0){ sg[x][y]=i; break; }
}
return sg[x][y];
}
int main(){
//freopen("cin.txt","r",stdin);
int t,ca=1;
int n;
cin>>t;
while(t--){
scanf("%d",&n);
int ans=0;
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
ans=ans^calc_sg(a,b);
}
printf("Case %d: ",ca++);
if(ans) puts("Alice");
else puts("Bob");
}
return 0;
} lightOJ 1199 Partitioning Game（sg博弈）
http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1199
大意：給出Ｎ個堆，針對每個堆每一次取１－ｋ，ｋ小于Ｎ的一半，不能取的人失敗。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e4+10;
int sg[N];
bool vis[N];
void init(int n){
sg[1]=sg[2]=0;
sg[3]=1; sg[4]=0;
for(int i=5;i<n;i++){
memset(vis,0,sizeof(vis));
for(int j=1;2*j<i;j++) vis[sg[j]^sg[i-j]]=1;
int j=0;
while(vis[j]) j++; //能有效分割的次數
sg[i]=j;
}
}
int main()
{
//freopen("cin.txt","r",stdin);
init(N);
int t,n,ca=1;
cin>>t;
while(t--){
scanf("%d",&n);
int ans=0,a;
for(int i=0;i<n;i++){
scanf("%d",&a);
ans=ans^sg[a];
}
if(ans) printf("Case %d: Alice\n",ca++);
else printf("Case %d: Bob\n",ca++);
}
return 0;
}