首页 > 代码库 > [原博客] POJ 2425 A Chess Game
[原博客] POJ 2425 A Chess Game
题目链接
题意:给定一个有向无环图(DAG),上面放有一些旗子,旗子可以重合,两个人轮流操作,每次可以把一个旗子从一个位置移动到相邻的位置,无法移动时输,询问先手是否必胜。
这道题可以把每个旗子看作单独的一个游戏,那么所有这些旗子的状态SG值,就是这些旗子各自SG值的Xor和,可以记忆化搜索dfs,暴力算SG值判断即可。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring> //by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);int n;int H[1005],X[1000005],P[1000005],tot;inline void add(int x,int y){ P[++tot]=y;X[tot]=H[x];H[x]=tot;}int sg[1005];int dfs(int x){ if(~sg[x]) return sg[x]; bool nxt[1005]; memset(nxt,0,sizeof nxt); for(int i=H[x];i;i=X[i]){ nxt[dfs(P[i])]=1; } for(int i=0;;i++){ if(!nxt[i]){ return sg[x]=i; } }}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif while(~scanf("%d",&n)){ memset(H,0,sizeof H);tot=0; memset(sg,-1,sizeof sg); for(int i=0,x;i<n;i++){ scanf("%d",&x); for(int j=0,y;j<x;j++){ scanf("%d",&y); add(i,y); } } int q; while(scanf("%d",&q),q){ int SG=0; for(int i=0,x;i<q;i++){ scanf("%d",&x); SG^=dfs(x); } if(SG) puts("WIN"); else puts("LOSE"); } } return 0;}
[原博客] POJ 2425 A Chess Game
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。