前些日子我打算開了博弈基礎，事后想進行總結下

一句話就是分析必勝或必敗，異或為0。

以下內容來自轉載：

Nim游戲的概述：

還記得這個游戲嗎？
給出n列珍珠，兩人輪流取珍珠，每次在某一列中取至少1顆珍珠，但不能在兩列中取。最后拿光珍珠的人輸。
后來，在一份資料上看到，這種游戲稱為“拈（Nim）”。據說，它源自中國，經由被販賣到美洲的奴工們外傳。辛苦的工人們，在工作閑暇之余，用石頭玩游戲以排遣寂寞。后來流傳到高級人士，則用便士（Pennies），在酒吧柜臺上玩。
最有名的玩法，是把十二枚便士放成3、4、5三列，拿光銅板的人贏。后來，大家發現，先取的人只要在3那列里取走2枚，變成了1、4、5，就能穩操勝券了，游戲也就變得無趣了。于是大家就增加列數，增加銅板的數量，這樣就讓人們有了毫無規律的感覺，不易于把握。
直到本世紀初，哈佛大學數學系副教授查理士?理昂納德?包頓（Chales Leonard Bouton）提出一篇極詳盡的分析和證明，利用數的二進制表示法，解答了這個游戲的一般法則。
一般規則是規定拿光銅板的人贏。
它的變體是規定拿光銅板的人輸，只要注意某種特殊形態（只有1列不為1），就可以了！
有很多人把這個方法寫成計算機程序，來和人對抗，不知就理的人被騙得團團轉，無不驚嘆計算機的神奇偉大。其實說穿了，只因為它計算比人快，數的轉化為二進制其速度快得非人能比，如此罷了。
（以上來自K12教育論壇）

Nim游戲的數學理論論述：

Nim游戲是博弈論中最經典的模型，它又有著十分簡單的規則和無比優美的結論
Nim游戲是組合游戲(Combinatorial Games)的一種，準確來說，屬于“Impartial Combinatorial Games”（以下簡稱ICG）。滿足以下條件的游戲是ICG（可能不太嚴謹）：1、有兩名選手；2、兩名選手交替對游戲進行移動(move)，每次一步，選手可以在（一般而言）有限的合法移動集合中任選一種進行移動；3、對于游戲的任何一種可能的局面，合法的移動集合只取決于這個局面本身，不取決于輪到哪名選手操作、以前的任何操作、骰子的點數或者其它什么因素； 4、如果輪到某名選手移動，且這個局面的合法的移動集合為空（也就是說此時無法進行移動），則這名選手負。根據這個定義，很多日常的游戲并非ICG。例如象棋就不滿足條件3，因為紅方只能移動紅子，黑方只能移動黑子，合法的移動集合取決于輪到哪名選手操作。

通常的Nim游戲的定義是這樣的：有若干堆石子，每堆石子的數量都是有限的，合法的移動是“選擇一堆石子并拿走若干顆（不能不拿）”，如果輪到某個人時所有的石子堆都已經被拿空了，則判負（因為他此刻沒有任何合法的移動）。
這游戲看上去有點復雜，先從簡單情況開始研究吧。如果輪到你的時候，只剩下一堆石子，那么此時的必勝策略肯定是把這堆石子全部拿完一顆也不給對手剩，然后對手就輸了。如果剩下兩堆不相等的石子，必勝策略是通過取多的一堆的石子將兩堆石子變得相等，以后如果對手在某一堆里拿若干顆，你就可以在另一堆中拿同樣多的顆數，直至勝利。如果你面對的是兩堆相等的石子，那么此時你是沒有任何必勝策略的，反而對手可以遵循上面的策略保證必勝。如果是三堆石子……好像已經很難分析了，看來我們必須要借助一些其它好用的（最好是程式化的）分析方法了，或者說，我們最好能夠設計出一種在有必勝策略時就能找到必勝策略的算法。

定義P-position和N-position，其中P代表Previous，N代表Next。直觀的說，上一次move的人有必勝策略的局面是P-position，也就是“后手可保證必勝”或者“先手必敗”，現在輪到move的人有必勝策略的局面是N-position，也就是“先手可保證必勝”。更嚴謹的定義是：1.無法進行任何移動的局面（也就是terminal position）是P-position；2.可以移動到P-position的局面是N-position；3.所有移動都導致N-position的局面是P-position。
按照這個定義，如果局面不可能重現，或者說positions的集合可以進行拓撲排序，那么每個position或者是P-position或者是N-position，而且可以通過定義計算出來。

