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; } } }