博弈的必胜策略？HDU 5724 Chess解析

题面：

Chess Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 450    Accepted Submission(s): 165


Problem Description Alice and Bob are playing a special chess game on an n × 20 chessboard. There are several chesses on the chessboard. They can move one chess in one turn. If there are no other chesses on the right adjacent block of the moved chess, move the chess to its right adjacent block. Otherwise, skip over these chesses and move to the right adjacent block of them. Two chesses can’t be placed at one block and no chess can be placed out of the chessboard. When someone can’t move any chess during his/her turn, he/she will lose the game. Alice always take the first turn. Both Alice and Bob will play the game with the best strategy. Alice wants to know if she can win the game.  
Input Multiple test cases.

The first line contains an integer T(T≤100), indicates the number of test cases.

For each test case, the first line contains a single integer n(n≤1000), the number of lines of chessboard.

Then n lines, the first integer of ith line is m(m≤20), indicates the number of chesses on the ith line of the chessboard. Then m integers pj(1≤pj≤20) followed, the position of each chess.
 
Output For each test case, output one line of “YES” if Alice can win the game, “NO” otherwise.  
Sample Input

2 1 2 19 20 2 1 19 1 18  
Sample Output

NO YES  
Author HIT  
Source 2016 Multi-University Training Contest 1  

题意：

    给定一个n*20的棋盘，棋盘上有若干棋子。如果一颗棋子右侧为空，则只可以向右移动一格，若非空，则可以移到第一个空的位置，两人轮流操作，不能操作者为输，问先者是否有必胜策略。

解题：

    比较简单的博弈，通过SG值的计算即可解决问题。将游戏划分为多个子游戏，每个游戏相互独立，视为一行的棋盘，最后将每行的SG值异或即可。SG值的计算是，其后续状态（即操作一步之后达到的状态）的SG值集合中未出现过的最小自然数。棋盘的状态可以用二进制位表示，1代表有棋子，0代表无棋子。枚举每个状态的后继，计算该状态的SG值。

代码：

#include#include#include#include#include#include#include#include#include#include#include#include#define eps 1e-8
using namespace std;
int dp[1100000];
//本地测试，最大值不超过30
bool vis[30];
//寻找后续状态
int dfs(int x)
{
	//记忆化搜索
	if(dp[x]!=-1)
		return dp[x];
	int tmp;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<19;i++)
	{
        if((1<x)
			break;
		//找到一个和1紧邻的0
		if(((x&(1<<i))==0)&&(x&(1<<(i+1))))
		{
		   int j=i+2;
           for(;j<20;j++)
		   {
			   if(x&(1<<j))
				   continue;
			   else
				   break;
		   }
		   j--;
		   //逐次替换连续1块中的每一块
		   for(int k=i+1;k<=j;k++)
		   {
              tmp=(x-(1<<k)+(1<<i));
			  tmp=dfs(tmp);
			  vis[tmp]=1;
		   }
		}
	}
	for(int i=0;;i++)
	{
		if(!vis[i])
	    {
			dp[x]=i;
			break;
		}
	}
	return dp[x];
}	
int main()
{
	memset(dp,-1,sizeof(dp));
	//初始化必输态
	for(int i=0;i<=20;i++)
		dp[(1<<i)-1]=0;
	for(int i=1;i<=1100000;i++)
	{
		if(dp[i]==-1)
			dp[i]=dfs(i);
	}
	int t,n,m,status,res,tmp;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		res=0;
		for(int i=0;i<n;i++)
		{
			status=0;
			scanf("%d",&m);
			for(int j=0;j<m;j++)
            {
				//构建进制表示状态
				scanf("%d",&tmp);
				status+=(1<<(20-tmp));
			}
			//异或得出结果
			res^=dp[status];
		}
		if(res)
			printf("YESn");
		else
			printf("NOn");
	}
	return 0;
}