以Nim游戲為例來進行一下計算。比如說我剛才說當只有兩堆石子且兩堆石子數量相等時后手有必勝策略，也就是這是一個P-position，下面我們依靠定義證明一下(3,3)是一個P是一個P是一個P-position。首先(3,3)的子局面（也就是通過合法移動可以導致的局面）有(0,3)(1,3)(2,3)（顯然交換石子堆的位置不影響其性質，所以把(x,y)和(y,x)看成同一種局面），只需要計算出這三種局面的性質就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)顯然是P-position，所以(0,3)是N-position（只要找到一個是P-position的子局面就能說明是N-position）。(1,3)的后繼中(1,1)是P-position（因為(1,1)的唯一子局面(0,1)是N-position），所以(1,3)也是N-position。同樣可以證明(2,3)是N-position。所以(3,3)的所有子局面都是N-position，它就是P-position。通過一點簡單的數學歸納，可以嚴格的證明“有兩堆石子時的局面是P-position當且僅當這兩堆石子的數目相等”。

根據上面這個過程，可以得到一個遞歸的算法——對于當前的局面，遞歸計算它的所有子局面的性質，如果存在某個子局面是P-position，那么向這個子局面的移動就是必勝策略。當然，可能你已經敏銳地看出有大量的重疊子問題，所以可以用DP或者記憶化搜索的方法以提高效率。但問題是，利用這個算法，對于某個Nim游戲的局面(a1,a2,...,an)來說，要想判斷它的性質以及找出必勝策略，需要計算O(a1*a2*...*an)個局面的性質，不管怎樣記憶化都無法降低這個時間復雜度。所以我們需要更高效的判斷Nim游戲的局面的性質的方法。

直接說結論好了。

