简单博弈论入門

admin

(2),在遊戲举行的肆意時刻，可以履行的正當举措與轮到哪位玩家無關

(3),不克不及举措的玩家判负

   则称该遊戲為一個公允组合遊戲。

值得注重的是，尼姆遊戲（NIM）属於公允组合遊戲，但常見的棋類遊戲，好比围棋就

不是公允组合遊戲，由於围棋交兵两边别離只能落黑子和白子，输赢断定也比力賣力，不知足

前提2和3。

1. 标题描写
   
2. 给定n堆石子，两位玩家轮番操作，每次操作可以從肆意一堆石子中拿走肆意数目的石子（可以拿完，但不得不拿），最後没法举行操作的人视為失败。
   
3. 問若是两人都采纳最優计谋，先手是不是必胜。
   
4. 比方：有两堆石子，第一堆有2個，第二堆有3個，先手必胜。
   
5. 操作步調：
   
6. 1. 先手從第二堆拿走1個，此時第一堆和第二堆数量不异
   
7. 2. 不管背工怎样拿，先手都在此外一堆石子中取走不异数目的石子便可

複製代碼

在解决這個問题以前，先来领會两個名词：

结论

假如n堆石子，石子数量别離是a1,a2,…,an，若是a1⊕a2⊕..⊕an≠磁鐵，0，先手必胜；不然先手必

败。

证實：

1. 操作到最後時，每堆石子数都是0，0⊕0⊕…0=0
   
2. 在操作進程中，若是 a1⊕a2⊕…⊕an=x≠0。那末玩家必定可以經由過程拿走某一堆若干個石子将异或成果變線上娛樂，成0
   
3. 证實：無妨設x的二進制暗示中最高一名1在第k位，那末在a1,a2,…,an中，必定有一個数ai，它的第k為時1，且
   
4. ai⊕x<ai ，那末從第i堆石子中拿走(ai−ai⊕x)個石子，第i堆石子還剩ai−(ai−ai⊕x)=ai⊕x，此時
   
5. a新店汽車借款 ,1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0

複製代碼

基於上述三個证實：

1. 若是先手面临的場合排場是a1⊕a2⊕…⊕an≠0，

那末先手总可以經由過程拿走某一堆若干個石子，将場合排場酿成a1⊕a2⊕…⊕an=0。如斯反复，最後必定是背工面對终极没有石子可拿的状况。先手必胜。

2. 若是先手面临的場合排場是a1⊕a2⊕…⊕an=0，

那末不管先手怎样拿，城市将場合排場酿成a1⊕a2⊕…⊕an≠幸運飛艇,0，那末背工总可以經由過程拿走某一堆若干個石子，将場合排場酿成a1⊕a2⊕…⊕an=0。

如斯反复，最後必定是先手面對终极没有石子可拿的状况。先手必败。

1. #include <iostream>
   
2. #include <cstdio>
   
3. using namespace std;
   
4. int main(){
   
5. int n;
   
6. scanf("%d", &n);
   
7. int res = 0;
   
8. for(int i = 0; i < n; i++) {
   
9. int x;
   
10. scanf("%d", &x);
    
11. res ^= x;
    
12. }
    
13. if(res == 0) puts("No");
    
14. else puts("Yes");
    
15. }

複製代碼