题解 CF1149E 【Election Promises】

justin_cao · 2020-03-15 17:17:29 · 题解

首先如果没有任意地去改变后继节点的权值的话，这道题就是一个nim游戏的板子。

有的话首先考虑一下分组，分组的过程是这样：

• 将所有出度为0的点的标号设为0。
• 然后拓扑排序，每个点的标号是它的后继节点编号的mex。

考虑这样分组的特点：

• 对于图中的任意一条边(u,v)，u和v必定不在一个组内。
• 假设一个点i的标号是id[x]，那么x的后继节点中，[0,id[x])任意一个组必定至少有一个。

那么考虑每一个组内所有点的异或和，设其为val[i]。

那么考虑发现一下val的一些性质：

• 如果一个组的val=0，那么对于这个组中的某个点进行操作之后，这个点的权值一定不为0。（显然）
• 对于一个组i而言，那么对它操作，可以将标号为[0,i-1]的集合的val全部变成0。

那么我们通过上面两个性质可以知道：

• 对于一个所有组的val不全都=0的状态，一定可以用一步操作将所有的val变为0。具体操作就是将一个标号最大的val不为0的点降低成0，然后将前面所有val不为0的节点修改成0。
• 对于一个所有组的val都为0的状态，通过一次操作只能转移到全0的状态。

那么通过上面的分析，对于初始局面，只要有一个组的val为0，那么这个局面就是先手必胜，否则就是先手必败。

至于输出方案的话，我们只需要对于那个标号最大的val不为0的组找到一个能将val降成0的点降成0，然后将它的后继节点修改即可。

复杂度O(n)。

code:

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,top,mx;
int head[maxn],nxt[maxn],to[maxn],tot;
void add(int u,int v)
{
    tot++;
    nxt[tot]=head[u];
    head[u]=tot;
    to[tot]=v;
}
ll a[maxn],val[maxn];
int deg[maxn],p[maxn],vis[maxn],id[maxn];
queue<int>q;
void top_sort()
{
    for(int i=1;i<=n;i++)
      if(!deg[i])  q.push(i);
    while(q.size())
    {
        int now=q.front();q.pop();
        p[++top]=now;
        for(int i=head[now];i;i=nxt[i])
        {
            deg[to[i]]--;
            if(!deg[to[i]])  q.push(to[i]);
        }
    }
    for(int i=n;i>=1;i--)
    {
        int x=p[i];
        for(int j=head[x];j;j=nxt[j])  vis[id[to[j]]]=1;
        while(vis[id[x]])  id[x]++;
        val[id[x]]^=a[x];mx=max(mx,id[x]);
        for(int j=head[x];j;j=nxt[j])  vis[id[to[j]]]=0;
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)  a[i]=read();
    for(int i=1;i<=m;i++)
    {
        int q=read(),w=read();
        add(q,w);deg[w]++;
    }
    top_sort();
    int pos=-1;
    for(int i=0;i<=mx;i++)
      if(val[i])  pos=i;
    if(pos==-1)  return puts("LOSE"),0;
    puts("WIN");
    for(int i=1;i<=n;i++)
    {
        if(id[i]==pos)
        {
            if((val[id[i]]^a[i])>a[i])  continue;
            a[i]^=val[id[i]];val[id[i]]=0;
            for(int j=head[i];j;j=nxt[j])
              a[to[j]]^=val[id[to[j]]],val[id[to[j]]]=0;
        }
    }
    for(int i=1;i<=n;i++)  printf("%lld ",a[i]);
    puts("");
    return 0;
}