题意
有一个DAG，点有点权。两个人轮流操作，每次可以选择一个点，将这个点的权值变小，并把所有该点出边指向的点的权值改变为任意值。满足任意时刻每个点的点权均为非负整数。无法操作者输。问先手是否必胜，若必胜则给出第一步操作。
n
,
m
≤
2
∗
1
0
5
n,m\le2*10^5
n,m≤2∗105
分析
先把每个点的sg函数求出来，设
s
u
m
(
x
)
sum(x)
sum(x)表示所有sg函数等于
x
x
x的点的权值的异或和。那么先手必胜当且仅当不存在
x
x
x满足
s
u
m
(
x
)
sum(x)
sum(x)为
0
0
0。 证明：当无法操作时所有的
s
u
m
(
x
)
sum(x)
sum(x)都为
0
0
0。 若所有
s
u
m
(
x
)
sum(x)
sum(x)都为
0
0
0，当对一个点
k
k
k操作时，所有sg函数值为
k
k
k的点只有该点的权值发生改变，则
s
u
m
(
s
g
(
k
)
)
sum(sg(k))
sum(sg(k))必然变得不为
0
0
0。 若存在
s
u
m
(
x
)
sum(x)
sum(x)不为
0
0
0，找到最大且满足的
x
x
x，然后对某个sg函数值为
x
x
x的点操作，必然可以使得所有的
s
u
m
(
x
)
sum(x)
sum(x)都变为
0
0
0。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
const int N
=200005;
int n
,m
,cnt
,last
[N
],a
[N
],deg
[N
],sg
[N
],h
[N
],sum
[N
];
bool vis
[N
];
struct edge
{int to
,next
;}e
[N
];
void addedge(int u
,int v
)
{
e
[++cnt
].to
=v
;e
[cnt
].next
=last
[u
];last
[u
]=cnt
;
}
void get_sg()
{
int tot
=0;
for (int i
=1;i
<=n
;i
++) if (!deg
[i
]) a
[++tot
]=i
;
for (int i
=1;i
<=n
;i
++)
{
int x
=a
[i
];
for (int j
=last
[x
];j
;j
=e
[j
].next
)
{
deg
[e
[j
].to
]--;
if (!deg
[e
[j
].to
]) a
[++tot
]=e
[j
].to
;
}
}
for (int i
=n
;i
>=1;i
--)
{
int x
=a
[i
];
for (int j
=last
[x
];j
;j
=e
[j
].next
) vis
[sg
[e
[j
].to
]]=1;
for (;vis
[sg
[x
]];sg
[x
]++);
for (int j
=last
[x
];j
;j
=e
[j
].next
) vis
[sg
[e
[j
].to
]]=0;
}
}
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
);
addedge(u
,v
);
deg
[v
]++;
}
get_sg();
for (int i
=1;i
<=n
;i
++) sum
[sg
[i
]]^=h
[i
];
int mx
=-1;
for (int i
=n
;i
>=0;i
--) if (sum
[i
]) {mx
=i
;break;}
if (mx
==-1) {puts("LOSE");return 0;}
int pos
=0;
for (int i
=1;i
<=n
;i
++) if (sg
[i
]==mx
&&(h
[i
]^sum
[mx
])<h
[i
]) {pos
=i
;break;}
puts("WIN");
h
[pos
]=sum
[mx
]^h
[pos
];
for (int i
=last
[pos
];i
;i
=e
[i
].next
)
{
int x
=e
[i
].to
;
if (vis
[sg
[x
]]) continue;
vis
[sg
[x
]]=1;
h
[x
]=sum
[sg
[x
]]^h
[x
];
}
for (int i
=1;i
<=n
;i
++) printf("%d ",h
[i
]);
puts("");
return 0;
}
