题解 | #Agnej#

D. Agnej

博弈，m 为偶数的时候最后一定是变成每层两半各留一个，直接统计 1 的数目判断奇偶性；

m 为奇数的时候先默认大家都会薅掉中间的，这样还是每层两半各留一个。但是只要某层某一半没了，中间还在，中间就不能被薅掉了。

假设某一层中间被包裹得很好，例如 1 1 1 1 1，至少需要薅掉两个旁边的才能被保护，这样由于 Alice 和 Bob 里面一定有一个想在中间那个被保护之前薅掉它，它就一定会被薅掉，最后和 m 为偶数的情况一样，剩下类似于 0 1 0 0 1 的东西，剩下 2 个 1。

假设某一层中间没有被包裹，例如 0 0 1 1 1，这个 1 不能被薅掉，因此最后这层一定变成 0 0 1 0 0，只会剩下一个 1。

假设只有一阶包裹，例如 0 1 1 1 1，且只有一层符合这个要求，假设一旦这个 1 被保护 Alice 就寄了，Alice 会把它薅掉，Alice 就能赢。假设 1 被薅掉 Alice 才寄，Alice 可以把这个 1 保护起来（抽掉旁边的 1，变成 0 0 1 1 1），Alice 还是能赢。所以假设只有一层有一阶包裹，就能导致 Alice 必胜。

假设有偶数个层有一阶包裹，且如果大家都薅掉中间的，Alice 会寄，Alice 就只能选择保护，但这样 Bob 也可以跟着保护一个，Alice 扭转不了局面。这个情况换 Bob 来也一样。

假设有奇数个层有一阶包裹，偶数部分会被像上面那样被浪费掉，最后剩下一个，导致 Alice 必胜。

所以可以这样编码：

#include <algorithm>
#include <iostream>
#define int long long

const int N = 1e5 + 4;

int n, m;
char s[N];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n >> m;
  // 虚空视为 bob 赢
  int res = 0;
  // 一次阻止中间薅掉能否逆转局势？（可以被 alice 破坏）
  int blk1 = 0;
  for (int i = 0; i < n; i++) {
    std::cin >> s;
    for (int j = 0; j < m; j++) {
      if (s[j] == '1') {
        // 多一个就逆转一次局势
        res ^= 1;
      }
    }
    // 处理中间有 1 的情况
    if (m % 2 == 1 && s[m / 2] == '1') {
      // 统计两侧 1 的数量
      int lc = 0, rc = 0;
      for (int j = 0; j < m / 2; j++) {
        if (s[j] == '1') {
          lc++;
        }
      }
      for (int j = m / 2 + 1; j < m; j++) {
        if (s[j] == '1') {
          rc++;
        }
      }
      // 最少多少次阻止中间被薅掉
      int blk = std::min(lc, rc);
      // 中间薅不掉，局势逆转
      if (blk == 0) {
        res ^= 1;
      }
      // 一次阻止中间薅掉，总共有奇数次这种情况才逆转局势，否则可以 replica
      if (blk == 1) {
        blk1 ^= 1;
      }
    }
  }
  std::cout << (res || blk1 ? "Alice" : "Bob") << '\n';
  return 0;
}