记录编号	85867	评测结果	AAAAAAAAAA
题目名称	[UVa 10561] Treblecross 游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2014-01-15 11:22:44	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int SIZEN=200;
int SG[SIZEN+10]={0};
bool win(string &s){//是否必胜
	int i,j;
	int n=s.size();
	for(i=0;i<n-2;i++) if(s[i]=='X'&&s[i+1]=='X'&&s[i+2]=='X') return false;//输了
	for(i=0;i<n-1;i++) if(s[i]=='X'&&s[i+1]=='X') return true;//两个挨着的,赢
	for(i=0;i<n-2;i++) if(s[i]=='X'&&s[i+2]=='X') return true;//中间有一个空格,赢
	bool flag[SIZEN+10]={0};//可用与否,可用为0
	for(i=0;i<n;i++){
		if(s[i]=='X'){
			for(j=-2;j<=2;j++) if(0<=i+j&&i+j<n) flag[i+j]=true;
		}
	}
	flag[n]=1;//给"最后一块"加上边界
	i=-1;
	int anssg=0;//这个状态的sg函数
	for(j=0;j<=n;j++){
		if(i==-1&&!flag[j]) i=j;//新块的起点
		if(i!=-1&&flag[j]) anssg^=SG[j-i];
		if(flag[j]) i=-1;//当前块统计结束
	}
	return anssg!=0;
}
void singledeal(string &s){
	if(!win(s)) printf("LOSING\n\n");
	else{
		vector<int> ans;
		printf("WINNING\n");
		for(int i=0;i<s.size();i++){
			if(s[i]=='X') continue;
			s[i]='X';
			if(!win(s)) ans.push_back(i+1);
			s[i]='.';
		}
		for(int i=0;i<ans.size();i++){
			if(i) printf(" %d",ans[i]);
			else printf("%d",ans[i]);
		}
		printf("\n");
	}
}
int mex(vector<int> &s){
	sort(s.begin(),s.end());
	if(s[0]) return 0;
	for(int i=1;i<s.size();i++) if(s[i]>s[i-1]+1) return s[i-1]+1;
	return s.back()+1;
}
void getSG(int SIZEN){
	SG[0]=0,SG[1]=SG[2]=SG[3]=1;
	for(int i=4;i<=SIZEN;i++){
		vector<int> s;
		s.push_back(SG[i-3]);//一侧占3个
		s.push_back(SG[i-4]);//一侧占4个
		if(i>=5) s.push_back(SG[i-5]);
		for(int j=1;j<i-5;j++) s.push_back(SG[j]^SG[i-j-5]);
		SG[i]=mex(s);
	}
}
int main(){
	freopen("treblecross.in","r",stdin);
	freopen("treblecross.out","w",stdout);
	getSG(SIZEN);
	int T;
	scanf("%d",&T);
	while(T--){
		string s;
		cin>>s;
		singledeal(s);
	}
	return 0;
}