HDU 1524 树上无环博弈 暴力SG

一个拓扑结构的图,给定n个棋的位置,每次可以沿边走,不能操作者输。

已经给出了拓扑图了,对于每个棋子找一遍SG最后SG和就行了。

/** @Date    : 2017-10-13 20:08:45
* @FileName: HDU 1524 树上无环博弈 暴力SG.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e3+20;
const double eps = 1e-8; vector<int>edg[N];
int sg[N]; int dfs(int x)
{
int vis[N];
MMF(vis);
if(sg[x] != -1)
return sg[x];
for(auto i : edg[x])
vis[dfs(i)] = 1;
for(int i = 0; ;i++)
if(!vis[i])
return sg[x] = i;
return sg[x];
} int main()
{
int n;
while(cin >> n)
{
for(int i = 0; i <= n; i++)
edg[i].clear(), sg[i] = -1;
for(int i = 0; i < n; i++)
{
int cnt;
int y;
scanf("%d", &cnt);
while(cnt--) scanf("%d", &y), edg[i].PB(y);
}
int q;
while(scanf("%d", &q) && q)
{
int ans = 0;
int x;
for(int i = 0; i < q; i++)
scanf("%d", &x), ans ^= dfs(x);
//, cout << "~"<<x <<" "<<dfs(x)<<endl;;
printf("%s\n", ans?"WIN":"LOSE");
}
}
return 0;
}
上一篇:js点击页面其他地方如何隐藏div元素菜单


下一篇:openssl生成https证书 (转)