(Bouton's Theorem)：對于一個Nim游戲的局面(a1,a2,...,an)，它是P-position當且僅當a1^a2^...^an=0，其中^表示異或(xor)運算。

怎么樣，是不是很神奇？我看到它的時候也覺得很神奇，完全沒有道理的和異或運算扯上了關系。但這個定理的證明卻也不復雜，基本上就是按照兩種position的證明來的。

根據定義，證明一種判斷position的性質的方法的正確性，只需證明三個命題： 1、這個判斷將所有terminal position判為P-position；2、根據這個判斷被判為N-position的局面一定可以移動到某個P-position；3、根據這個判斷被判為P-position的局面無法移動到某個P-position。

第一個命題顯然，terminal position只有一個，就是全0，異或仍然是0。

第二個命題，對于某個局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某個合法的移動，將ai改變成ai'后滿足a1^a2^...^ai'^...^an=0。不妨設a1^a2^...^an=k，則一定存在某個ai，它的二進制表示在k的最高位上是1（否則k的最高位那個1是怎么得到的）。這時ai^k<ai一定成立。則我們可以將ai改變成ai'=ai^k，此時a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

第三個命題，對于某個局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某個合法的移動，將ai改變成ai'后滿足a1^a2^...^ai'^...^an=0。因為異或運算滿足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以將ai改變成ai'不是一個合法的移動。證畢。

根據這個定理，我們可以在O(n)的時間內判斷一個Nim的局面的性質，且如果它是N-position，也可以在O(n)的時間內找到所有的必勝策略。Nim問題就這樣基本上完美的解決了。

（以上來自百度百科）

Nim游戲的形象具體論述：

Nim取子游戲是由兩個人面對若干堆硬幣（或石子）進行的游戲。設有k>=1堆硬幣，各堆分別含有N₁，N₂，……N_K枚硬幣。游戲的目的就是選擇最后剩下的硬幣。游戲法則如下： 1．兩個游戲人交替進行游戲（游戲人I和游戲人II）； 2．當輪到每個游戲人取子時，選擇這些堆中的一堆，并從所選的堆中取走至少一枚硬幣（游戲人可以取走他所選堆中的全部硬幣）； 3．當所有的堆都變成空堆時，最后取子的游戲人即為勝者。 這個游戲中的變量是堆數k和各堆的硬幣數N₁，N₂，……N_k。對應的組合問題是，確定游戲人I獲勝還是游戲人II獲勝以及兩個游戲人應該如何取子才能保證自己獲勝（獲勝策略）。 為了進一步理解Nim取子游戲，我們考查某些特殊情況。如果游戲開始時只有一堆硬幣，游戲人I則通過取走所有的硬幣而獲勝。現在設有2堆硬幣，且硬幣數量分別為N₁和N₂。游戲人取得勝利并不在于N1和N2的值具體是多少，而是取決于它們是否相等。設N₁！=N₂，游戲人I從大堆中取走的硬幣使得兩堆硬幣數量相等，于是，游戲人I以后每次取子的數量與游戲人II相等而最終獲勝。但是如果N₁= N₂，則：游戲人II只要按著游戲人I取子的數量在另一堆中取相等數量的硬幣，最終獲勝者將會是游戲人II。這樣，兩堆的取子獲勝策略就已經找到了。 現在我們如何從兩堆的取子策略擴展到任意堆數中呢？ 首先來回憶一下，每個正整數都有對應的一個二進制數，例如：57_(10)?à?111001₍₂₎?，即：57₍₁₀₎=2⁵+2⁴+2³+2⁰。于是，我們可以認為每一堆硬幣數由2的冪數的子堆組成。這樣，含有57枚硬幣大堆就能看成是分別由數量為2⁵、2⁴、2³、2⁰的各個子堆組成。 現在考慮各大堆大小分別為N₁，N₂，……N_k的一般的Nim取子游戲。將每一個數N_i表示為其二進制數（數的位數相等，不等時在前面補0）： N_1?= a_s…a₁a₀ N_2?= b_s…b₁b₀ …… N_k?= m_s…m₁m₀ 如果每一種大小的子堆的個數都是偶數，我們就稱Nim取子游戲是平衡的，而對應位相加是偶數的稱為平衡位，否則稱為非平衡位。因此，Nim取子游戲是平衡的，當且僅當：

a_s?+ b_s?+ … + m_s?是偶數

……

a_1?+ b_1?+ … + m_1?是偶數

a_0?+ b₀?+ … + m₀是偶數

于是，我們就能得出獲勝策略： 游戲人I能夠在非平衡取子游戲中取勝，而游戲人II能夠在平衡的取子游戲中取勝。 我們以一個兩堆硬幣的Nim取子游戲作為試驗。設游戲開始時游戲處于非平衡狀態。這樣，游戲人I就能通過一種取子方式使得他取子后留給游戲人II的是一個平衡狀態下的游戲，接著無論游戲人II如何取子，再留給游戲人I的一定是一個非平衡狀態游戲，如此反復進行，當游戲人II在最后一次平衡狀態下取子后，游戲人I便能一次性取走所有的硬幣而獲勝。而如果游戲開始時游戲牌平衡狀態，那根據上述方式取子，最終游戲人II能獲勝。 下面應用此獲勝策略來考慮4-堆的Nim取子游戲。其中各堆的大小分別為7，9，12，15枚硬幣。用二進制表示各數分別為：0111，1001，1100和1111。于是可得到如下一表：

?	23?= 8	22?= 4	21?= 2	20?= 1
大小為7的堆	0	1	1	1
大小為9的堆	1	0	0	1
大小為12的堆	1	1	0	0
大小為15的堆	1	1	1	1

由Nim取子游戲的平衡條件可知，此游戲是一個非平衡狀態的取子游戲，因此，游戲人I在按獲勝策略進行取子游戲下將一定能夠取得最終的勝利。具體做法有多種，游戲人I可以從大小為12的堆中取走11枚硬幣，使得游戲達到平衡（如下表），

?	23?= 8	22?= 4	21?= 2	20?= 1
大小為7的堆	0	1	1	1
大小為9的堆	1	0	0	1
大小為12的堆	0	0	0	1
大小為15的堆	1	1	1	1

之后，無論游戲人II如何取子，游戲人I在取子后仍使得游戲達到平衡。 同樣的道理，游戲人I也可以選擇大小為9的堆并取走5枚硬幣而剩下4枚，或者，游戲人I從大小為15的堆中取走13枚而留下2枚。

歸根結底，Nim取子游戲的關鍵在于游戲開始時游戲處于何種狀態（平衡或非平衡）和第一個游戲人是否能夠按照取子游戲的獲勝策略來進行游戲。

(以上轉自Rainco_shnu的百度空間)

下面寫點自己的東西:

如果Nim游戲中的規則稍微變動一下,每次最多只能取K個,怎么處理?

方法是將每堆石子數mod (k+1).

Bash Game

巴什博弈：只有一堆n個物品，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取m個。最后取光者得勝。 顯然，如果n=m+1，那么由于一次最多只能取m個，所以，無論先取者拿走多少個，后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發現了如何取勝的法則：如果n=（m+1）r+s，（r為任意自然數，s≤m),那么先取者要拿走s個物品，如果后取者拿走k（≤m)個，那么先取者再拿走m+1-k個，結果剩下（m+1）（r-1）個，以后保持這樣的取法，那么先取者肯定獲勝。總之，要保持給對手留下（m+1）的倍數，就能最后獲勝。 這個游戲還可以有一種變相的玩法：兩個人輪流報數，每次至少報一個，最多報十個，誰能報到100者勝。 對于巴什博弈，那么我們規定，如果最后取光者輸，那么又會如何呢？ （n-1）%（m+1）==0則后手勝利 先手會重新決定策略，所以不是簡單的相反行的 例如n=15，m=3 后手 先手 剩余 0 2 13 1 3 9 2 2 5 3 1 1 1 0 0 先手勝利 輸的人最后必定只抓走一個，如果>1個，則必定會留一個給對手 Wythoff Game 威佐夫博弈（Wythoff Game）：有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規定每次至少取一個，多者不限，最后取光者得勝。 兩個人如果都采用正確操作，那么面對非奇異局勢，先拿者必勝；反之，則后拿者取勝。 結論 那么任給一個局勢（a，b），怎樣判斷它是不是奇異局勢呢？我們有如下公式： ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...n 方括號表示取整函數) 奇妙的是其中出現了黃金分割數（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，b = aj + j + 1，若都不是，那么就不是奇異局勢。然后再按照上述法則進行，一定會遇到奇異局勢。

