# [洛谷 2575] 高手过招【SG定理】

• 2018-02-28
• 0
• 0

## Problem:

### 题目描述

akn玩游戏玩累了，于是他开始和同伴下棋了，玩的是跳棋！对手是wwx！这两位上古神遇在一起下棋，使得棋局变得玄幻莫测，高手过招，必有一赢，他们都将用最佳策略下棋，现在给你一个n*20的棋盘，以及棋盘上有若干个棋子，问谁赢？akn先手！

```2
1
2 19 20
2
1 19
1 18
```

```NO
YES
```

### 说明

10%的数据T≤1，n≤1

100%的数据T≤100，n≤1000，m≤20，1≤pj≤20

By:Mul2016

## Code: O(2nnlogn), n为列数(=20) [6132K, 1500MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int MAXSTAT = 1 << 20;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int SG[MAXSTAT], S[MAXSTAT], tops;
int T, n, m;

inline void calc_SG(){
memset(SG, 0, sizeof(SG));
for(register int i = 1; i < MAXSTAT; i++){
int cur = i + 1 - lowbit(i + 1);  // Clear unmovable chesses
tops = 0;
while(cur){
int lb = lowbit(cur), k = lb;  // Find the lowest 1
for(k >>= 1; k; k >>= 1) if((i & k) == 0) break;  // Find the highest 0 after that 1
cur ^= lb, S[++tops] = SG[i ^ lb ^ k];  // Calculate the succ-set
}
sort(S + 1, S + tops + 1);
if(S[1]) SG[i] = 0;  // Condition mex{S} == 0 needs special judgement
else{
S[tops + 1] = 0x3f3f3f3f;
for(register int j = 1; j <= tops; j++)
if(S[j + 1] > S[j] + 1) {SG[i] = S[j] + 1; break;}
}
}
}

int main(){
calc_SG(), getint(T);
while(T--){
int nimsum = 0; getint(n);
while(n--){
int stat = 0, chess; getint(m);
while(m--) getint(chess), stat |= 1 << 20 - chess;
nimsum ^= SG[stat];
}
puts(nimsum ? "YES" : "NO");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai