C++(clang++ 11.0.1) 解法, 执行用时: 78ms, 内存消耗: 7032K, 提交时间: 2022-08-26 11:54:12
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define sf(n) scanf("%d",&n)
const int N=1e5+3;
int g[1001];
vector<int> v[1001];
int mex(int y){
if(g[y]!=-1) return g[y];
int vis[1001]={0};
int num=v[y].size();
rep(i,0,num-1){
g[v[y][i]]=mex(v[y][i]);
vis[g[v[y][i]]]=1;
}
rep(i,0,1001){
if(!vis[i]) return i;
}
return 0;
}
int main(){
int n,k,x;
sf(n);
int num=n-1;
memset(g,-1,sizeof(g));
while(n--){
sf(k);
if(k==0) g[num-n]=0;
rep(j,1,k){
sf(x);
v[num-n].push_back(x);
}
}
int m,y;
while(sf(m)&&m){
int sum=0;
rep(i,1,m){
sf(y);
g[y]=mex(y);
sum^=g[y];
}
if(sum) cout<<"WIN"<<endl;
else cout<<"LOSE"<<endl;
}
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 95ms, 内存消耗: 3284K, 提交时间: 2023-07-15 14:09:29
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
const int N = 1e3+7;
vector<int>s[N];
int f[N];
int sg(int x){
if(f[x]!=-1)return f[x];
unordered_set<int>v;
for(int i=0;i<s[x].size();i++){
v.insert(sg(s[x][i]));
}
for(int i=0;;i++){
if(!v.count(i))return f[x]=i;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++){
int k;
cin>>k;
for(int j=0;j<k;j++){
int x;
cin>>x;
s[i].push_back(x);
}
}
int m;
memset(f,-1,sizeof f);
while(cin>>m,m){
int res=0;
for(int i = 0;i<m;i++){
int y;
cin>>y;
res^=sg(y);
}
if(res==0)cout<<"LOSE"<<endl;
else cout<<"WIN"<<endl;
}
return 0;
}
个节点的有向无环图，编号为 
到 
。有若干轮游戏，每轮游戏给出 
个棋子在图上的哪个节点，可能会有两个棋子在同一个节点上。两个玩家轮流移动，每次可以选择一个棋子将其移动到他的后继节点，直到有一方不能移动任何棋子，判定为输。假设双方都能够采取最优的策略，如果第一个移动棋子的人获胜输出"WIN"，否则输出"LOSE"。)，表示节点个数。
，表示第
(
) 个节点有
(
)，表示节点
)，表示
(
)，表示
。