Treblecross

nim

这算是一道变形的nim游戏的题目。
这是从我学博弈论开始第一次独立做出来的 还算有点意思的博弈题目。

其实这里面的nim特征并不难发现。因为有符号'X'的存在将string划分成了几个小段。
我们可以分别将这几个小段看成独立的nim游戏。
最后再异或和，得到当前的sg值。从而判断这场游戏的胜负。

但是有几个坑点。
我们先想想，sg[i]即长度为i的string其sg值
毫无疑问，sg[0]==0
又因为长度为1,2,3的string其子状态都长度为0的string
所以sg[1]==sg[2]==sg[3]==1

为什么长度为1，2，3在选择一个点放置X后子状态都是长度为0的string呢？
因为：对于这样的情况：..X 和 .X. X..
事实上，如果我在一个点上放置了X那么这个点左右距离他为2的点都作废了。是绝对不能选的，选了 就输。

同理，长度为4的string 子状态为长度为1的string和长度为0的string，则sg[4]==2
依照这样我们求到sg[6]
对于sg[7]
我们发现有这样的一个状态
...X...我们发现左右两边有两个子状态i==1和i==1,按照nim的定理则此时状态的sg值为 sg[1]^sg[1]
如此，一直求到sg[200] 打表。

然后我们似乎就可以，判断当前状态的胜负了。但是，如何选择其下一步走的位置呢？
我们可以，枚举下一步的位置，然后判此时状态的胜负。这样就好了。

但是，这样真的是对的吗？
回到我们刚才的分析：
我们默认X两边距离小于等于2的.都作废，因为选他们必会输。
但是如果这种情况呢：
...X.X..
我们发现我们必须选择中间的那个被作废的.了。否则留给后手选我们必败。

对于这种情况我们需要特殊考虑。

我讲的真垃圾

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int sg[210];
bool used[1100];
int SG(int x) {
    fill(used, used + 1100, 0);
    if (x - 5 <= 0)
        for (int i = 3;x - i >= 0;++i)
            used[sg[x - i]] = true;
    else {
        for (int i = 3;i <= 5;++i)
            used[sg[x - i]] = true;
        int tx = x - 5;
        for (int i = 1;i < tx;++i)
            used[sg[i] ^ sg[tx - i]] = true;
    }for (int i = 0;i < 110;++i)
        if (!used[i])
            return i;
}
string s;
bool judge() {
    string ss;for (int i = 0;i < s.size();++i)ss += s[i];
    for (int i = 0;i < ss.size();++i) {
        if (s[i] == 'X') {
            for (int j = i - 1;j >= 0 && i - j <= 2;--j)
                ss[j] = 'X';
            for (int j = i + 1;j < s.size() && j - i <= 2;++j)
                ss[j] = 'X';
        }
        else {
            if (i - 1 >= 0 && s[i - 1] == 'X' && i + 1 < s.size() && s[i + 1] == 'X')return true;
            if (i + 2 < s.size() && s[i + 1] == 'X' && s[i + 2] == 'X')return true;
            if (i - 2 >= 0 && s[i - 2] == 'X' && s[i - 1] == 'X')return true;
        }
    }
    int cnt = 0;int ans = 0;
    for (int i = 0;i < ss.size();++i) {
        if (ss[i] == '.')++cnt;
        if (ss[i] == 'X' || i == ss.size() - 1) {
            ans ^= sg[cnt];
            cnt = 0;
        }
    }return ans != 0;
}
int main() {
    ios::sync_with_stdio(0);
    sg[0] = 0;
    sg[1] = sg[2] = sg[3] = 1;
    for (int i = 4;i <= 200;++i)
        sg[i] = SG(i);
    int T;cin >> T;
    for (int tcase = 1;tcase <= T;++tcase) {
        cin >> s;vector<int> res;
        for (int i = 0;i < s.size();++i) {
            if (s[i] == '.') {
                if (i - 1 >= 0 && s[i - 1] == 'X' && i + 1 < s.size() && s[i + 1] == 'X')res.push_back(i + 1);
                else if (i + 2 < s.size() && s[i + 1] == 'X' && s[i + 2] == 'X')res.push_back(i + 1);
                else if (i - 2 >= 0 && s[i - 2] == 'X' && s[i - 1] == 'X')res.push_back(i + 1);
            }
        }if (!res.empty()) {
            cout << "Case " << tcase << ":";
            for (int ans : res)cout << " " << ans;
            cout << endl;
        }
        else if (!judge())
            cout << "Case " << tcase << ": 0\n";
        else {
            cout << "Case " << tcase << ":";
            for (int i = 0;i < s.size();++i) {
                if (s[i] != 'X') {
                    s[i] = 'X';
                    if (!judge())
                        cout << " " << i + 1;
                    s[i] = '.';
                }
            }cout << endl;
        }
    }
}