博弈论

尼姆游戏

\(n\) 堆石子，每次取 \(\geq1\) 颗，只能取 \(1\) 堆。先手必败条件 \([a_1\oplus a_2\oplus...\oplus a_n==0]\)

\(n\) 堆石子，每次取 \([1,m]\) 颗，只能取 \(1\) 堆。先手必败条件 \([\left(a_1\mod(m+1)\oplus a_2\mod(m+1)\oplus...\oplus a_n\mod(m+1)\right)==0]\)

\(n\) 堆石子，每次取 \(\geq1\) 颗，只能取 \([1, k]\) 堆。先手必败条件 将 \(a\) 二进制分解，每一位的 \(1\) 的数量模 \(k+1\) 为 \(0\)

威佐夫游戏

\(2\) 堆石子，每次在任意 \(1\) 堆中取 \(\geq1\) 颗，或同时从 \(2\) 堆中都取 \(\ge1\) 颗。先手必败条件为 \((\lfloor\dfrac{1+\sqrt{5}}{2}\cdot{}k\rfloor,\lfloor\dfrac{3+\sqrt{5}}{2}\cdot{}k\rfloor)\) \(k\geq1\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int a, b;
while (cin >> a >> b) {
    if (a > b) swap(a, b);
    int k = (b - a) * (1 + sqrt(5)) / 2;
    if (a == k) {
        cout << 0 << "\n";
    } else {
        cout << 1 << "\n";
    }
}

 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

int a, b;
while (cin >> a >> b) {
    if (a == 0) break;
    if (a > b) swap(a, b);
    int k = (b - a) * (1 + sqrt(5)) / 2;
    if (a == k) {
        cout << 0 << "\n";
    } else {
        cout << 1 << "\n";
        for (int i = 1 ; i <= a ; i++) {
            int n = a - i, m = b - i;
            if (n == k) {
                cout << n << " " << m << "\n";
            }
        }
        for (int i = b ; i >= 0 ; i--) {
            int n = a, m = i;
            if (n > m) swap(n, m);
            k = (m - n) * (1 + sqrt(5)) / 2;
            if (n == k) {
                cout << n << " " << m << "\n";
            }
        }
    }
}

\(2\) 堆石子，每次在任意 \(1\) 堆中取 \(\geq1\) 颗，或在第 \(1\) 堆拿 \(x\) 颗，在第 \(2\) 堆拿 \(y\) 颗，且 \(|x-y|< d\)。先手必败条件为 \((\lfloor\dfrac{2-d+\sqrt{d^2+4}}{2}\cdot{}k\rfloor,\lfloor\dfrac{2+d+\sqrt{d^2+4}}{2}\cdot{}k\rfloor)\)

斐波那契博弈

\(1\) 堆石子，先手第一次取 \([1,n)\) 颗，令前一次取了 \(m\) 颗，接下来每次取 \([1,2*m]\) 颗。先手必败条件为斐波那契数。

阶梯博弈

阶梯尼姆博弈: \(n\) 堆石头，每次可以取走第 \(i\) 堆 \(\geq1\) 颗石子，并放到 \(i-1\) 堆，如果是第 \(1\) 堆，则直接取走。先手必败条件为对编号为奇数的堆做尼姆游戏，即\([a_1\oplus a_3\oplus...\oplus a_n==0]\)