?附：來自Matrix67: The Aha Moments

什么是P問題、NP問題和NPC問題

????這或許是眾多OIer最大的誤區之一。
????你會經常看到網上出現“這怎么做，這不是NP問題嗎”、“這個只有搜了，這已經被證明是NP問題了”之類的話。你要知道，大多數人此時所說的NP問題其實都是指的NPC問題。他們沒有搞清楚NP問題和NPC問題的概念。NP問題并不是那種“只有搜才行”的問題，NPC問題才是。好，行了，基本上這個誤解已經被澄清了。下面的內容都是在講什么是P問題，什么是NP問題，什么是NPC問題，你如果不是很感興趣就可以不看了。接下來你可以看到，把NP問題當成是 NPC問題是一個多大的錯誤。

????還是先用幾句話簡單說明一下時間復雜度。時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規模擴大后，程序需要的時間長度增長得有多快。也就是說，對于高速處理數據的計算機來說，處理某一個特定數據的效率不能衡量一個程序的好壞，而應該看當這個數據的規模變大到數百倍后，程序運行時間是否還是一樣，或者也跟著慢了數百倍，或者變慢了數萬倍。不管數據有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復雜度，也稱常數級復雜度；數據規模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是O(n)，比如找n個數中的最大值；而像冒泡排序、插入排序等，數據擴大2倍，時間變慢4倍的，屬于O(n^2)的復雜度。還有一些窮舉類的算法，所需時間長度成幾何階數上漲，這就是O(a^n)的指數級復雜度，甚至O(n!)的階乘級復雜度。不會存在O(2*n^2)的復雜度，因為前面的那個“2”是系數，根本不會影響到整個程序的時間增長。同樣地，O (n^3+n^2)的復雜度也就是O(n^3)的復雜度。因此，我們會說，一個O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，盡管在n很小的時候，前者優于后者，但后者時間隨數據規模增長得慢，最終O(n^3)的復雜度將遠遠超過O(n^2)。我們也說，O(n^100)的復雜度小于O(1.01^n)的復雜度。
????容易看出，前面的幾類復雜度被分為兩種級別，其中后者的復雜度無論如何都遠遠大于前者：一種是O(1),O(log(n)),O(n^a)等，我們把它叫做多項式級的復雜度，因為它的規模n出現在底數的位置；另一種是O(a^n)和O(n!)型復雜度，它是非多項式級的，其復雜度計算機往往不能承受。當我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復雜度，非多項式級的復雜度需要的時間太多，往往會超時，除非是數據規模非常小。

