CF1149E Election Promises 题解

· · 题解

题目大意：给定一张 n 个点 m 条边的有向图（不一定连通），每个点有一个权值 a_i，两人轮流进行操作，每次操作可以选择任意一个节点 u 并将其点权 减小 为一个非负整数，之后可以将所有节点 v\in\{v|\,\exists 有向边 u\rightarrow v\} 的权值 更改 为任意非负整数，最先不能操作者输，求先手有无必胜策略，若有则接下来输出第一次操作后能够确保获胜的每个节点的权值（1\le n\le 2\times10^5，0\le m\le 2\times10^5，时限 2s）。

我们发现这像一个 Nim 和有向图游戏的合成版，于是考虑计算 SG 值与 Nim 和。我们可以算出每一个点的 SG 值，令 f_x = \bigoplus\limits_{SG_p\ =\ x}a_p，当且仅当 \forall x,f_x = 0 时先手必败，否则先手必胜，我们用 N - position 和 P - position 来证明。

对于任意一个 P - position，即 \forall x,f_x = 0 时，任意修改都会使得 \exists x,f_x\neq 0，具体思路同 Nim 游戏。

对于任意一个 N - position，即 \exists x,f_x\neq 0 时，我们只需要找到最大的 x 使得 f_x\neq 0，并找到一个 u 使得 SG_u = x,a_u\oplus f_x < a_u（参考 Nim 游戏的证明，一定存在这样的 u），将 a_u\leftarrow a_u\oplus f_x，此时就将 f_x 清零了。而对于其它 f_y\neq 0(y < x)，由于 SG 值由 mex 得到，u 的后继中一定存在 v\in\{v|\ SG_v = y,f_y\neq 0,y < x\}，所以只要将 a_v\leftarrow a_v\oplus f_y 即可。

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#define maxn 200005
#define ll long long
using namespace std;
int n,m,u,v,deg[maxn]; ll mmax,a[maxn],sg[maxn],xxor[maxn]; queue<int> q; map<int,int> mp[maxn];
struct node{int to,nex;}g[maxn],g2[maxn]; int head[maxn],head2[maxn],cnt=0,cnt2=0;
void add(int from,int to){g[++cnt].to=to; g[cnt].nex=head[from]; head[from]=cnt;}
void add2(int from,int to){g2[++cnt2].to=to; g2[cnt2].nex=head2[from]; head2[from]=cnt2;}
int main(){
    scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++){scanf("%d%d",&u,&v); add(v,u); add2(u,v); deg[u]++;}
        for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i);
    while(!q.empty()){
        int top=q.front(); q.pop(); for(int i=0;;i++) if(!mp[top][i]){sg[top]=i; break;}
        for(int i=head[top];i;i=g[i].nex)
                        {deg[g[i].to]--; mp[g[i].to][sg[top]]=1; if(!deg[g[i].to]) q.push(g[i].to);}
    }
    for(int i=1;i<=n;i++){xxor[sg[i]]^=a[i]; mmax=max(mmax,sg[i]);}
    for(int i=mmax;i>=0;i--){
        if(xxor[i]){
            for(int j=1;j<=n;j++) if(sg[j]==i&&((a[j]^xxor[i])<a[j])){
                                a[j]^=xxor[i]; xxor[i]=0;
                                for(int k=head2[j];k;k=g2[k].nex) if(xxor[sg[g2[k].to]])
                                        {a[g2[k].to]^=xxor[sg[g2[k].to]]; xxor[sg[g2[k].to]]=0;} break;
                        }
            printf("WIN\n"); for(int i=1;i<=n;i++) printf("%lld ",a[i]); return 0;
        }
        if(i==0){printf("LOSE"); return 0;}
    }
    return 0;
}