博弈论一点点

基本就是把这里的题过了一遍

SG函数资料（入门必备）

感觉很不错的文章

博弈论（一）：Nim游戏

博弈论（二）：Sprague-Grundy函数

寻找必败态——一类博弈问题的快速解法

练手

hdu1846

#include
using namespace std;
int main(){int T,n,m;scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);if (n<=m)puts("first");//多余的一行 else puts((n%(m+1))?"first":"second");}return 0;
} 

hdu2147

#include
using namespace std;int main(){int n,m;while (scanf("%d%d",&n,&m)==2&&n&&m){puts((n&m&1)?"What a pity!":"Wonderful!");}return 0;
}

hdu2188

#include
using namespace std;
int main(){int T,n,m;scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);puts((n%(m+1))?"Grass":"Rabbit");}return 0;
} 

hdu2148

PN似乎反过来了。。。。找规律

#include
using namespace std;
int main(){int n,m;while (scanf("%d%d",&m,&n)==2){if (n>=m){for (int i=m;iprintf("%d ",i);printf("%d
",n);}else {int x=m%(n+1);if (x)printf("%d
",x);else puts("none");}}return 0;
} 

Nim游戏

对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示异或(xor)运算。

先记个结论（坑以后再填）

ｈｄｕ１９０７

#include
using namespace std;
int main(){int T,n,x;scanf("%d",&T);while (T--){scanf("%d",&n);int ans=0,cnt=0;for (int i=1;i<=n;i++){scanf("%d",&x);ans ^= x;if (x>1)cnt++;}if (!cnt)ans = !(n&1);if (ans)puts("John");else puts("Brother");}return 0;
} 

ｈｄｕ２５０９

#include
#include
using namespace std; int main(){int n,x;while (scanf("%d",&n)==1){int ans=0,cnt=0;for (;n--;){scanf("%d",&x);ans ^= x;if (x>1) cnt++;}if (!cnt)ans = !!(n&1);//这个时候n都=0了，前面循环应该for个i，这里能过是因为数据弱吧 if (ans)puts("Yes");else puts("No");}return 0;
}

hdu1527

威佐夫博弈

#include
#include
#include
using namespace std;
const double phi=(1+sqrt(5))/2.0;
int main(){int m,n;while (scanf("%d%d",&n,&m)==2){if (min(n,m)==(int)(phi*abs(n-m)))puts("0");else puts("1");}return 0;
} 

继续练手

hdu1847

#include
using namespace std;
int main(){int n;while (scanf("%d",&n)==1){if (n%3==0)puts("Cici");else puts("Kiki");}return 0;
}

hdu1849

#include
using namespace std;
int main(){int n,x;while (scanf("%d",&n)==1&&n){int ans=0;for (;n--;){scanf("%d",&x);ans ^= x;}puts(ans?"Rabbit Win!":"Grass Win!");}return 0;
} 

hdu1850

#include
using namespace std;
const int N=111;
int a[N];
int main(){int n;while (~scanf("%d",&n)&&n){int nim=0;for (int i=1;i<=n;i++){scanf("%d",&a[i]);nim ^= a[i];}if (!nim)puts("0");else {int cnt=0;for (int i=1;i<=n;i++){int kk = nim^a[i];if (a[i]>kk)cnt++;}printf("%d
",cnt);}}return 0;
} 

SG函数模板

理论详细解释

hdu1848

#include
#include
using namespace std;
const int N = 1007;
int sg[N],fib[N];void getFib(){fib[1] = 1 , fib[2] = 2;for (int i=3;i<=17;i++)fib[i]=fib[i-1]+fib[i-2];
}void getSG(){getFib();/*memset(sg,0,sizeof(sg));int lastP;for (int i = 0; i < N ; i++ ){if (sg[i]==-1) sg[i] = i-lastP;else {//sg[i]==0lastP = i ;for (int j=1;j<17&&i+fib[j]int j;sg[0]=0;bool mex[17];for(int i=1;imemset(mex,0,sizeof(mex));for (j=1 ;fib[j]<=i ;j++ )mex[sg[i-fib[j]]]=1;for (j=0 ; jif(!mex[j])break;sg[i] = j;}}
//by cww97
int main(){int x,y,z;getSG();while (scanf("%d%d%d",&x,&y,&z)==3){if ( !x&& !y&& !z ) break;int ans = sg[x]^sg[y]^sg[z];if (ans)puts("Fibo");else puts("Nacci");}return 0;
} 

hdu1536

再次上演悲剧，调试N弄成了15，然后RTE，然后设成了10W（题目上数字看错了），然后TLE，然后，，，，好气啊

#include
#include
#include
using namespace std;
const int N=10007;
int s[110],sg[N],k;void getSG(){sg[0]=0;bool vis[N];for (int i=1;imemset(vis,0,sizeof(vis));for (int j=1;s[j]<=i&&j<=k;j++)vis[sg[i-s[j]]]=1;for (int j=0;jif(!vis[j]){sg[i]=j;break;}}
}int main(){//freopen("fuck.in","r",stdin);int m,n,x;while (scanf("%d",&k)==1&&k){for (int i=1;i<=k;i++)scanf("%d",&s[i]);sort(s+1,s+k+1);getSG();scanf("%d",&n);while (n--){scanf("%d",&m);int ans=0;while (m--){scanf("%d",&x);ans ^= sg[x];}putchar(ans?'W':'L');}puts("");}return 0;
} 

hdu5724

第一次多校训练的题，，就是这题引出了这一整篇文fei章hua

学(zhuang)术(bi)一点的说法是，状态压缩+SG

先说状态压缩

简单点的话，一行一行处理，第i个格子有棋子就 +1<< i(2的i次方) ,最后得到一个数字表示这一行的一种状态，个人习惯从1开始数，，，于是1<<0=1遍没有意义，导致我的表只有偶数（一半是空的，为了个人的强迫症强行多开了一倍空间，不过我喜欢，嘻嘻），所以所有状态的最小值是0（没有棋子），最大是（1<<21-2）（所有格子都有棋子，等比数列求个和就行）。

SG嘛，对棋盘的每个状态求sg值，注意所有棋子集中在右边的时候是没法走的（sg=0），所以从大到小求，，，状态变化，我一开始写的加减号，然后看有人用的位运算，以为自己错了，改成位运算的样子，A了之后又感觉自己想法不错，改回加减号，果然还是A了，，当然，感觉用位运算更易于理(zhuang)解(bi)一点，这里贴的代码就是位运算版本的辣（mdzz，一个符号讲这么多废话）

#include
#include
using namespace std;
const int N=(1<<21)+7;
int sg[N];
int c[23],C;//the position of chessesint next(int x){ //move the x-th chess for (int i=x;i<=C;i++){if (c[i+1]>c[i]+1)return 1<<(c[i]+1);}return 0;
}void getSG(){bool vis[107];// enough??for (int i=N-9;i>=0;i-=2){ //downtoC=0;           //get the stituationfor (int j=1;j<=20;j++)//num->arrayif (i&(1<1]=21;memset(vis,0,sizeof(vis));//sgsgsgfor (int j=1;j<=C;j++){int nxt=next(j);//move a chessif (nxt)vis[sg[i^(1<1;//- +}for (int j=0;j<107;j++)if(!vis[j]){sg[i]=j;break;}}
}int main(){//freopen("fuck.in","r",stdin);int T,n,m,x;getSG();scanf("%d",&T);while (T--){int ans = 0;scanf("%d",&n);for (;n--;){int che = 0;scanf("%d",&m);for (;m--;){scanf("%d",&x);che |= 1<//+=}ans ^= sg[che];}if (ans)puts("YES");else puts("NO");}return 0;
}