????自然地，人們會想到一個問題：會不會所有的問題都可以找到復雜度為多項式級的算法呢？很遺憾，答案是否定的。有些問題甚至根本不可能找到一個正確的算法來，這稱之為“不可解問題”(Undecidable Decision Problem)。The Halting Problem就是一個著名的不可解問題，在我的Blog上有過專門的介紹和證明。再比如，輸出從1到n這n個數的全排列。不管你用什么方法，你的復雜度都是階乘級，因為你總得用階乘級的時間打印出結果來。有人說，這樣的“問題”不是一個“正規”的問題，正規的問題是讓程序解決一個問題，輸出一個“YES”或“NO”（這被稱為判定性問題），或者一個什么什么的最優值（這被稱為最優化問題）。那么，根據這個定義，我也能舉出一個不大可能會有多項式級算法的問題來：Hamilton回路。問題是這樣的：給你一個圖，問你能否找到一條經過每個頂點一次且恰好一次（不遺漏也不重復）最后又走回來的路（滿足這個條件的路徑叫做Hamilton回路）。這個問題現在還沒有找到多項式級的算法。事實上，這個問題就是我們后面要說的NPC問題。

????下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。P是英文單詞多項式的第一個字母。哪些問題是P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的算法。
????接下來引入NP問題的概念。這個就有點難理解了，或者說容易理解錯誤。在這里強調（回到我竭力想澄清的誤區上），NP問題不是非P類問題。NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準。現在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小于100個單位長度的路線。它根據數據畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權值加起來一看，嘿，神了，路徑長度98，比100小。于是答案出來了，存在比100小的路徑。別人會問他這題怎么做出來的，他就可以說，因為我找到了一個比100 小的解。在這個題中，找一個解很困難，但驗證一個解很容易。驗證一個解只需要O(n)的時間復雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那么，只要我RP好，猜得準，我一定能在多項式的時間里解決這個問題。我猜到的方案總是最優的，不滿足題意的方案也不會來騙我去選它。這就是NP問題。當然有不是NP問題的問題，即你猜到了解但是沒用，因為你不能在多項式的時間里去驗證它。下面我要舉的例子是一個經典的例子，它指出了一個目前還沒有辦法在多項式的時間里驗證一個解的問題。很顯然，前面所說的Hamilton回路是NP問題，因為驗證一條路是否恰好經過了每一個頂點非常容易。但我要把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間里進行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒有Hamilton回路”。
????之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快明白，信息學中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關系。

????很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有 NP問題劃進另一個集合NP中，那么，顯然有P屬于NP。現在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP。
????NP問題一直都是信息學的巔峰。巔峰，意即很引人注目但難以解決。在信息學研究中，這是一個耗費了很多時間和精力也沒有解決的終極問
題，好比物理學中的大統一和數學中的歌德巴赫猜想等。
????目前為止這個問題還“啃不動”。但是，一個總的趨勢、一個大方向是有的。人們普遍認為，P=NP不成立，也就是說，多數人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題。人們如此堅信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-完全問題，也即所謂的 NPC問題。C是英文單詞“完全”的第一個字母。正是NPC問題的存在，使人們相信P≠NP。下文將花大量篇幅介紹NPC問題，你從中可以體會到NPC問題使P=NP變得多么不可思議。

????為了說明NPC問題，我們先引入一個概念——約化(Reducibility，有的資料上叫“歸約”)。
????簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。《算法導論》上舉了這么一個例子。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那么我們能找到一個“規則”，按照這個規則把解一元一次方程程序的輸入數據變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規則即是：兩個方程的對應項系數不變，一元二次方程的二次項系數為0。按照這個規則把前一個問題轉換成后一個問題，兩個問題就等價了。同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點相連即這兩點距離為0，兩點不直接相連則令其距離為1，于是問題轉化為在TSP問題中，是否存在一條長為0的路徑。Hamilton回路存在當且僅當TSP問題中存在長為0的回路。
????“問題A可約化為問題B”有一個重要的直觀意義：B的時間復雜度高于或者等于A的時間復雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間復雜度比A的時間復雜度還低了，那A的算法就可以改進為B的算法，兩者的時間復雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決后者。
????很顯然，約化具有一項重要的性質：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。這個道理非常簡單，就不必闡述了。
????現在再來說一下約化的標準概念就不難理解了：如果能找到這樣一個變化法則，對任意一個程序A的輸入，都能按這個法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說，問題A可約化為問題B。
????當然，我們所說的“可約化”是指的可“多項式地”約化(Polynomial-time Reducible)，即變換輸入的方法是能在多項式的時間里完成的。約化的過程只有用多項式的時間完成才有意義。

