02-博弈.md

博弈

SG函数

• 所有后继状态的$MEX$

多个游戏组合

• 前提：多个公平游戏且游戏之间相互独立
• 结论：每个游戏的$SG$值异或和为$0$则先手必败，反之先手必胜

阶梯NIM

题面

$N$ 堆石子，两人轮流操作，一次操作为挑选一堆石子 $i$，将至少 $1$ 个石子移动至 $i-1$ 位置（$i=1$则被移出游戏），不能操作者输。

结论

相当于对所有奇数位置上的石子堆做 $NIM$ 游戏。即 $a_1\bigoplus a_3\bigoplus \dots =0 $，则先手必败

斐波那契博弈

题面

有一堆个数为$n(n\geq 2)$的石子，游戏双方轮流取石子，规则如下

• 先手不能在第一次把所有石子取完，至少取1颗
• 之后每次取石子数范围$[1, 2*a_{i-1}]$，$a_{i-1}$表示对手上一轮取石子的数量
• 取走最后一个石子的为赢家

结论

当$n$为$Fibonacci$数时，先手必败。

威佐夫博弈

题面

有两堆石子，两人分先后手按最优策略取石子，每次可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取的人输，给出两堆石子的数量$a$，$b$，分析胜负情况。

$Beatty$定理

设$x$，$y$是正无理数且 $1/x+1/y=1$。记$P$={ $\lfloor ix\rfloor$ | $i$为正整数}，$Q$={ $\lfloor iy\rfloor$ | $i$ 为正整数}，则$P$与$Q$是$N$+的一个划分，即$P\cap Q=\emptyset$且$P\cup Q=N+$（正整数集）。

$Beatty$定理与威佐夫博弈的关联

假设$x<y$且$P,Q$内数均按大小排序，$(P_i,Q_i)$构成第$i$种先手必败态（此处证略）。在朴素威佐夫博弈中，对于所有必败态势，$P_i$是当前最小的没有使用过的数，$Q_i=P_i+i$，即$\lfloor iy\rfloor=\lfloor ix\rfloor +i$，因为对任意正整数$i$均成立，可得$y=x+1$。因此解方程$1/x+1/(x+1)=1$可得$x=((1+\sqrt5)/2)$，因此有必败态通项$(\lfloor m(1+\sqrt5)/2 \rfloor, \lfloor m(3+\sqrt5)/2 \rfloor)$。

结论

假设$a<b$，当且仅当$(b-a)*(\sqrt5 + 1)/2=a$时先手必败

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    ll a, b;
    scanf("%lld%lld", &a, &b);
    if(a > b) swap(a, b);
    ll tmp = abs(a - b);
    ll ans = tmp * (1.0 + sqrt(5.0)) / 2.0;
    printf("%d\n", ans == a ? 0 : 1);
    return 0;
}

威佐夫博弈变种(HDU 6869)

题面变化

从两堆石子取同样多的石子改为从两堆石子中分别取$x$，$y$个石子，$|x-y|<=k$，$k$由题目给出。

Sol

设$(P_i,Q_i)$构成先手必败态，打表可得$P_i$是当前最小的没有使用过的数，$Q_i=P_i+(k+1)i$，套入$Beatty$定理，有$\lfloor iy\rfloor=\lfloor ix\rfloor +(k+1)i$，因为对任意正整数$i$均成立，可得$y=x+k+1$，解方程$1/x+1/(x+k+1)=1$可得$x=(1-k+\sqrt{k^2+2k+5})/2$，可求得结论中通项。

结论

所有的先手必败态为$(\lfloor m(1-k+\sqrt{k^2+2k+5})/2 \rfloor, \lfloor m(3+k+\sqrt{k^2+2k+5})/2 \rfloor)$，$k=0$即朴素威佐夫博弈。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {

    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b; double k;
        scanf("%d%d%lf", &a, &b, &k);
        double r1 = 1 - k + sqrt((k + 1) * (k + 1) + 4);
        double r2 = 3 + k + sqrt((k + 1) * (k + 1) + 4);
        if (a > b) swap(a, b);
        int m = (int) ceil(a * 2 / r1);
        int m2 = (int) ceil((a + 1) * 2 / r1);
        if (m == m2) {
            printf("1\n");
            continue;
        }
        assert(m + 1 == m2);
        if (b == (ll) floor(m * r2 / 2)) {
            printf("0\n");
        } else {
            printf("1\n");
        }
    }

    return 0;
}