《博弈-哈尔滨工业大学2016暑期acm训练》由会员分享，可在线阅读，更多相关《博弈-哈尔滨工业大学2016暑期acm训练（33页珍藏版）》请在金锄头文库上搜索。
1、,博弈,取石子游戏,巴什博弈,一堆n个石子，两个人轮流取，每次至少取一个，至多取m个，最后取光者胜。,巴什博弈,必胜态 必败态,威佐夫博弈,有两堆石子，两个人轮流取，每次可以从其中一堆或者两堆同时取至少一个石子，最后取光者胜。,威佐夫博弈,奇异局势：,威佐夫博弈,奇异局势： (0,0) (1,2) (3,5) (4,7) (6,10) (8,13) ,威佐夫博弈,奇异局势： (0,0) (1,2) (3,5) (4,7) (6,10) (8,13) ak = floor(k(1+sqrt(5)/2) , bk = ak + k,威佐夫博弈,尼姆博奕,有若干堆石子，两个人轮流取，每次可以从一堆中
2、取至少一个石子，最后取光者胜。,尼姆博奕,SG,mex(minimal excludant)SGi = mexsgj ( i - j ),SG,翻硬币游戏,N个硬币排成一排，有的正面朝上，有的反面朝上。两个人轮流翻硬币，每次翻的最右边一个硬币必须由正面翻到反面。不能翻的人输。,翻硬币游戏,1.一次只能翻一个硬币。,翻硬币游戏,1.一次只能翻一个硬币。 2.一次能翻一个或者两个硬币。,翻硬币游戏,hdu3032 Nim or not Nim? 大意：给定n堆石子，alice和bob轮流操作，每次可以从一堆石子中取出若干个，或者将一堆石子分成两堆非空石子。最后取光者胜。,例题：,对SG打表找规律。
3、 SG: 0 1 2 4 3 5 6 8 7 9 10 12 11猜测SGi = i (i%4 = 1 or I % 4 = 2)SGi = i + 1(i%4 = 3)SGi = i 1 (i%4 = 0),例题：,Hdu2516 取石子游戏 大意：1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜。,例题：,打表找规律。 发现2,3,5,8,13都是必败态。 猜测所有Fib都是必败态。 （然后试了一下，发现猜对了。）,例题：,hdu2147 kikis game 大意：在一个n*m的棋盘上，一个硬币位于(1,m)，两个人博弈，每次可以向左、向下或者向左下移动一格，无法移动者输。,例题：,打表找规律。,例题：,打表找规律。,例题：,打表找规律。 其实还有更优美的做法。,例题：,hdu1847 Good Luck in CET-4 Everybody! 大意：一堆N个石子，两个人博弈，每次可以取2的幂次个数的石子，最后取光者胜。,例题：,打表找规律。,例题：,Anti-Nim,有若干堆石子，两个人轮流取，每次可以从一堆中取至少一个石子，最后取光者负。,Anti-Nim,必胜态： 1.每堆石子都只剩1个，且SG=0 2.至少一堆石子1个，且SG0,Anti-Nim,没啦,