????好了，從約化的定義中我們看到，一個問題約化為另一個問題，時間復雜度增加了，問題的應用范圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找復雜度更高，但應用范圍更廣的算法來代替復雜度雖然低，但只能用于很小的一類問題的算法。再回想前面講的P和NP問題，聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復雜的大NP問題，那么最后是否有可能找到一個時間復雜度最高，并且能“通吃”所有的 NP問題的這樣一個超級NP問題？答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC 問題，也就是NP-完全問題。NPC問題的出現使整個NP問題的研究得到了飛躍式的發展。我們有理由相信，NPC問題是最復雜的問題。再次回到全文開頭，我們可以看到，人們想表達一個問題不存在多項式的高效算法時應該說它“屬于NPC問題”。此時，我的目的終于達到了，我已經把NP問題和NPC問題區別開了。到此為止，本文已經寫了近5000字了，我佩服你還能看到這里來，同時也佩服一下自己能寫到這里來。

????NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。證明一個問題是 NPC問題也很簡單。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至于第一個NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。
????既然所有的NP問題都能約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等于P 了。因此，給NPC找一個多項式算法太不可思議了。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法，只能用指數級甚至階乘級復雜度的搜索。

????順便講一下NP-Hard問題。NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發現了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復雜度更高從而更難以解決。

????不要以為NPC問題是一紙空談。NPC問題是存在的。確實有這么一個非常具體的問題屬于NPC問題。下文即將介紹它。
????下文即將介紹邏輯電路問題。這是第一個NPC問題。其它的NPC問題都是由這個問題約化而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”。
????邏輯電路問題是指的這樣一個問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True。
????什么叫做邏輯電路呢？一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成。看下面一例，不需要解釋你馬上就明白了。
??┌───┐
??│ 輸入1├─→┐????┌──┐
??└───┘????└─→┤????│
??????????????????????│ or ├→─┐
??┌───┐????┌─→┤????│????│????┌──┐
??│ 輸入2├─→┤????└──┘????└─→┤????│
?&
nbsp;└───┘????│????????????????┌─→┤AND ├──→輸出
????????????????└────────┘┌→┤????│
??┌───┐????┌──┐????????????│??└──┘
??│ 輸入3├─→┤ NOT├─→────┘
??└───┘????└──┘
????這是個較簡單的邏輯電路，當輸入1、輸入2、輸入3分別為True、True、False或False、True、False時，輸出為True。
????有輸出無論如何都不可能為True的邏輯電路嗎？有。下面就是一個簡單的例子。
??┌───┐
??│輸入1 ├→─┐????┌──┐
??└───┘????└─→┤????│
??????????????????????│AND ├─→┐
????????????????┌─→┤????│????│
????????????????│????└──┘????│??┌──┐
????????????????│????????????????└→┤????│
??┌───┐????│????????????????????│AND ├─→輸出
??│輸入2 ├→─┤??┌──┐??????┌→┤????│
??└───┘????└→┤NOT ├→──┘??└──┘
????????????????????└──┘
????上面這個邏輯電路中，無論輸入是什么，輸出都是False。我們就說，這個邏輯電路不存在使輸出為True的一組輸入。
????回到上文，給定一個邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。
????邏輯電路問題屬于NPC問題。這是有嚴格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它（不要以為NP問題有無窮多個將給證明造成不可逾越的困難）。證明過程相當復雜，其大概意思是說任意一個NP問題的輸入和輸出都可以轉換成邏輯電路的輸入和輸出（想想計算機內部也不過是一些 0和1的運算），因此對于一個NP問題來說，問題轉化為了求出滿足結果為True的一個輸入（即一個可行解）。

????有了第一個NPC問題后，一大堆NPC問題就出現了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題。現在被證明是NPC問題的有很多，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了。因此說，正是因為NPC問題的存在，P=NP變得難以置信。P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘。攀登這個信息學的巔峰是我們這一代的終極目標。現在我們需要做的，至少是不要把概念弄混淆了。

Matrix67原創

TOJ 2703: Cow Digit Game

2306: S-Nim??

Time Limit(Common/Java):1000MS/10000MS ? ? Memory Limit:65536KByte
Total Submit: 9 ? ? ? ?? ? Accepted:7

Description

Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows:

?

• The starting position has a number of heaps, all containing some, not necessarily equal, number of beads.
• The players take turns chosing a heap and removing a positive number of beads from it.
• The first player not able to make a move, loses.

Arthur and Caroll really enjoyed playing this simple game until they recently learned an easy way to always be able to find the best move:

?

• Xor the number of beads in the heaps in the current position (i.e. if we have 2, 4 and 7 the?xor-sum?will be 1 as 2 xor 4 xor 7 = 1).
• If the xor-sum is 0, too bad, you will lose.
• Otherwise, move such that the xor-sum becomes 0. This is always possible.

It is quite easy to convince oneself that this works. Consider these facts:

?

