忽然發(fā)現(xiàn)博弈論是個很好玩的東西哎

之前假期學長講課的時候就發(fā)現(xiàn)這種必勝的戰(zhàn)略可以用來坑人做題

這兩天終于做了第一道博弈論的題，寫篇博客紀念一下

靈感來源：洛谷P1247

Pre-scene

眾所周知，李明和Jenny都喜歡Danny，為了爭奪Danny的所有權(quán)，他們決定玩一個游戲。規(guī)則是這樣的：

有k堆撲克牌（不成套），兩人輪流從某一堆中拿出x張牌，不能不拿，也不能跨堆拿牌，拿走最后一張(堆)牌的一方獲勝。

命運當然是不公平的，李明來向你請教有沒有必勝的方法，你聰明的，能告訴他么

---

?

0X10 ?知識

先來了解一下，什么是Nim博弈

---

?

通常的Nim游戲的定義是這樣的：有若干堆石子，每堆石子的數(shù)量都是有限的，合法的移動是“選擇一堆石子并拿走若干顆（不能不拿）”，如果輪到某個人時所有的石子堆都已經(jīng)被拿空了，則判負（因為他此刻沒有任何合法的移動）。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 　　　　　　　　　　　　? ——百度百科?

---

?

了解Nim游戲之后，我們會發(fā)現(xiàn)這是一個經(jīng)典的ICG游戲（不要問我什么是ICG因為我百度百科也不知道）

顯然游戲有兩種局面，先手必敗和先手必勝，我們分別定義他們?yōu)镻-position和N-position兩種，其中P代表Previous，N代表Next，那么我們可以得出，從N-position轉(zhuǎn)移而來的一定是P-position，反之也成立。

0X20 ?簡單的證明

我們先來手玩一組小數(shù)據(jù)，一共有2堆石子，每一堆都有3個，你是先手的話，會怎么拿？由規(guī)則我們知道，玩家的目標是拿走最后一個石子，所以先手的你一定不會把某一堆全部拿走，因為如果這樣，后手將會拿走另一堆，先手必敗；但是如果你先拿1個，后手會跟著你從另一堆也拿一個，你拿2個，后手仍可以做和你一樣的操作，先手必敗。至此我們發(fā)現(xiàn)，（3，3）是一個P-position的局面。

推論：1.當a1^a2^a3^……a^n=0時，為P-position，即先手必敗。

? ? ? ? ?2.當a1^a2^a3^……a^n!=0時，一定存在某個移動，使得局面變成一個P-position，即此局面為N-position。

0X30 ?實現(xiàn)

直接異或運算即可，代碼過于簡單就不放了。

0X40 ?題解

傳送門

了解了上述知識后，這道題幾乎就是一個裸的板子了，就是加了一個輸出怎么取和取完的狀態(tài)而已，這也很好實現(xiàn)。

0X41 ?怎么取

由于我們發(fā)現(xiàn)異或和不等于0，我們就要考慮怎么取使得其等于0了。

設(shè)k=a1^a2^a3^……a^n，因為k!=0，而顯然k^k=0，所以要使a1^a2^a3^……a(n-1)^an^k=0，只需要把其中一個ai變成ai^k即可，又因必須要取，可得ai^k<ai

0X42 ?取完的狀態(tài)

直接更改即可

0X43 ?代碼

1 // 2 // main.cpp 3 // Luogu 4 // 5 // Created by gengyf on 2019/5/16. 6 // Copyright ? 2019 yifan Geng. All rights reserved. 7 // 8 9 #include <cstdio> 10 int n; 11 int a[500005]; 12 int main(){ 13 scanf("%d",&n); 14 int check=0; 15 for(int i=1; i<=n; i++){ 16 scanf("%d",&a[i]); 17 check^=a[i]; 18 } 19 if(!check){ 20 printf("lose\n"); 21 return 0; 22 } 23 for(int i=1; i<=n; i++){ 24 if((check^a[i])<a[i]){ 25 printf("%d %d\n",a[i]-(check^a[i]),i); 26 for(int j=1; j<=n; j++) 27 if(j!=i) 28 printf("%d ",a[j]); 29 else printf("%d ",check^a[i]); 30 break; 31 } 32 } 33 return 0; 34 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/gengyf/p/10878126.html

總結(jié)

以上是生活随笔為你收集整理的Nim博弈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。