noi.ac164 字符串游戏

读错题引发的血案。

题目里加粗的可以在字符串任意位置加入字符我没看到，然后GG了。

当且仅当原串能够删除一个字符使得剩下的串为01相间的时候，先手必胜。

可以转化为串中至多有一个位置存在两个连续的0或者1.

首先考虑整个串都是01相间的情况，显然先手必胜。

存在1处连续两个1的时候，设其为0110

如果A先放置1，那么B不管如何放置，A总能放出连续两个1,。

存在连续两个0时同理。

存在多处连续两个1的时候，设其为

0110110

A在放置出第一个11的时候，B一定会采取策略阻止A放置第二个11（A之所以能放第一个11因为他是先手）。

#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 5000;
char buf[LARGE * 2 + 1];
bool prefix[LARGE + 1], suffix[LARGE + 1];
int main() {
    int T;
    cin >> T;
    while (T--) {
        scanf("%s", buf + 1);
        int n = strlen(buf + 1);
        for (int i = 1; i <= n; i++) buf[i] -= '0';
        if (n <= 2) {
            cout << "Zhangzj" << endl;
            continue;
        }
        prefix[1] = true, suffix[n] = true;
        for (int i = 2; i <= n; i++)
            prefix[i] = prefix[i - 1] && (buf[i] ^ buf[i - 1]);
        for (int i = n - 1; i >= 1; i--)
            suffix[i] = suffix[i + 1] && (buf[i] ^ buf[i + 1]);
        bool result = false;
        for (int i = 2; i < n && (!result); i++) {
            result |=
                (buf[i - 1] ^ buf[i + 1]) && prefix[i - 1] && suffix[i + 1];
        }
        result |= (prefix[n - 1] || suffix[2]);
        if (result)
            cout << "Zhangzj" << endl;
        else
            cout << "Owaski" << endl;
    }
    return 0;
}