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

Tabris

CSDN博弈

发布于：2016年10月27日

次浏览

[原创]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
这都是玄学。。。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

//#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;
}

本页文档最后更新于：2021年5月16日

CSDN