博弈论总结

博弈

anti-nim

nim游戏，不能操作者胜。
先手必胜当且仅当：
1.所有石子都为1，且有偶数堆。
2.至少一堆数量大于1，sg函数异或不为0

那么对于所有的anti-sg游戏，先手必胜当且仅当：
1.sg函数异或为0且不存在sg>1
2.sg函数异或不为0且至少有一个sg>1

every-sg

每一轮里要操作所有能操作的子游戏。（nim游戏每一轮要从所有堆里取石子）
由于胜负是由最后一个结束的游戏的胜负决定的，因此先手想让自己能赢的游戏尽可能的延长。
定义step
1.若u为终止状态，则step[u]=0
2.若sg[u]=0，则step[u]=min(step[v])+1
3.若sg[u]=1，则step[u]=max(step[v])+1,sg[v]=0。
先手必胜当且仅当每个子游戏的最大step为奇数。（step）的奇偶性等价于sg函数是否为0。

翻硬币游戏

有一些翻硬币的，并且每一轮操作的最右边的硬币一定是从正面变成反面，谁不能翻谁输。

局面的sg值为仅有每个正面朝上的硬币时sg函数的异或。

zjoi 染色

删边游戏

树的删边游戏

给定一棵有根树，每次可以选择一条边删去，把没有根的部分扔掉，不能删的输。

叶子的sg为0，非叶子的sg为所有叶子的sg+1的异或。

图的删边游戏

随便找一个偶环，缩成一个点；随便找一个奇环，缩成一个点，再从这个点向外连一个点。迭代进行，直到变成一棵树，做树上删边游戏。

二分图博弈

一类博弈问题，基于以下条件：

1.博弈者人数为两人，双方轮流进行决策。
2.博弈状态（对应点）可分为两类（状态空间可分为两个集合），对应二分图两边（X集和Y集）。任意合法的决策（对应边）使状态从一类跳转到另一类。（正是由于这个性质使得问题可以用二分图描述）
3.不可以转移至已访问的状态。（不可重复访问点）
4.无法转移者判负。

这类问题相当于从二分图指定起点开始轮流移动，不可重复访问点，无法移动判负 。

不妨设起点在二分图的X集中，那么先手只能从X集移动到Y集，后手只能从Y集移动到X集。一次游戏过程对应一条路径 。若最后停留在X集且无法移动则先手负，停留在Y集则后手负。
考虑该二分图的某个最大匹配。（注意可能存在多个匹配相同的最大匹配）
若起点s∈X不属于该最大匹配。则先手所转移到的点y∈Y一定属于最大匹配（否则s-y是一个匹配，与最大匹配矛盾）。后手沿着最大匹配的边走即可，终点t（指无法从t再走一步）一定不可能在Y集中（否则，若t在Y集中，s-…-t为一增广路，与最大匹配矛盾）。因此先手必败，后手必胜。
若起点s∈X属于该最大匹配。则将s从图中删除，再求图的最大匹配。若最大匹配数不变，则s还是不属于某最大匹配，先手必败。否则该图的任意最大匹配都包含s，则先手沿着最大匹配的边走即可，根据上面的分析，先手必胜。

超现实数与不平等博弈

开始了

大概要算一个 Alice 比 Bob 多走几步这样一件事情，本质上求了一个局面的超现实数是多少。

有环图博弈问题

1

给定一张有向图（可能有环），上面有一枚棋子。两人轮流移动，不能操作者输，判断先手胜/败/平。

首先像 DAG 一样从终点向前递推，即将负点的前驱都标记为胜点，如果某个点只能到达胜点那他就是负点。但因为有环的存在，某些节点可能不会被处理到，那这些点都是平局。

简要证明：考虑一个没有被处理的点的后继，只能是没有被处理的点或者没有被处理的点+胜点。显然不会有人主动移动到胜点，因此大家都会在未处理点中转圈圈。

2

Jewel Game
https://contest.ucup.ac/contest/1207/problem/6331

有环图，不只求胜负，而是要求得分，边有边权。分析方法类似。注意到任意一个环内边权为零，因此我们可以分层考虑这个图，对于某一层，每一轮首先标记那些已经能被确定的点，然后从所有转移中找最大的那条边，标记起点，直到不能操作为止，接着处理下一层。

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 33;

vector<int> e[N], sta[N], b[N];

int pos[N], w[N], f[(1<<10)+2][33][33], id[N], du[N][N], vis[N][N], chong[(1<<10)+2][N];
P tmp[1025];

queue <P> q;
priority_queue<P> ksj;

int main() {
    int n, m, A, B;
    scanf("%d%d%d%d", &n, &m, &A, &B);
    rep (i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        b[v].push_back(u);

    }
    int k; scanf("%d", &k);
    rep (i, 1, k) {
        scanf("%d%d", &pos[i], &w[i]);
        id[pos[i]] = i;
    }
    int mx = (1<<k) - 1;
    rep (s, 1, mx) {
        rep (i, 1, k) if ((s>>i-1) & 1) {
            chong[s][pos[i]] = 1;
        }
    }
    rep (s, 1, mx) {
        sta[__builtin_popcount(s)].push_back(s);
    }
    rep (s, 1, mx) {
        rep(i, 1, n) {
            rep (j, 1, n) {
                f[s][i][j] = -1e9;
            }
        }
    }
    rep (_, 1, k) {
        for (auto s: sta[_]) {
            auto g = f[s];
            while (!ksj.empty()) ksj.pop();
            rep (i, 1, n) {
                rep (j, 1, n) if (!chong[s][i] && !chong[s][j]) {
                    int top = 0;
                    for (auto v: e[i]) {
                        int p = id[v];
                        if ((s>>p-1) & 1) {
                            int t = s ^ (1<<p-1);
                            g[i][j] = max(g[i][j], -f[t][j][v] + w[p]);
                            tmp[++top] = P(-f[t][j][v] + w[p], i * n + j - 1);
                        } else {
                            du[i][j]++;
                        }
                    }
                    if (du[i][j] == 0) {
                        vis[i][j] = 1;
                        q.push(P(i, j));
                    } else {
                        while (top) ksj.push(tmp[top--]);
                    }
                }
            }
            while (1) {
                while (!q.empty()) {
                    auto [i, j] = q.front();
                    q.pop();
                    for (auto v: b[j]) { //previous: (v, i)
                        if (chong[s][v] || chong[s][i]) continue;
                        if (vis[v][i]) continue;
                        du[v][i]--;
                        g[v][i] = max(g[v][i], -g[i][j]);
                        if (du[v][i] == 0) {
                            vis[v][i] = 1;
                            q.push(P(v, i));
                        } else {
                            ksj.push(P(-g[i][j], v*n + i - 1));
                        }
                    }
                }
                if (ksj.empty()) break;
                auto [v, t] = ksj.top();
                ksj.pop();
                if (v < 0) break;
                int i = t/n, j = t%n+1;
                if (vis[i][j]) continue;
                vis[i][j] = 1;
                g[i][j] = v;
                q.push(P(i, j));
            }

            rep (i, 1, n) {
                rep (j, 1, n) {
                    if (!vis[i][j]) g[i][j] = 0;
                    vis[i][j] = du[i][j] = 0;
                }
            }
        }
    }
    cout << f[mx][A][B];
    return 0;
}