CF1149Etj

FiraCode · 2022-12-02 21:17:20 · 题解

题解思路

首先，先对原图进行拓扑排序。

我们求出每个点的 SG 值。

那么 u 点的 SG 值，即：SG(u) = \operatorname{mex}_{v\in son_u}(SG(v))。

然后求出 sum_x = \operatorname{xor}_{SG(u) = x} a_u

那么先手必赢当且仅当存在 sum_x 非零。

那么我们就找到最大的 i 使得 sum_x 非零。

然后对于 i，当有一个 u 满足，SG_u=i 且 w_u \oplus sum_i < w_u，就是存在一个满足条件的 u。

那么就修改 w_i，然后输出就可以了。

AC CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
int w[N];//读入的数组
int d[N];//度数，topsort时要用的度数
int SG[N], sum[N];//这个分别就是SG函数，和SG(x)=i的w_i之和
vector<int> e[N], p;//存边的，p是topsort的顺序
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        d[v] ++;
        e[u].push_back(v);
    }
    //================topsort================
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!d[i])
            q.push(i);
    while (q.size()) {
        int t = q.front();
        q.pop();
        p.push_back(t);
        for (auto v : e[t])
            if (!--d[v])
                q.push(v);
    }
    //================topsort end================
    for (int i = p.size() - 1; i >= 0; --i) {//计算SG函数
        set<int> mex;
        for (auto v : e[p[i]])
            mex.insert(SG[v]);
        for (int j = 0; ; ++j) {
            if (!mex.count(j)) {
                SG[p[i]] = j;
                break;
            }
        }
    }
    for (int i = n; i; --i)
        sum[SG[i]] ^= w[i];//计算SG值为SG(i)的w[i]的异或和
    for (int i = n - 1; i >= 0; --i) {
        if (sum[i]) {//这个值不是0
            puts("WIN");//一定能赢。
            for (int u = 1; u <= n; ++u) {
                if (SG[u] == i && (w[u] ^ sum[i]) < w[u]) {
                    w[u] ^= sum[i];
                    for (auto v : e[u]) {
                        w[v] ^= sum[SG[v]];
                        sum[SG[v]] = 0;//只有一次修改，所以修改完了要初始化成0。
                    }
                    for (int j = 1; j <= n; ++j) printf("%d ", w[j]);
                    return 0;
                }
            }
        }
    }
    puts("LOSE");
    return 0;
}