學了三種簡單博弈(前一篇)之后,我又在這篇博文這學了HDU1907的解法
下面說下我的理解,有些借鑒原博文。

這題和下面的題有點相似,但是又不一樣
也就是說把最后取完的定為輸家改成,最后取完的定為贏家。
后面的這個要簡單一點,下面是簡單分析,先來看這個簡單的
首先我們用T表示當前狀態的所有火柴數異或為0,否則極為S。
1.S可以轉化成T
我們設一共有n堆火柴,每堆有k(i)根.
那么S態中k(1)^k(2)^……^k(n) != 0,這個值我們記為c
那么肯定有某個k(i)的最高位和c的最高位同為1,不然c的最高位變成了0
假設這個最高位和c的最高位同為1的是第m堆,這樣我們可以得到x = k(m)^c < k(m)(x的最高位為0)
k(1)^k(2)^……^x^……^k(n)
=k(1)^k(2)^……^k(m)^c^……^k(n)
=k(1)^k(2)^……^k(m)^k(m+1)^……^k(n)^(k(1)^k(2)^K(3)^……^k(n))
= 0
這樣我們只要從第m堆中取出k(m)-x根火柴,那么剩下的就變成了T態。
2.T一定會轉化成S
假設T不轉化成S,
我們從第m堆中取出一定的火柴數那么我們得到
0 = k(1)^k(2)^……^k(m)^……^k(n)
0 = k(1)^k(2)^……^k(m')^……^k(n)(k(m)表示取之前的 k(m')表示取最后的)
那么我們得到k(m)^k(m')=0也就是說k(m)==k(m')矛盾。
3.S態,只要方法得當就可以取勝
每一個S態可以轉化成T態,然后每一個T態必然轉化成S態,所以每一次只要把S態變成T態,那么對手就只能把T態變成S態,這樣自己就一直控制著S態,最后一定可以取完(變成T態)成為勝利者
4.T態,只要對手方法得當就必輸
同3
下面我們來看看該題的思路
我們設只有一根火柴的堆為單根堆,否則為充裕堆,充裕堆>=2的T用T2表示,全是單根堆的T用T0表示(沒有T1)
同樣的充裕堆>=2的S用S2表示,全為單根堆的S用S0表示,只有一堆充裕堆的用S1表示
5.S0必敗,T0必勝
每次自己取奇數堆的,那么最后一堆一定由自己取.T0必勝同理
6.S1只要方法得當,必勝
如果單根堆的堆數為偶數,那么把充裕堆中取成只剩下1根,變成S0,對手必敗.如果單根堆的堆數為奇數,那么把充裕堆全取完,同樣對手必敗
7.S2不可以一次轉化到T0
每次最多只能取完一堆,所以2堆充裕堆不可能一次就沒了
8.S2可以一次變成T2
用1可知S可以變成T,由7可知S不可一次變成T0,所以S可以一次變成T2
9.T2不可以一次變成S0
同7
10.T2一定變成S1或者S2中的一種
由2知T一定變成S,由9知T2不可一次變成S0,所以一定變成S1或S2中的一種
11.S2,只要方法得當一定勝
S2可以變成T2,然T2一定變成S1或者S2,如果變成S1,已勝,變成S2,則繼續,直到T2只能變成S1為止。
12.T2,只要對手方法得當必輸
同11
綜上所述先手必勝態為T0 S2 S1
必輸態為S0 T2

到這這兩題就可以輕松搞定了。