• The player that takes the last bead wins.
• After the winning player's last move the xor-sum will be 0.
• The xor-sum will change after every move.

Which means that if you make sure that the xor-sum always is 0 when you have made your move, your opponent will never be able to win, and, thus, you will win.

Understandibly it is no fun to play a game when both players know how to play perfectly (ignorance is bliss). Fourtunately, Arthur and Caroll soon came up with a similar game, S-Nim, that seemed to solve this problem. Each player is now only allowed to remove a number of beads in some predefined set S, e.g. if we have S = {2, 5} each player is only allowed to remove 2 or 5 beads. Now it is not always possible to make the xor-sum 0 and, thus, the strategy above is useless. Or is it?

Your job is to write a program that determines if a position of S-Nim is a losing or a winning position. A position is a winning position if there is at least one move to a losing position. A position is a losing position if there are no moves to a losing position. This means, as expected, that a position with no legal moves is a losing position.

?

Input

?

Input consists of a number of test cases.

For each test case: The first line contains a number?k?(0 <?k?≤ 100) describing the size of S, followed by?k?numbers?s_i?(0 <?s_i?≤ 10000) describing S. The second line contains a number?m?(0 <?m?≤ 100) describing the number of positions to evaluate. The next?m?lines each contain a number?l?(0 <?l?≤ 100) describing the number of heaps and?l?numbers?h_i?(0 ≤?h_i?≤ 10000) describing the number of beads in the heaps.

The last test case is followed by a 0 on a line of its own.

?

Output

?

For each position:

?

• If the described position is a winning position print a 'W'.
• If the described position is a losing position print an 'L'.

Print a newline character after each test case.

?

Sample Input

?

2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0

Sample Output

?

LWW
WWL

sg函數模板題

#include <stdio.h> #include <algorithm> using namespace std; int s[110],sg[10010],n; int SG(int x) { int i; if(sg[x]!=-1) return sg[x]; bool vis[110]; memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) { if(x>=s[i]) { SG(x-s[i]); vis[sg[x-s[i]]]=1; } } int e; for(i=0;;i++) if(!vis[i]) { e=i; break; } return sg[x]=e; } int main() { int i,m,t,num; while(scanf("%d",&n)&&n) { for(i=0;i<n;i++) scanf("%d",&s[i]); memset(sg,-1,sizeof(sg)); sort(s,s+n); scanf("%d",&m); while(m--) { scanf("%d",&t); int a=0; while(t--) { scanf("%d",&num); a^=SG(num); } if(a) printf("W"); else printf("L"); } printf("\n");} return 0; }

sg模版

//SG 的模板： int mex1(int p) { int i,t; bool vis[101]={0}; for(i=0;i<n;i++) //n是S數組的個數 { t=p-S[i];// S[i]是題中定義的特殊取法規則的數組（） if(t<0) break; if (f[t]==-1) //f[] 表示存放SG 函數值的數組 f[t]=mex1(t); vis[f[t]]=1; } for(i=0;;i++) { if (!vis[i]) return i; } } //注意： S數組要按從小到大排序，注意f和g數組的大小選定

?

2954: 取石子游戲??

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 44 ? ? ? ?? ? Accepted:18

Description

?

給定n堆棋子(1=<n<=6)，兩個人a,b去取棋子。規則是：一個人一次只能從一堆棋子里面取，每次至少取一個，可以取任意個，誰先取完棋子就贏了。題目假設a這個人先取。

例子：假如給2堆，數量分別為8，7，那么a從第一堆取1一個棋子，剩下相同的兩堆。這個時候b取多少，a只要從另外一堆取相同數目的棋子，這樣下去a肯定可以贏了。

?

Input

?

第一行：輸入n表示堆數（1<=n<=6）

第二行：輸入n組數據，并且保證其中一堆的數量比其他各堆的數量多一倍或一倍多。只有兩堆不用遵循這個規則。

各個數據都小于2^31。

?

Output

輸出a最先在最大堆里取的數量，才能保證a一定會贏。

Sample Input

?

2
8 7
3
4 8 17

Sample Output

?

1
5

Hint

提示：第一次a肯定從最大數量的堆里取棋子，因為這樣是保證自己贏的前提之一。 乍一看還以為是個規律題，因為要從最大的堆拿，而且最大堆比他的一半多。。。但是其實他是讓求最大堆拿了多少個之后的異或值為0，這個就是必勝態 要知道兩個相同的數異或為0，即求最大值-最大值^其他所有值的異或值 #include <stdio.h> #include <algorithm> using namespace std; typedef long long LL; int main() {int n;while(~scanf("%d",&n)){LL ma=0,s=0,p;for(int i=1;i<=n;i++){scanf("%lld",&p);ma=max(ma,p);s^=p;}printf("%lld\n",ma-(s^ma));}return 0; }

