ZOJ 3964Yet Another Game of Stones 扩展尼姆博弈

题意

给n堆石头，每堆石头有a个数量和b性质。Alice和Bob玩游戏，每次只能在一堆中取任意多个石头。

  • b=0，Alice随便取。
  • b=1，Alice只能取奇数个。
  • b=2，Alice只能取偶数个。

取最后一个win。

思路

我们知道，如果所有的石头的b都为0，那么就是简单的尼姆博弈，那么我们把b不为0的给限制出来。

  1. 存在一堆b=2，并且a为奇数，则Bob必胜。
  2. 存在两堆及以上b=2或b=1且a>1，则Bob必胜。
  3. 如果只存在一堆b=2，则Alice为了胜利，必须先把这堆拿完(否则Bob可以拿到奇数个然后必胜)，则转化为Bob先手的尼姆博弈。
  4. 如果只存在一堆b=1，择Alice为了胜利，必须拿完(奇数)或者拿a-1个(偶数)，然后转化为Bob先手的尼姆博弈。
  5. 全为b=0，简单尼姆博弈。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
##include "bits/stdc++.h"
using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        int a = 0, b = 0; // 奇数、偶数
        vector<int> v(n + 1), c(n + 1);
        for(int i = 1;i <= n; i++) cin >> v[i];
        bool flag = 1;
        int p = 0, q = 0;
        for(int i = 1;i <= n; i++) {
            cin >> c[i];
            if(c[i] == 1) {
                if(v[i] > 1) a++;
            }
            else if(c[i] == 2) {
                if(v[i] % 2) flag = 0;
                else b++;
            }
        }
        if(!flag  (a + b > 1)) cout << "Bob" << endl;
        else {
            int ans = 0;
            if(!a && !b) {
                for(int i = 1;i <= n; i++) ans ^= v[i];
                cout << (ans ? "Alice" : "Bob") << endl;
            }
            else if(a) {
                for(int i = 1;i <= n; i++) {
                    if(c[i] == 1 && v[i] > 1) ans ^= (v[i] % 2 ? 0 : 1);
                    else ans ^= v[i];
                }
                cout << (ans == 0 ? "Alice" : "Bob") << endl;
            }
            else if(b) {
                for(int i = 1;  i <= n; i++) {
                    if(c[i] != 2) ans ^= v[i];
                }
                cout << (ans == 0 ? "Alice" : "Bob") << endl;
            }
        }
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/05/zoj-3964yet-another-game-of-stones/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！