AcWing 1319. 移棋子游戏
原题链接
中等
作者:
呆呆小Y
,
2022-06-24 12:14:41
,
所有人可见
,
阅读 167
SG函数+记忆化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N=2005;
const int M=6005;
int n,m,k,e[M],h[N],ne[M],sg[N],idx;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int SG(int x)
{
if(sg[x]!=-1) return sg[x];
unordered_set<int> S;
for(int i=h[x];i!=-1;i=ne[i])
{
S.insert(SG(e[i]));
}
for(int i=0;;i++)
{
if(S.count(i)==0)
return sg[x]=i;
}
}
int main()
{
memset(h, -1, sizeof h);
memset(sg,-1,sizeof sg);
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
add(u,v);
}
int res=0;
for(int i=0;i<k;i++)
{
int x;
cin>>x;
res^=SG(x);
}
if(res)
cout<<"win";
else
cout<<"lose";
return 0;
}