[洛谷 2575] 高手过招【SG定理】
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; }
发表评论