蓝桥杯练习题——博弈论

1.必胜态后继至少存在一个必败态
2.必败态后继均为必胜态

Nim游戏

思路

2 3，先手必赢，先拿 1，然后变成 2 2，不管后手怎么拿，先手同样操作，后手一定先遇到 0 0
a1 ^ a2 ^ a3 … ^ an = 0，先手必败，否则先手必胜

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int res = a[1];
    for(int i = 2; i <= n; i++) res ^= a[i];
    if(res == 0) cout<<"No";
    else cout<<"Yes";
    return 0;
}

// 求先手必胜第一次怎么拿
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int res = a[1];
    for(int i = 2; i <= n; i++) res ^= a[i];
    if(res == 0) cout<<"lose";
    else{
        for(int i = 1; i <= n; i++){
            if((a[i] ^ res) >= a[i]) continue;
            printf("第%d堆 拿%d个\n", i, (a[i] - (a[i] ^ res)));
            a[i] = a[i] ^ res;
            break;
        }
    }
    for(int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}

台阶-Nim游戏

思路

如果拿偶数的台阶，你拿多少下去，我就拿多少下去，所以只需要看奇数台阶
如果奇数位 a1 ^ a3 ^ a5 ^ … ^ an = 0，先手必败

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int res = a[1];
    for(int i = 3; i <= n; i += 2){
        res ^= a[i];
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}

集合-Nim游戏

思路

如果 SG(x1) ^ SG(x2) ^ SG(x3) ^ … ^ SG(xn) = 0，先手必败

能到 0 那就是 1，能到 1 那就是 0，同时能到 1 和 0，那就是 2

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110, M = 1e4 + 10;
int a[N], b[M];
int n, m;

int sg(int x){
    if(b[x] != -1) return b[x];
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        int t = a[i];
        if(x >= t) s.insert(sg(x - t));
    }
    for(int i = 0; ; i++){
        if(!s.count(i)){
            b[x] = i;
            return b[x];
        }
    }
}

int main(){
    memset(b, -1, sizeof(b));
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    int res = 0, x;
    for(int i = 0; i < m; i++){
        scanf("%d", &x);
        res ^= sg(x);
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}

拆分-Nim游戏

思路

一个数分成两个数，再异或

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110;
int b[N];
int n;

int sg(int x){
    if(b[x] != -1) return b[x];
    unordered_set<int> s;
    for(int i = 0; i < x; i++){
        for(int j = 0; j <= i; j++){
            s.insert(sg(i) ^ sg(j));
        }
    }
    for(int i = 0; ; i++){
        if(!s.count(i)){
            b[x] = i;
            return b[x];
        }
    }
}

int main(){
    memset(b, -1, sizeof(b));
    scanf("%d", &n);
    int res = 0, x;
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        res ^= sg(x);
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}