题解：Election Promises

· · 题解

可以感受到满外向树是比较简单的，所以先思考满外向森林的情况。（后文深度表示离出度为 0 的点的距离）

假如只有一些深度为 1 的点，显然就是取石子游戏。

假如上面接上一些深度为 2 的点，通过手玩几个样例，可以发现当深度为 2 的点异或和 和 深度为 1 的点异或和 全都为 0 时，先手必输，否则先手必胜。

最大深度为 3 的情况，假设深度为 2 的点异或和 s2 为零，深度为 1 的点异或和为 s1，深度为 3 的点异或和为 s3。若 s1 = 0 时显然先手必胜。当 s1 等于 s3 时，不管先手如何操作，后手都可以使局面归于 s1 等于 s3 的情况。当 s1 不等于 s3 时，先手可以通过一次操作使 s1 = s3。当 s2 不为零时，先手可以通过一次操作使 s1 = s3, s2 = 0 所以可以知道，当 s1 \oplus s3 和 s2 都为零时，先手必输，否则先手必胜。

类比着推到最大深度为 4 和最大深度为 5 的情况，可以得到相似的结论。

那么可难以看出，当奇数深度异或和 和 偶数深度异或和 都为零时，先手必败，否则先手必胜。异或运算有一个很好的性质：当异或和不为零时，一定可以通过修改某个数使异或和为零，当异或和为零时则不行。需要凑出零时，当最大深度大于一时，一定存在点可以影响到奇数深度的点和偶数深度的点。所以可以证明。

但是当结论推广至 DAG 上怎么做呢？猜想也是要将节点分组然后求异或和。通过前面对结论的证明，分组相当于划分“阶段”。某一个阶段可以影响到在他之前的所有阶段，同时出度为 0 的点是最靠前的阶段。那么可难以想到钦定出度为 0 的阶段为 0，其他节点的阶段为它能到达的节点阶段的 mex 和。然后套用之前的证明即可。

博弈题目的思考一开始需要手玩找规律（然后思考过程就没什么头绪），然后通过构造 必胜局面 和 必败局面 来解决问题。同时对结论正确性的证明也可以对结论的推广有启示作用。

#include <bits/stdc++.h>
using namespace std;
const int MAXSG = 1000;

int n, m;
int h[200002];
int du[200002];
vector<int> vec[200002], fvec[200002];

int have[MAXSG+2], SG[200002];
queue<int> q;
int sum[MAXSG+2];

int hpie[200002];

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);
        fvec[v].push_back(u);
        vec[u].push_back(v);
        du[u]++;
    }

    for(int i=1;i<=n;i++) 
        if(du[i] == 0) q.push(i);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int o=0;o<vec[u].size();o++){
            have[SG[vec[u][o]]]++;
        }
        while(have[SG[u]] > 0) SG[u]++;
        for(int o=0;o<vec[u].size();o++){
            have[SG[vec[u][o]]]--;
        }
        for(int o=0;o<fvec[u].size();o++){
            int v = fvec[u][o];
            du[v]--;
            if(du[v] == 0) q.push(v);
        }
    }

    for(int i=1;i<=n;i++){
        sum[SG[i]] ^= h[i];
    }
    for(int o=MAXSG;o>=0;o--){
        if(sum[o] != 0) {
            printf("WIN\n");
            for(int i=1;i<=n;i++) hpie[i] = h[i];
            for(int i=1;i<=n;i++){
                if(SG[i] == o && (sum[o] ^ h[i]) < h[i]){
                    hpie[i] = sum[o] ^ h[i];
                    for(int j=0;j<vec[i].size();j++){
                        int v = vec[i][j];
                        if(sum[SG[v]] > 0){
                            hpie[v] = sum[SG[v]] ^ h[v];
                            sum[SG[v]] = 0;
                        }
                    }
                    for(int i=1;i<=n;i++) printf("%d ",hpie[i]);
                    return 0;
                }
            }
        }
    }
    printf("LOSE\n");

    return 0;
}