uva 10561 Treblecross 【博弈】【SG函数打表】【先手第一步】【子游戏】

题目链接https://vjudge.net/problem/UVA-10561

• 题目大意：
给定一行只含'.'和'X'的字符串且没有连续三个“XXX”的情况，两个玩家依次将'.'改成‘X’,

当一方操作后出现“XXX”的情况时，该方胜利。问先手是否能获胜？

若能，输出所有先手第一步可以操作的位置。

• 分析：一步胜利的情况：
首先要把一步就能取胜的情况单独处理，即“.....XX.....”和“.....X.X.......”,

一旦存在这种情况就不需要考虑一般的情况了，输出所有获胜位置即可。

这里要注意边界位置的处理。
对于一般情况下：
枚举每两个X之间的区间，并求其SG值，可以对1~N长度的SG值在线打表。

求出其区间长度作为下标访问其SG值，整个游戏的SG值ns^=该子游戏的SG值，

并记录下该区间的信息（起始位置和长度），用来后续求先手第一步操作的位置。

注意：
对于全为'.'的情况需要特判。

对X枚举完后，右边界可能会剩下的全'.'区间。（只枚举到了最右边的X，右边可能还有位置）

若为先手胜利，需对之前记录下的每个区间（子游戏）的每个位置进行枚举，

相当于模拟先手第一步的位置，当该位置变为X时使得整个游戏的SG值ns==0时，

留给对手的局面就是ns==0的必败点，这种位置就是我们所要求的位置。

• 求先手第一步的具体原理：

•AC代码：

#include
#include 
#include
#include
#include
#include 
#include
#include
#define ll long long 
#define INF 0x3f3f3f3f
#define	For(i,a,b) for(int i=a;iret; 
void go(){ //对1~N的SG值打表 
	int t1,t2;
	sg[1]=sg[2]=sg[3]=1;
	Forr(i,4,N){
		memset(vis,0,sizeof(vis));
		Forr(j,1,i/2+1){//i为区间长度 
			t1=(j-3<=0)?0:sg[j-3];//左侧SG 
			t2=(i-j-2<=0)?0:sg[i-j-2];//右侧SG 
			vis[t1^t2]=1;
		}
		For(j,0,N)
			if(vis[j]==0){
				sg[i]=j;
				break;
			}
	}
}
void check(int st,int len,int v){//check某个区间 
	int i,t1,t2;
	memset(vis,0,sizeof(vis));
	Forr(i,1,len){//在该区间内枚举所有位置 
		t1=(i-3<=0)?0:sg[i-3];//左侧SG 
		t2=(len-i-2<=0)?0:sg[len-i-2];//右侧SG 
		if(v==(t1^t2))//此时将sg[len]换为t1^t2即可使ns==0 
			ret.push_back(st+i);
	}
}

int main()
{ios::sync_with_stdio(false);
	int t;cin>>t;
	go();
	while(t--){
		cin>>s;
		int sz=s.size();
		int cnt=0,pre=-1,flg=0;//pre表示距离当前x最近的前一个X 
		ret.clear();
		vector>sub;//记录区间（每一堆/每一个子游戏），first是区间开头位置，second为区间长度 
		int ns=0;  //nim-sum
		For(i,0,sz){
			if(s[i]=='X'){
				if(pre!=-1&&i-pre==1){//相邻XX 
					if(pre-1>=0&&s[pre-1]=='.')//.XX
						ret.push_back(pre-1);
					if(i+12){
						sub.push_back(mkp(0,i-2));//这种情况下区间一定从0开始 
						ns^=sg[i-2];
					}
				}else if(i-pre>5){//x..【这里即为此处所讨论的区间】..x
					sub.push_back(mkp(pre+3,i-pre-5));
					ns^=sg[i-pre-5];
				}
				pre=i;//更新上一个X的位置 
			}
		}
		if(pre==-1){//全.无X  
			sub.push_back(mkp(0,sz));
			ns^=sg[sz];
		}
		else if(pre3){//特判右边界可能剩下的全.区间 
			sub.push_back(mkp(pre+3,sz-pre-3));
			ns^=sg[sz-pre-3];
		}
		if(flg){//一步胜利 
			cout<<"WINNING"<

uva 10561 Treblecross 【博弈】【SG函数打表】【先手第一步】【子游戏】

C/C++/C#相关栏目本月热门文章