Treblecross UVA - 10561
每个X把区域分成了禁区,也就是说谁先进入必死,因为他下一个,别人就一定会赢,也就是必胜态的位置。
也就是我们如果先手,一定要给对手留下一个必败态,这样对方才会输。所以就是枚举一下位置,判断一下NIM和就好了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)
const int N=210;
char s[N];
int limit[N];
vector<int> vec;
int sg[N];
bool mex[N];
void get_sg()
{
sg[0]=0;
sg[1]=sg[2]=sg[3]=1;
for(int i=4; i<N; i++) {
memset(mex,0,sizeof(mex));
for(int j=i-3; j>=0; --j) {
int t=max(0,i-(j+5));
mex[sg[t]^sg[j]]=1;
}
for(int j=0;; j++) {
if(!mex[j]) {
sg[i]=j;
break;
}
}
}
//rep(i,0,50)printf("i:%d %d\n",i,sg[i]);
}
int st[N],ed[N];
int main()
{
//freopen("123.txt","w",stdout);
//double t1=clock();
get_sg();
//double t2=clock();
//printf("%.2f\n",(t2-t1)/CLOCKS_PER_SEC);
int T;
scanf("%d",&T);
rep(kase,0,T) {
scanf("%s",s);
int len=strlen(s);
vec.clear();
fill(st,st+len+1,-1);
fill(ed,ed+len+1,-1);
fill(limit,limit+len+1,0);
rep(i,0,len) {
if(s[i]=='X') {
rep(j,0,3) {
if(i-j>=0)limit[i-j]=1;
if(i+j<len) limit[i+j]=1;
}
}
}
rep(i,0,len) {
if(!limit[i]||s[i]=='X')continue;
if(i+2<len&&s[i+1]=='X'&&s[i+2]=='X'||i-2>=0&&s[i-1]=='X'&&s[i-2]=='X'||i-1>=0&&i+1<len&&s[i-1]=='X'&&s[i+1]=='X')
vec.push_back(i);
}
//rep(i,0,vec.size())printf("i:%d %d\n",i,vec[i]);
rep(i,0,len) {
if(limit[i])continue;
if(i-1>=0&&st[i-1]!=-1)st[i]=st[i-1];
else st[i]=i;
}
per(i,0,len) {
if(limit[i])continue;
if(i+1<len&&ed[i+1]!=-1)ed[i]=ed[i+1];
else ed[i]=i;
}
//rep(i,0,len)printf("i:%d st:%d ed:%d\n",i,st[i],ed[i]);
int sum=0;
rep(i,0,len) {
if(limit[i]||s[i]=='X')continue;
sum=sum^sg[(ed[i]-st[i]+1)];
i=ed[i];
}
//printf("sum:%d\n",sum);
int sz=vec.size();
if(sz&&sum==0) {
printf("WINNING\n");
rep(i,0,sz)printf("%d%c",vec[i]+1,i==sz-1?'\n':' ');
continue;
}
int t;
if(sum&&!sz) {
rep(i,0,len) {
if(limit[i]||s[i]=='X')continue;
t=sum^sg[(ed[i]-st[i]+1)];
int l=max(0,i-st[i]+1-3),r=max(0,ed[i]-i+1-3);
//printf("i:%d l:%d r:%d t:%d\n",i,l,r,t);
int tmp=t^sg[l]^sg[r];
// printf("tmp:%d\n",tmp);
if(tmp==0)vec.push_back(i);
}
}
sort(vec.begin(),vec.end());
sz=vec.size();
if(sz) {
printf("WINNING\n");
rep(i,0,sz)printf("%d%c",vec[i]+1,i==sz-1?'\n':' ');
} else {
printf("LOSING\n\n");
}
}
return 0;
}