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

• 2018-02-28
• 0
• 0

Problem:

题目描述

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

游戏规则是这样的：

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

输入输出格式

输入格式：

第一行一个T，表示T组数据

每组数据第一行n，表示n*20的棋盘

接下来n行每行第一个数m表示第i行有m个棋子

随后跟着m个数p_j表示第i行的棋子布局

输出格式：

如果akn能赢，则输出”YES”，否则输出”NO”

输入输出样例

2
1
2 19 20
2
1 19
1 18

NO
YES

说明

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

另外10%的数据m≤1

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

By:Mul2016

Solution:

本题是较简单的博弈论。

由于棋盘每一行都是相互独立的 Nim 游戏，考虑计算出各个游戏的 SG 值，套用 SG 定理即可。

由于每行只有 20 列，我们可以将状态压缩，预处理出所有的 2²⁰ 个状态的 SG 值。

采用位运算可以加快计算速度，lowbit(x) = x & -x 能计算出二进制数最后一位 1 对应的值。

将后继节点 SG 值集合 S[] 进行排序以计算 mex{S}。

注意当 S 中最小元素不为 0 时 mex{S} = 0，需要特判。

Code: O(2ⁿnlogn), 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;
}