博弈论

如果没有修改后继城市这个操作，就是一个$nim$游戏

现在将整个图的$sg$函数求出 把所有点按$sg$函数分类 设一类点的编号为$sg$函数值 每一类点有以下性质

1.这类点之间互相没有直接连边

2.这类点能到达所有编号小于该类点的集合中的至少一点

以上根据$sg$函数性质可以直接推出

设每类点的$sum$为所有$h$的异或和 根据$nim$游戏 如果所有类的$sum$都为$0$ 那么先手必输 因为如果先手修改某个点的$h$以及后继 那么同类点中肯定存在某个点可以通过同样的操作使得$sum$重新变回$0$ 直到不可操作

如果$sum$存在不为$0$ 那么先手必胜 找到编号最大的那类点中某点 修改该点及后继点的$h$使得$sum$全部为$0$即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int h[maxn], in[maxn], q[maxn], sg[maxn], sum[maxn], vis[maxn];
vector<int> G[maxn];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    for(int i = 1; i <= m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v);
        ++in[v];
    }
    int l = 1, r = 0;
    for(int i = 1; i <= n; ++i) if(!in[i]) q[++r] = i;
    while(l <= r) {
        int u = q[l++];
        for(int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if(!--in[v]) q[++r] = v;
        }
    }
    for(int i = n; i; --i) {
        int u = q[i];
        for(int j = 0; j < G[u].size(); ++j) {
            int v = G[u][j];
            vis[sg[v]] = 1;
        }
        for(; vis[sg[u]]; ++sg[u]);
        for(int j = 0; j < G[u].size(); ++j) {
            int v = G[u][j];
            vis[sg[v]] = 0;
        }
    }
    for(int i = 1; i <= n; ++i) sum[sg[i]] ^= h[i];
    int p = -1;
    for(int i = n; ~i; --i) if(sum[i]) {
        p = i;
        break;
    } 
    if(p == -1) {
        puts("LOSE");
        return 0;
    }
    puts("WIN");
    for(int i = 1; i <= n; ++i) if(sg[i] == p) {
        if((sum[p] ^ h[i]) > h[i]) continue;
        h[i] ^= sum[p]; 
        for(int j = 0; j < G[i].size(); ++j) {
            int v = G[i][j];
            h[v] ^= sum[sg[v]];
            sum[sg[v]] = 0;
        }
        break;
    }
    for(int i = 1; i <= n; ++i) printf("%d ", h[i]);
    return 0;
} 

View Code