巴什游戲(Bash Game)
裸題：HDU 1846 Brave Game
題目鏈接：https://vjudge.net/problem/HDU-1846
題意：有 顆石子，甲先取，乙后取纫骑，每次可以拿
顆石子，輪流拿下去登颓，拿到最后一顆的人獲勝。
思路：動(dòng)態(tài)規(guī)劃红氯。時(shí)間復(fù)雜度為 框咙，本題數(shù)據(jù)不是很強(qiáng)，可以通過(guò)痢甘。
AC代碼：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n, m;
scanf("%d%d", &n, &m);
memset(f, 0, sizeof f);
for(int i = 1; i <= m; i++) f[i] = 1;
for(int i = m + 1; i <= n; i++)
{
int t = 1;
for(int j = 1; j <= m; j++) t &= f[i - j];
// 如果有一個(gè)是必?cái)B(tài)喇嘱，那么這個(gè)狀態(tài)就是必勝態(tài)
// 如果全是必勝態(tài)，那么這個(gè)狀態(tài)就是必?cái)B(tài)
f[i] = (t == 1 ? 0 : 1);
}
if(f[n]) puts("first");
else puts("second");
}
return 0;
}
上面動(dòng)態(tài)規(guī)劃的求解過(guò)程非常直觀塞栅，但時(shí)間復(fù)雜度略高者铜，所以，我們選擇將 的結(jié)果打印出來(lái)放椰，看看有沒(méi)有什么規(guī)律作烟。
可以發(fā)現(xiàn)，如果 是
的倍數(shù)砾医，則后手獲勝拿撩；否則，先手獲勝如蚜。
這個(gè)規(guī)律怎么解釋呢压恒？先來(lái)看兩種簡(jiǎn)單的情況：
當(dāng)
時(shí)，由于一次最少拿
個(gè)错邦、最多拿
個(gè)涎显，甲可以一次拿完，先手贏兴猩。
當(dāng)
時(shí)，無(wú)論甲拿走多少個(gè)（
個(gè)）早歇，剩下的都多于
上面兩種情況可以擴(kuò)展為以下兩種情況：
如果
潭千，即
是
的整數(shù)倍，那么不管甲拿多少借尿，例如
個(gè)刨晴，乙都拿
個(gè)，使得剩下的永遠(yuǎn)是
如果
茂契，即
，那么甲拿走
在這個(gè)拿石子的游戲里璧亚，對(duì)于后拿的乙來(lái)說(shuō)是很不利的讨韭，只有在 的情況下乙才能贏，在其他情況下都是甲贏涨岁。
AC代碼：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n, m;
cin >> n >> m;
if(n % (m + 1) == 0) puts("second");
else puts("first");
}
return 0;
}
本題是最經(jīng)典也是最簡(jiǎn)單的巴什游戲拐袜，在編程時(shí)可以用動(dòng)態(tài)規(guī)劃，也可以直接按周期性變化規(guī)律做求余計(jì)算梢薪。但是蹬铺，如果遇到更復(fù)雜的游戲，將很難分析秉撇。有一種高級(jí)的分析方法甜攀，即Sprague-Grundy函數(shù)，是該類(lèi)問(wèn)題的通用方法琐馆。
Sprague-Grundy函數(shù)
首先介紹一些概念：
公平組合游戲(Impartial Combinatorial Game, ICG)
若一個(gè)游戲滿(mǎn)足：
- 由兩名玩家交替行動(dòng)规阀；
- 在游戲進(jìn)程的任意時(shí)刻，可以執(zhí)行的合法行動(dòng)與輪到哪名玩家無(wú)關(guān)瘦麸；
- 不能行動(dòng)的玩家判負(fù)谁撼；
則稱(chēng)該游戲?yàn)橐粋€(gè)公平組合游戲。
常見(jiàn)的棋類(lèi)游戲滋饲，比如圍棋厉碟，就不是公平組合游戲喊巍。因?yàn)閲褰粦?zhàn)雙方分別只能落黑子和白子，勝負(fù)判定也比較復(fù)雜箍鼓，不滿(mǎn)足條件 和條件
崭参。
有向圖游戲
給定一個(gè)有向無(wú)環(huán)圖，圖中有一個(gè)唯一的起點(diǎn)款咖，在起點(diǎn)上放有一枚棋子何暮。兩名玩家交替地把這枚棋子沿有向邊進(jìn)行移動(dòng)，每次可以移動(dòng)一步铐殃，無(wú)法移動(dòng)者判負(fù)海洼。該游戲被稱(chēng)為有向圖游戲。
任何一個(gè)公平組合游戲都可以轉(zhuǎn)化為有向圖游戲背稼。具體方法是贰军，把每個(gè)局面看成圖中的一個(gè)節(jié)點(diǎn)，并且從每個(gè)局面向沿著合法行動(dòng)能夠到達(dá)的下一個(gè)局面連有向邊蟹肘。
Mex運(yùn)算
設(shè) 表示一個(gè)非負(fù)整數(shù)集合词疼。定義
為求出不屬于集合
的最小非負(fù)整數(shù)的運(yùn)算，即：
SG函數(shù)
在有向圖游戲中帘腹，對(duì)于每個(gè)節(jié)點(diǎn) 贰盗，設(shè)從
出發(fā)共有
條有向邊，分別到達(dá)節(jié)點(diǎn)
阳欲，定義
為
的后繼節(jié)點(diǎn)
的 SG 函數(shù)值構(gòu)成的集合再執(zhí)行 mex 運(yùn)算的結(jié)果舵盈，即：
特別地，整個(gè)有向圖游戲 的 SG 函數(shù)值被定義為有向圖游戲起點(diǎn)
的 SG 函數(shù)值球化，即
秽晚。
有向圖游戲的和
設(shè) 是
個(gè)有向圖游戲。定義有向圖游戲
筒愚，它的行動(dòng)規(guī)則是任選某個(gè)有向圖游戲
赴蝇，并在
上行動(dòng)一步。
被稱(chēng)為有向圖游戲
的和巢掺。
有向圖游戲的和的 SG 函數(shù)值等于它包含的各個(gè)子游戲 SG 函數(shù)值的異或和句伶，即：
定理
有向圖游戲的某個(gè)局面必勝，當(dāng)且僅當(dāng)該局面對(duì)應(yīng)節(jié)點(diǎn)的SG函數(shù)值大于0陆淀。
有向圖游戲的某個(gè)局面必?cái)】加啵?dāng)且僅當(dāng)該局面對(duì)應(yīng)節(jié)點(diǎn)的SG函數(shù)值等于0。
至此轧苫，相關(guān)概念就介紹完了楚堤，接著，我們嘗試用SG函數(shù)求解HDU 1846的巴什游戲。
AC代碼：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
int sg[N], s[N];
int main()
{
int T;
cin >> T;
while(T--)
{
int n, m;
cin >> n >> m;
memset(sg, 0, sizeof sg);
for(int i = 1; i <= n; i++)
{
memset(s, 0, sizeof s);
// 把i的后繼結(jié)點(diǎn)放到集合s中
for(int j = 1; j <= m && i - j >= 0; j++) s[sg[i - j]] = 1;
// 計(jì)算sg[i]
for(int j = 0; j <= n; j++)
{
if(!s[j])
{
sg[i] = j;
break;
}
}
}
if(sg[n]) puts("first");
else puts("second");
}
return 0;
}