3358: 石子游戲-A??

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 24 ? ? ? ?? ? Accepted:14

Description

甲乙兩人面對若干堆石子，其中每一堆石子的數目可以任意確定。例如圖1所示的初始局面：共n=3堆，其中第一堆的石子數a1=3，第二堆石

子數a2=3，第三堆石子數a3=1。



* *?
* *
* * *
3 3 1
圖(1)



兩人輪流按下列規則取走一些石子，游戲的規則如下：
1.每一步應取走至少一枚石子；
2.每一步只能從某一堆中取走部分或全部石子；
3.如果誰無法按規則取子，誰就是輸家。

如果甲乙兩人都采取最優的策略,請問,是甲必勝還是乙必勝.

Input

第一行包含一個正整數T,表示有多少個測試數據.
每組測試數據的第一行包含正整數N,表示有多少堆石頭. 接下去一行有N個正整數,表示每堆石頭的個數, 1<=N<=10000, 每堆石頭的數量在Int范圍內.

Output

每組測試數據輸出一行,如果甲存在必勝策略,輸出"Win",否則輸出"Lost"

Sample Input

?

1
3
3 3 1

Sample Output

?Win

兩個人輪流取石子，讓你找甲是否存在必勝策略，那就是異或值是不是0了

#include<stdio.h> int main() {int n,t;scanf("%d",&t);while(t--) {scanf("%d",&n);int s=0,m;while(n--) {scanf("%d",&m);s^=m;}printf("%s\n",s?"Win":"Lost");}return 0; }

下面這份代碼的原理我忘了，真是個坑。。。就是排序后把少進行了一遍循環？

大概意思是這樣的，讓兩個相對小的堆進行NIM操作，那么我肯定回拿對方的全部，對面肯定會拿一個，這樣剩下的最多才能為其他場的異或為0做貢獻

就是把他分為有限個二元組博弈

#include <stdio.h> #include <algorithm> using namespace std; int T,n,a[10010]; int main() {scanf("%d",&T); while(T--) {scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+1+n); int t=0,h=1; if(n%2)t=a[1]-1,h++; for(int i=h;i<=n;i+=2) t^=(a[i+1]-a[i]-1); if(t)printf("Win\n"); else printf("Lost\n");} return 0; }

3359: 石子游戲-B??

Time Limit(Common/Java):1000MS/3000MS ? ? Memory Limit:65536KByte
Total Submit: 18 ? ? ? ?? ? Accepted:10

Description

甲乙兩人面對若干堆石子，其中每一堆石子的數目可以任意確定。例如圖1所示的初始局面：共n=3堆，其中第一堆的石子數a1=3，第二堆石子數a2=3，第三堆石子數a3=1。



* *?
* *
* * *
3 3 1
圖(1)



兩人輪流按下列規則取走一些石子，游戲的規則如下：
1.每一步只能從某一堆中至少要取走一個石子,最多m個；
2.如果誰無法按規則取子，誰就是輸家。


如果甲乙兩人都采取最優的策略,請問,是甲必勝還是乙必勝.

Input

第一行包含一個正整數T,表示有多少個測試數據.
每組測試數據的第一行包含正整數N,m,表示有多少堆石頭. 接下去一行有N個正整數,表示每堆石頭的個數, 1<=N<=10000, 1<=m<=10000每堆石頭的數量在Int范圍內.

Output

每組測試數據輸出一行,如果甲存在必勝策略,輸出"Win",否則輸出"Lost"

Sample Input

1
2 3
4 4

Sample Output

?Lost

?

這個是最多拿k個的，那就拿到不能拿k個，回到以前的版本啊

#include <stdio.h> int a[10010]; int main() {int t; scanf("%d",&t); while(t--){int n,m;scanf("%d%d",&n,&m);scanf("%d",&a[0]);a[0]%=m+1;for(int i=1;i<n;i++){scanf("%d",&a[i]);a[i]=(a[i]%(m+1))^a[i-1];}if(!a[n-1])printf("Lost\n");else printf("Win\n"); } return 0; }

?

?

轉載于:https://www.cnblogs.com/BobHuang/p/7198017.html

總結

以上是生活随笔為你收集整理的acm之简单博弈 Nim Bash Wythoff的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。