这题细节还挺多的。
分析
拿到题目先拿样例找一下性质。
对于最初的局面，发现如果有一个位置出现 X ，那么它的左边两个或者右边两个位置只要存在 X ，那么先手必然胜利。
如果不存在上面的情况，我们就可以枚举一下先手决策的位置，看看所得到的状态能不能让后手必输。
这时候我们想到用 sg 函数来刻画这一点。
方便起见，我们约定
X的左右两个位置为“禁着点”（记为O）（因为谁在这个地方下了X谁就输了）。
用 (f[x]) 表示空棋盘（也就是 (x) 个 . ）的 sg 函数值。
我们以 (x=10) 为例（..........）：
当下了一个 X 时在位置 (p=5) 时，棋盘变为 ..OOXOO... 。
剩下的部分可以看成两个棋盘，大小分别为 (2, 3) 。
一般地，对于落点 (p) ，得到的两个新棋盘的 sg 函数值为 (f[max(0, p-3)],~f[max(0, x-p-2)]) 。
类似地枚举落点的位置，我们可以得到 (f[x]) ：
[f[x] = {
m mex}_{p=1}^{x} (f[max(0, p-3)]oplus f[max(0, x-p-2)])
]
mex（minimal exdudant）函数
设 (S) 表示一个非负整数集合。定义 ({ m mex{(S)}}) 为求出不属于集合 (S) 的最小非负整数的运算。
如：{ (0,1,3) } 对应的 ({ m mex}) 值 就是 (2) 。
最后还要提醒一下输出问题：
- 每一行输出行末不要空格！
- 如果判断得到的是
LOSING，要额外输出一个空行。
高清程序
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '
'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=220;
int n;
string str, tmp;
vector<int> res;
int f[N];
int sg(int x){
if(~f[x]) return f[x];
unordered_set<int> buf;
rep(i,1,x){ // 枚举决策求 sg 函数
int len1=i-3, len2=x-i-2;
len1=max(len1, 0), len2=max(len2, 0);
int t=sg(len1)^sg(len2);
buf.insert(t);
}
int p=0;
while(buf.count(p)) p++;
return f[x]=p;
}
void init(){
memset(f, -1, sizeof f);
f[0]=0;
f[1]=f[2]=f[3]=1;
rep(i,1,N-1) sg(i);
}
int main(){
init(); // 预处理出 sg 函数并存在 f[] 中
int T; cin>>T;
while(T--){
res.clear(); // 记得清空 res
cin>>str;
n=str.size();
str="##"+str+"##"; // 减少特判边界，加上边界符号
bool ok=false; // 特殊判断一开始的局面是否存在 "XX." "X.X" ".XX" 的情况
rep(i,2,n+1) if(str[i]=='.'){
bool fl=false;
if(str[i-1]=='X' && str[i-2]=='X') ok=fl=true;
if(str[i+1]=='X' && str[i+2]=='X') ok=fl=true;
if(str[i-1]=='X' && str[i+1]=='X') ok=fl=true;
if(fl) res.pb(i);
}
if(ok){
puts("WINNING");
rep(i,0,res.size()-1){
if(!i) cout<<res[i]-1;
else cout<<' '<<res[i]-1;
}
cout<<endl;
continue;
}
rep(i,2,n+1) if(str[i-2]!='X' && str[i-1]!='X' && str[i]!='X' && str[i+1]!='X' && str[i+2]!='X'){
tmp=str;
tmp[i]='X';
int t=0;
rep(j,2,n+1){
if(tmp[j]=='.'){ // 将连续的 "." 区域拿来讨论。
int l=j;
while(tmp[j]=='.') j++;
j--;
int r=j;
int len=r-l+1;
if(tmp[l-1]=='X') len-=2;
if(tmp[r+1]=='X') len-=2;
len=max(len, 0);
t^=f[len];
}
}
if(!t) res.pb(i);
}
if(res.size()){
puts("WINNING");
rep(i,0,res.size()-1){
if(!i) cout<<res[i]-1;
else cout<<' '<<res[i]-1;
}
cout<<endl;
}
else puts("LOSING
");
}
return 0;
}