博弈论

2018-04-12 19:30:32


这个目前用不到,先放在这里,以后再学

nim游戏

甲,乙两个人玩Nim取石子游戏。

nim游戏的规则是这样的:地上有n堆石子(每堆石子数量小于10000),每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取完,不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手,且告诉你这n堆石子的数量,他想知道是否存在先手必胜的策略。

输入格式: 第一行一个整数T<=10,表示有T组数据

接下来每两行是一组数据,第一行一个整数n,表示有n堆石子,n<=10000;

第二行有n个数,表示每一堆石子的数量

输出格式: 共T行,如果对于这组数据存在先手必胜策略则输出"Yes",否则输出"No",不包含引号,每个单词一行。

解法:

裸的NimmGame

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[10001];
int Nimm_Game(int n){
    int flag=0;
    for(int i = 1;i<=n;i++){
        flag^=a[i];
    }
    if(flag) return 1;
    return 0;
}
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        if(Nimm_Game(n)) printf("Yes\n");
        else printf("No\n");
        memset(a,0,sizeof(a));
    }
    return 0;
} 


#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

const int N=1e8+3;

//巴什博奕:只有一堆n个物品,两人轮流从中取出(1~m)个 
int Bash_Game(int n,int m){
    if(n%(m+1)!=0) return 1;
    return 0;
}

//尼姆博奕:有n堆,每堆有a[i]>0个物品,依旧是两人轮流取 
int a[N];
int Nimm_Game(int n){
    int flag=0;
    for(int i = 1;i<=n;i++) flag^=a[i];
    if(flag) return 1;
    return 0;
}
//如果是n非常大,且每一堆物品的数量是连续的整数的情况
//需要考虑连续的整数的异或和 
int  xor_n(int n){
    int t = n & 3;
    if(t & 1) return t / 2 ^ 1;
    return t / 2 ^ n;
}
int Special_Nimm_Game(int n){
//  int flag=0;
//  for(int i = 1;i<=n;i++){
//       flag^=xor_n(a[i]);
//  }
//  if(flag) return 1;
    if(xor_n(n)) return 1;
    return 0;
}

int cnt;
int main(){
    int n=1;
    for(int i = 1;i<=1000001;i++) a[i]=i;
    while(n<=1000000){
        n++;
        if(Nimm_Game(n)==Special_Nimm_Game(n)) continue;
        cnt=1;
    }
    if(cnt){
        puts("Wrong");
        return 0;
    }
    puts("Yes");
    return 0;
}