MYF

HDU 5724 Chess

Posted on | In | | Visitors

题目链接

HDU 5724

解题方法：sg函数

题目分析

题目大意

一个$n*20$的棋盘上有若干个棋子，Alice和朋友玩这样一个游戏，每个人操作的时候可以选取一个棋子向右移动到右边第一个空格的位置，当玩家不能选取了也就是每一行的所有棋子都在最右边时，该取子者输，问Alice是否能赢

解析

第一场多校的题拖到现在，本来想把博弈全都扔给队友的，谁知道前天第六场又出现了博弈sg函数的题，想明白的十分钟就ac了，像我们这样想不明白的要四个多小时外加好几发的wa。这两天看看博弈觉得也挺有神奇的，就当重新学了一遍吧。

先推荐几篇比较好的关于博弈的文章，建议按顺序阅读。

  1. 组合博弈 – 三大基本博弈
  2. 组合游戏 - SG函数和SG定理
  3. HDU 5724 Chess 从懵逼到学会 SG函数

言归正传，下面开始写题解。

根据sg函数，我们可以知道，要求出最后Alice能否获胜就要求出各行的sg值，这样问题就转化成为了一个求一行能否获胜的问题。一行共有20个格子，也就是说最多有220种情况，即每一格有棋子或者没有棋子。数据范围还可以接受，所以选择打表的方式先把这么多种情况的sg值全部打印下来，然后对于每一个游戏，所有出现情况的sg值异或看是否为零则可以判断先手是否获胜或者失败。

现在我们该找当前情况$x$的sg值。我们首先先要找到他可以转化到的情况y，取这些情况的sg值sg[y]，然后取mex{sg[y]|x->y}。对于当前的形势，我们可以将任意一位没有走到头的棋子右移到他应该到达的位置。方便起见，我们用每一行只有9个格子举例，比如当前情况为”000111001”，那么这种情况可以转化为三种状态，也就是中间的三个1分别右移之后的状态，即”0000111001”,”000101101”,”000110101”。由于我们取sg值是从小到大取的，所以这三个值我们之前应当已经记录过，将这三个sg值存入一个集合中，取这个集合的mex值即为当前状态的sg值。

剩下的就很简单了，将每一行的情况的sg值异或起来，根据Nimm博弈，等于0则先手必败，否则先手必胜。

类似的博弈题目还有2016年多校第六场的HDU5795，比这题简单一些。我的题解传送门

代码

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
70
71
72
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define pb push_back
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("1005.in","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=10+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int sg[1<<20];
void Init(){
    for(int i = 1;i < (1<<20); i++){
        int h[25];
        memset(h, -1, sizeof(h));
        int last = -1;
        for(int j = 0; j < 20; j++){
            if(!((i >> j) & 1))
                last = j;
            if(((i >> j) & 1)){
                if(last != -1){
                    h[sg[(i ^ (1 << j)) ^ (1 << last)]]=1;
                }
            }
        }
        int j=0;
        while(h[j] != -1) j++;
        sg[i]=j;
    }

}
int main(){
    Init();
    int T,n,m,len,tmp;
    scanf("%d", &T);
    while (T--) {
        int sum =0;
        scanf("%d",&n);
        for (int i=0; i<n; i++) {
            scanf("%d",&m);
            tmp = 0;
            for (int j=1; j<=m; j++) {
                scanf("%d",&len);
                tmp |= (1<<(20-len));
            }
            sum ^= sg[tmp];
        }
        if (sum)
            puts("YES");
        else
            puts("NO");
    }
}