首页 > 代码库 > [原博客] POJ 2425 A Chess Game

[原博客] POJ 2425 A Chess Game

2024-07-21 13:57:50   219人阅读

题目链接
题意：给定一个有向无环图（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;}
View Code

 

[原博客] POJ 2425 A Chess Game


联系
我们