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

  • 2018-02-28
  • 0
  • 0

Problem:

题目描述

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

游戏规则是这样的:

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

输入输出格式

输入格式:

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

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

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

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

输出格式:

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

输入输出样例

输入样例#1:

2
1
2 19 20
2
1 19
1 18

输出样例#1:

NO
YES

说明

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

另外10%的数据m≤1

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

By:Mul2016

Solution:

本题是较简单的博弈论

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

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

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

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

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

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

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai