[原创]HDU 1524 A Chess Game [SG函数]【博弈】

2016-10-27 21:56:49 Tabris_ 阅读数：349

博客爬取于2020-06-14 22:42:57
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52950443

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1524
-------------------------------.
A Chess Game

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2133 Accepted Submission(s): 954

Problem Description
Let’s design a new chess game. There are N positions to hold M chesses in this game. Multiple chesses can be located in the same position. The positions are constituted as a topological graph, i.e. there are directed edges connecting some positions, and no cycle exists. Two players you and I move chesses alternately. In each turn the player should move only one chess from the current position to one of its out-positions along an edge. The game does not end, until one of the players cannot move chess any more. If you cannot move any chess in your turn, you lose. Otherwise, if the misfortune falls on me… I will disturb the chesses and play it again.

Do you want to challenge me? Just write your program to show your qualification!

Input
Input contains multiple test cases. Each test case starts with a number N (1 <= N <= 1000) in one line. Then the following N lines describe the out-positions of each position. Each line starts with an integer Xi that is the number of out-positions for the position i. Then Xi integers following specify the out-positions. Positions are indexed from 0 to N-1. Then multiple queries follow. Each query occupies only one line. The line starts with a number M (1 <= M <= 10), and then come M integers, which are the initial positions of chesses. A line with number 0 ends the test case.

Output
There is one line for each query, which contains a string “WIN” or “LOSE”. “WIN” means that the player taking the first turn can win the game according to a clever strategy; otherwise “LOSE” should be printed.

Sample Input
4
2 1 2
0
1 3
0
1 0
2 0 2
0

4
1 1
1 2
0
0
2 0 1
2 1 1
3 0 1 3
0

Sample Output
WIN
WIN
WIN
LOSE
WIN

Source
PKU Monthly

--------------------------------------.
题目大意：
这题就是给你一个有向图最后不能移动的人就输了问你先手输赢的情况

这题的输入比较乱反正我是看了半天才明白；
就是先输入一个n代表有n个点
然后又n行分别表示的是0~n-1这几个点指向的节点
第一个数x是指向几个节点，然后的x个数表示节点
然后有q次询问
接下来有q行
每行第一个数表示有x个起始位置接下来的是x个其实位置的值
然后让你判断先手的输赢

解题思路：
这题就是最最最最裸的SG函数了
恰恰就是sg函数的定义：把问题抽象成一个有向无环图

并没有什么可说的只要dfs一下就行了当然for也可以

然而特别要注意的是，mex操作中的标记数组声明在外面就不能过在函数里面声明就AC
这都是玄学。。。

附本题代码
-------------------------------.


//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <vector>
using namespace std;

# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define min(a,b) (a)>(b)?(a):(b)
# define lalal puts("*******")
typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/

const int MOD = 10086;
const int N = 1e4+5;
const double eps = 1e-9;

int sg[1010];

vector<int>E[1010];
int getsg(int v)
{
    if(sg[v]!=-1) return sg[v];
    bool h[1010];
    memset(h,0,sizeof(h));
    for(int i=0;i<E[v].size();i++)
        h[getsg(E[v][i])]=1;
    for(int i=0;;i++)
        if(0==h[i]) {sg[v]=i;break;}

    return sg[v];
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        memset(sg,-1,sizeof(sg));
        int x,y;
        for(int i=0;i<n;i++){
            E[i].clear();
            scanf("%d",&x);
            while(x--){
                scanf("%d",&y);
                E[i].pb(y);
            }
        }
        int ans;
        while(true){
            ans=0;
            scanf("%d",&x);
            if(0==x) break;
            while(x--){
                scanf("%d",&y);
                ans^=getsg(y);
            }

        if(ans) puts("WIN");
        else    puts("LOSE");
        }
    }
    return 0;
}