（一）巴什博弈
只有一堆n個(gè)物品，兩個(gè)人輪流從這堆物品中取物狼纬，規(guī)定每次至少取一個(gè)羹呵，最多取m個(gè)。最后取光者得勝疗琉。顯然冈欢，如果n=m+1，那么由于一次最多只能取m個(gè)没炒，所以涛癌，無論先取者拿走多少個(gè)，
后取者都能夠一次拿走剩余的物品送火，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：如n=（m+1）r+s先匪，（r為任意自然數(shù)种吸，s≤m),那么先取者要拿走s個(gè)物品，如果后取者拿走k（≤m)個(gè)呀非，那么先者再拿走m+1-k個(gè)坚俗，結(jié)果剩下（m+1）（r-1）個(gè)镜盯，以后保持這樣的取法，那么先取者肯定獲勝猖败∷倮拢總之，要保持給對手留下（m+1）的倍數(shù)恩闻，就能最后獲勝艺糜。
這個(gè)游戲還可以有一種變相的玩法：兩個(gè)人輪流報(bào)數(shù)，每次至少報(bào)一個(gè)幢尚，最多報(bào)十個(gè)破停，誰能報(bào)到100者勝。##
#include <cstdio>
int main()
{
int t;
scanf("%d",&t);
int n,m;
while(t--)
{
scanf("%d%d",&n,&m);
if(n%(m+1)) printf("Win\n");
else printf("Lose\n");
}
}
#include <cstdio>
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)!=EOF)
{
if(m>n)//這種情況先手非必?cái)〉脑捴挥幸环N出法
{
if(m%(n+1)) printf("%d\n",m%(n+1));
else printf("none\n");
}
if(n>=m)//這種情況只需輸出大于等于m的就行
{
for(int i=m;i<n;i++)
printf("%d ",i);
printf("%d\n",n);
}
}
return 0;
}
SG Version
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
int fx[1010],g[1010];;
int n,m;
void getSG()
{
memset(fx,0,sizeof(fx));
fx[0]=0;//面對局面0,說明自己沒法取,所以局面0的結(jié)果是輸
for(int i=1;i<=m;i++)//枚舉每個(gè)局面i
{
memset(g,0,sizeof(g));
for(int j=1;j<=n;j++)//分解i局面,枚舉局面i產(chǎn)生的下一個(gè)局面,其中限制最多取n個(gè),最少取1個(gè)
{
if(i>=j) g[fx[i-j]]=1;
else break;//已經(jīng)沒法取了
}
for(int j=0;j<=m;j++)//這里必須從0開始遍歷
if(!g[j])
{
fx[i]=j;
break;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
getSG();
if(m>n)//這種情況先手非必?cái)〉脑捴挥幸环N出法
{
if(fx[m]) printf("%d\n",fx[m]);
else printf("none\n");
}
if(n>=m)//這種情況只需輸出大于等于m的就行
{
for(int i=m;i<n;i++)
printf("%d ",i);
printf("%d\n",n);
}
}
return 0;
}
Good Luck in CET-4 Everybody!
題意:
1尉剩、 總共n張牌;
2真慢、 雙方輪流抓牌；
3理茎、 每人每次抓牌的個(gè)數(shù)只能是2的冪次（即：1黑界，2，4皂林，8朗鸠，16…）
4、 抓完牌式撼，勝負(fù)結(jié)果也出來了：最后抓完牌的人為勝者童社；
每次都是Kiki先抓牌，請問誰能贏呢著隆？
題解一：
(1)扰楼、若是留給Cici的是3，那么Cici只能取1個(gè)或2個(gè)美浦，所以再輪到Kiki取的話必贏弦赖。
(2)、若是給Cici留下的是3的倍數(shù)浦辨，假設(shè)為3n(n=1,2,3,..)蹬竖，那么無論Cici取什么數(shù)，剩余的數(shù)一定可以寫成3m+1或者3m+2(m<n)的形式流酬，那么只要Kiki再取的時(shí)候留給Cici的仍然是3的倍數(shù)的話币厕，就必勝了。
#include <cstdio>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n%3) printf("Kiki\n");
else printf("Cici\n");
}
return 0;
}
題解二:
SG ( 嵌套循環(huán) )
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN=1010;
int fx[MAXN],g[MAXN];
int pow_2[15];
void getSG()
{
fx[0]=0;
for(int i=1;i<MAXN;i++)//枚舉每個(gè)局面i
{
memset(g,0,sizeof(g));
for(int j=0;j<25;j++)//枚舉的局面i的分解區(qū)間
{
if(i-pow_2[j]>=0)
{
g[fx[i-pow_2[j]]]=1;
}
else break;
}
for(int j=0;j<MAXN;j++)
{
if(!g[j])
{
fx[i]=j;
break;
}
}
}
}
int main()
{
pow_2[0]=1;
for(int i=1;i<15;i++) pow_2[i]=pow_2[i-1]<<1;
getSG();
int n;
while(scanf("%d",&n)!=EOF)
{
if(fx[n]) printf("Kiki\n");
else printf("Cici\n");
}
}
題解三:
SG (記憶化搜索)
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN=1010;
int fx[MAXN],g[MAXN];
int pow_2[15];
int getSG(int n)
{
if(fx[n]!=-1) return fx[n];
int g[MAXN];
memset(g,0,sizeof(g));
for(int j=0;j<25;j++)
{
if(n-pow_2[j]>=0)
{
getSG(n-pow_2[j]);
g[fx[n-pow_2[j]]]=1;
}
else break;
}
for(int j=0;;j++)
{
if(!g[j])
{
fx[n]=j;
break;
}
}
return fx[n];
}
int main()
{
pow_2[0]=1;
for(int i=1;i<15;i++) pow_2[i]=pow_2[i-1]<<1;
memset(fx,-1,sizeof(fx));
fx[0]=0;//初始化
int n;
while(scanf("%d",&n)!=EOF)
{
if(getSG(n)) printf("Kiki\n");
else printf("Cici\n");
}
}
題解四:
#include<cstdio>
int main()
{
int n;
while(~scanf("%d",&n))
{
n%=(2+1);
if(n==0) printf("Cici\n");//n=(b+1)*r,先手必輸
else if(n==2) printf("Kiki\n");//n=b,先手一次性拿走b芽腾，先手贏
else if(n&1) printf("Kiki\n");//n<b;則先手和后手每次只能拿走1
//( 因?yàn)閎^0=1 )旦装，如果是奇數(shù)，則先手贏摊滔；反之阴绢，后手贏店乐。
else printf("Cici\n");
}
return 0;
}
https://scut.online/problem.php?id=93
題目描述
大家都知道小林桑和托爾的相遇其實(shí)是假酒造成的，在喝多了酒之后呻袭，小林桑不僅會(huì)說女仆的話題眨八，作為一個(gè)程序員碼農(nóng)她也會(huì)和別人玩數(shù)字有關(guān)的游戲，這次她和托爾玩的是這個(gè)游戲：首先我們提出兩個(gè)整數(shù)B,N (1 <=B,N <=109),從小林桑開始左电，兩個(gè)人輪流進(jìn)行操作廉侧，操作的內(nèi)容是：選取一個(gè)冪指數(shù)k(k≥0)，使得Bk <= N券腔，然后令N = N - B^k伏穆。如果輪到一個(gè)人的時(shí)候沒有可以選的冪指數(shù)kk了，這個(gè)人就輸了纷纫。給出B,N枕扫，你能預(yù)測出游戲的最終結(jié)果嗎？
輸入格式
在單個(gè)文件包含多組數(shù)據(jù)辱魁，請循環(huán)讀取至末尾烟瞧。對于每組數(shù)據(jù)，包含了兩個(gè)整數(shù)B,N染簇，以空格分割参滴，獨(dú)占一行。
輸出格式
若小林桑獲勝锻弓，輸出"kobayashisan no kachi"砾赔，獨(dú)占一行。若托爾獲勝青灼，輸出"tohru no kachi"暴心，獨(dú)占一行。
樣例數(shù)據(jù)
輸入
2 37 3
輸出
tohru no kachi
kobayashisan no kachi
#include <bits/stdc++.h>
using namespace std;
int T,n,b;
int main()
{
while(scanf("%d%d",&b,&n)!=EOF)
{
n%=(b+1);
if(n==0) printf("tohru no kachi\n");//n=(b+1)*r,先手必輸
else if(n==b) printf("kobayashisan no kachi\n");//n=b,先手一次性拿走b杂拨，先手贏
else if(n&1) printf("kobayashisan no kachi\n");//n<b;則先手和后手每次只能拿走1
//( 因?yàn)閎^0=1 )专普，如果是奇數(shù)，則先手贏弹沽；反之檀夹，后手贏。
else printf("tohru no kachi\n");
}
}
邂逅明下
題意:三個(gè)數(shù)字n策橘，p炸渡，q，表示一堆硬幣一共有n枚丽已，從這個(gè)硬幣堆里取硬幣偶摔，一次最少取p枚，最多q枚促脉，如果剩下少于p枚就要一次取完辰斋。兩人輪流取，直到堆里的硬幣取完瘸味，最后一次取硬幣的算輸宫仗。對于每一行的三個(gè)數(shù)字，給出先取的人是否有必勝策略旁仿，如果有回答WIN藕夫，否則回答LOST。
題解:
若當(dāng)前石子共有n =（p+q）* r個(gè)枯冈，則A必勝毅贮，必勝策略為：A第一次取q個(gè)，以后每次若B取K個(gè)尘奏，A忍踩臁（p+q-k）個(gè)，如此下去最后必剩下p個(gè)給B炫加，所以A必勝瑰煎。
若n =（p+q）* r + left個(gè)（1< left <= p）B必勝，必勝策略為：每次取石子活動(dòng)中俗孝，若A取k個(gè)酒甸，則B去（p+q-k）個(gè)，那么最后剩下left個(gè)給A赋铝，此時(shí)left <= p插勤，所以A只能一次去完市怎，B勝舅世。
若n =（p+q）* r + left個(gè)（p < left <= q），則A必勝玷过，必勝策略為：A第一次取t（1<left – t <= p）個(gè)苛蒲，以后每次B取k個(gè)卤橄，則A取（p+q-k）個(gè)臂外，那么最后留下1< left – t <=p給B窟扑，則A勝。
#include<cstdio>
int main()
{
int n,p,q;
while(~scanf("%d%d%d",&n,&p,&q))
{
n%=(p+q);
if(n==0||n>p) printf("WIN\n");
else printf("LOST\n");
}
return 0;
}
另外,可以通過觀察SG函數(shù)得出結(jié)果
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN=65540;
int fx[MAXN],g[MAXN];
int n,p,q;
void getSG()
{
fx[0]=1;//面對局面0,說明已經(jīng)贏了
for(int i=1;i<p;i++) fx[i]=0;//小于p個(gè),必須自己取完,先手輸
for(int i=p;i<=n;i++)
{
memset(g,0,sizeof(g));
for(int j=p;j<=q;j++)
{
if(i-j>=0)
{
g[fx[i-j]]=1;
}
}
for(int j=0;j<=n;j++)
{
if(!g[j])
{
fx[i]=j;
break;
}
}
}
for(int i=0;i<=n;i++)//打印結(jié)果
{
if(fx[i]==0) printf("%d %d\n",i,fx[i]);
}
}
int main()
{
while(scanf("%d%d%d",&n,&p,&q)!=EOF)
{
getSG();
if(fx[n]) printf("WIN\n");
else printf("LOST\n");
}
}
（二 ）威佐夫博奕（Wythoff Game）：有兩堆各若干個(gè)物品漏健，兩個(gè)人輪流從某一堆或同
時(shí)從兩堆中取同樣多的物品嚎货，規(guī)定每次至少取一個(gè)，多者不限蔫浆，最后取光者得勝殖属。
我們用（ak，bk）（ak ≤ bk ,k=0瓦盛，1洗显，2外潜，…,n)表示兩堆物品的數(shù)量并稱其為局勢，如果甲面對（0挠唆，0）处窥，那么甲已經(jīng)輸了，這種局勢我們稱為奇異局勢玄组。前幾個(gè)奇異局勢是：（0滔驾，0）、（1俄讹，2）哆致、（3，5）患膛、（4摊阀，7）、（6剩瓶，10）驹溃、（8，13）延曙、（9豌鹤，15）、（11枝缔，18）（12布疙，20）
可以看出,a0=b0=0,ak是未在前面出現(xiàn)過的最小自然數(shù),而 bk= ak + k，奇異局勢有
如下三條性質(zhì)：
1愿卸。任何自然數(shù)都包含在一個(gè)且僅有一個(gè)奇異局勢中灵临。
由于ak是未在前面出現(xiàn)過的最小自然數(shù)，所以有ak > ak-1 趴荸，而 bk= ak + k > ak-1 + k-1 =
bk-1 > ak-1 儒溉。所以性質(zhì)1成立。
2发钝。任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨?br>
事實(shí)上顿涣，若只改變奇異局勢（ak，bk）的某一個(gè)分量酝豪，那么另一個(gè)分量不可能在其他奇異局勢中涛碑，所以必然是非奇異局勢。如果使（ak孵淘，bk）的兩個(gè)分量同時(shí)減少蒲障，則由于其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢揉阎。
3庄撮。采用適當(dāng)?shù)姆椒ǎ梢詫⒎瞧娈惥謩葑優(yōu)槠娈惥謩荨?br>
假設(shè)面對的局勢是（a,b）余黎，若 b = a重窟，則同時(shí)從兩堆中取走 a 個(gè)物體，就變?yōu)榱似娈惥謩荩?惧财，0）；如果a = ak 扭仁，b > bk垮衷，那么，取走b – bk個(gè)物體乖坠，即變?yōu)槠娈惥謩莶笸唬蝗绻鸻 = ak ， b < bk ,則同時(shí)從兩堆中拿走 ak – ab – ak個(gè)物體,變?yōu)槠娈惥謩荩?ab – ak , ab – ak+ b – ak）熊泵；如果a > ak 仰迁，b= ak + k,則從第一堆中拿走多余的數(shù)量a – ak 即可；如果a < ak 顽分，b= ak + k,分兩種情況徐许，第一種，a=aj （j < k）,從第二堆里面拿走 b – bj 即可卒蘸；第二種雌隅，a=bj （j < k）,第二堆里面拿走 b – aj 即可。 從如上性質(zhì)可知缸沃，兩個(gè)人如果都采用正確操作恰起，那么面對非奇異局勢，先拿者必勝趾牧；反之检盼，則后拿者取勝。
那么任給一個(gè)局勢（a翘单，b）吨枉，怎樣判斷它是不是奇異局勢呢？我們有如下公式：
ak =[k（1+√5）/2]县恕，bk= ak + k （k=0东羹，1，2忠烛，…,n 方括號表示取整函數(shù))
奇妙的是其中出現(xiàn)了黃金分割數(shù)（1+√5）/2 = 1属提。618…,因此,由ak，bk組成的矩形近似為黃金矩形，由于2/（1+√5）=（√5-1）/2冤议，可以先求出j=[a（√5-1）/2]斟薇，若a=[j（1+√5）/2]，那么a = aj恕酸，bj = aj + j堪滨，若不等于，那么a = aj+1蕊温，bj+1 = aj+1+ j + 1袱箱，若都不是，那么就不是奇異局勢义矛。然后再按照上述法則進(jìn)行发笔，一定會(huì)遇到奇異局勢。
https://vjudge.net/problem/HDU-1527
#include <cstdio>
#include<algorithm>
using namespace std;
int main()
{
int a,b,k;
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a>b) swap(a,b);
k=b-a;
b=(int)(k*(1+sqrt(5))/2.0);
if(a==b) printf("0\n");
else printf("1\n");
}
}
題意：在威佐夫博奕的基礎(chǔ)上新增加了一條要求：就是如果在贏得條件下凉翻，輸出第一步怎么走了讨。如果在任意的一堆中取走石子能勝同時(shí)在兩堆中同時(shí)取走相同數(shù)量的石子也能勝，先輸出取走相同數(shù)量的石子的情況制轰。
https://vjudge.net/problem/HDU-2177
#include <cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double val=(1+sqrt(5))/2.0;
int main()
{
int a,b,k,ak,bk,x,y;
while(scanf("%d%d",&a,&b)!=EOF,a+b)
{
if(a>b) swap(a,b);
k=b-a;
ak=(int)(k*val);
bk=ak+k;
if(a==ak) printf("0\n");
else
{
printf("1\n");
if(abs(a-ak)==abs(b-bk)&&a>ak)
{
printf("%d %d\n",ak,bk);
}
for(int i=b-1;i>=0;i--)
{
int x=a,y=i;
if(x>y) swap(x,y);
int num=y-x;
if((int)(num*val)==x)
printf("%d %d\n",x,y);
}
}
}
}
（三 ） 尼姆博奕（Nimm Game）：有三堆各若干個(gè)物品前计，兩個(gè)人輪流從某一堆取任意多的
物品，規(guī)定每次至少取一個(gè)垃杖，多者不限男杈，最后取光者得勝。我們用（a缩滨，b势就，c）表示某種局勢，首先（0脉漏，0苞冯，0）顯然是奇異局勢，無論誰面對奇異局勢侧巨，都必然失敗舅锄。第二種奇異局勢（0，n司忱，n）皇忿，只要與對手拿走一樣多的物品，最后都將導(dǎo)致（0坦仍，0鳍烁，0）。 任何奇異局勢（a繁扎，b幔荒，c）都有a（xor）b（xor）c =0糊闽。
題目1：
今有若干堆火柴，兩人依次從中拿取爹梁，規(guī)定每次只能從一堆中取若干根右犹，
可將一堆全取走，但不可不取姚垃，最后取完者為勝念链，求先手勝負(fù)。
題解：設(shè)ans為所有數(shù)據(jù)的xor運(yùn)算积糯，如果ans=0掂墓，則必輸；否則絮宁，則贏梆暮。
題目2：
今有若干堆火柴，兩人依次從中拿取绍昂，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走偿荷，但不可不取窘游，最后取完者為負(fù)，求先手勝負(fù)跳纳。
題解：全是1的時(shí)候忍饰，特判，數(shù)1的個(gè)數(shù)寺庄，奇數(shù)輸艾蓝，偶數(shù)贏。否則斗塘，設(shè)ans為所有數(shù)據(jù)的xor運(yùn)算赢织，如果ans=0，則必輸馍盟；反之于置，則贏。
https://vjudge.net/problem/HDU-1907
題意：n堆石子贞岭，最后一個(gè)取完的人輸八毯。
Nimm博弈：全是1的時(shí)候，特判瞄桨，數(shù)1的個(gè)數(shù)话速，奇數(shù)輸，偶數(shù)贏芯侥。
#include <cstdio>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,ans=0,flag=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&m);
ans^=m;
if(m>1) flag=1;//當(dāng)所有數(shù)據(jù)都為1時(shí)的特判
}
if(flag){
if(ans==0) puts("Brother");
else puts("John");
}
else
{
if(n&1) puts("Brother");
else puts("John");
}
}
}
https://vjudge.net/problem/HDU-185
題意：二人小游戲：桌子上有M堆撲克牌泊交；每堆牌的數(shù)量分別為Ni(i=1…M)；兩人輪流進(jìn)行；每走一步可以任意選擇一堆并取走其中的任意張牌活合；桌子上的撲克全部取光雏婶，則游戲結(jié)束；最后一次取牌的人為勝者白指。 現(xiàn)在我們不想研究到底先手為勝還是為負(fù)留晚，我只想問大家：
――“先手的人如果想贏，第一步有幾種選擇呢告嘲？”
#include <cstdio>
const int maxn=110;
int arr[maxn];
int main()
{
int n,res,sum;
while(scanf("%d",&n)!=EOF,n)
{
res=0;
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",arr+i);
res^=arr[i];
}
if(!res) {
printf("0\n");
continue;
}
//為了讓對手輸错维，則自己第一輪應(yīng)該在某一堆拿走k塊石頭，使得對手面對奇異狀態(tài)橄唬，即對手的異或?yàn)?
//第i堆可以取走石頭的前提是赋焕，使對手面對奇異狀態(tài)的石頭數(shù)<第i堆的石頭數(shù)
for(int i=1;i<=n;i++)
{
if((res^arr[i])<arr[i]) sum++;//res^arr[i]:除了第i堆石頭，其它堆的石頭進(jìn)行xor運(yùn)算
}
printf("%d\n",sum);
}
return 0;
}
