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

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

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