本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}