博弈论

板子

SG 函数

const int maxn = 10000 + 100;
int n;
int Array[maxn], SG[maxn];
bool visit[maxn];
// maxn 为“石子”数，n 为 Array 数组大小，Array 数组需从小到大排序
void get_SG() {
    SG[0] = 0;
    for(int i = 1; i <= 10000; ++i) {
        memset(visit, 0, sizeof(visit));
        for(int j = 0; j < k; ++j) {
            if(i >= Array[j]) {
                visit[SG[i - Array[j]]] = true;
            }
        }
        for(int j = 0; j <= 10000; ++j) {
            if(!visit[j]) {
                SG[i] = j;
                break;
            }
        }
    }
}

巴什博弈

题目

一堆物品有 $n$ 个，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 $m$ 个，取走最后一个物品者获胜。

结论

当 $n\%(m+1)=0$ 时，先手必败，否则先手必胜。

威佐夫博奕

题目

有两堆物品，分别有 $a$ 个与 $b$ 个，两个人轮流取物品，每次可以从任意一堆中取走任意个物品，或者从两堆物品中取走任意多个相同数量的物品，每次最少取一个物品，取走最后一个物品者获胜。

结论

若 $b>a$， $a=\lfloor(b-a)\times\frac{\sqrt5+1}{2}\rfloor$，则先手必败，否则先手必胜。