题解 | #小红的01串#

1 操作的不变量分析 观察操作：选择索引 ，将 和 取反。 我们关注字符串中字符 '1' 的数量（记为 ）：

• 如果 为 "00"，操作后变为 "11"， 增加 2。
• 如果 为 "11"，操作后变为 "00"， 减少 2。
• 如果 为 "01"，操作后变为 "10"， 不变。
• 如果 为 "10"，操作后变为 "01"， 不变。

结论：无论进行多少次操作，字符 '1' 数量的奇偶性（Parity）保持不变。同理，字符 '0' 数量的奇偶性也保持不变。

2 目标状态分析 题目要求“所有字符相同”，这意味着目标状态有两种可能：

1. 目标 A（全 '0'）：此时字符串中 '1' 的数量为 。 是偶数。
2. 目标 B（全 '1'）：此时字符串中 '0' 的数量为 。 是偶数。

3 可行性判定条件 基于不变量原理，我们可以得出充要条件：

• 若要通过操作将字符串变为全 '0'，其初始状态必须满足：'1' 的数量是偶数。
  • 证明思路（简述）： 如果 '1' 的数量是偶数，我们可以从左向右扫描，每遇到一个 '1'，就翻转它和它右边的位。这样可以将当前的 '1' 变成 '0'，并将“错误”向右传递。由于 '1' 的总数是偶数，最后一个 '1' 一定会被前面的操作消除或者与另一个 '1' 配对消除，最终所有位都会变成 '0'。
• 若要通过操作将字符串变为全 '1'，其初始状态必须满足：'0' 的数量是偶数（即 '1' 的数量与字符串总长度 具有相同的奇偶性）。

4 结论 每次询问的答案为 "Yes" 的条件是： （'1' 的数量为偶数） 或者 （'0' 的数量为偶数）

如果两者皆为奇数，则无论如何操作，都无法达到全 '0'（需要偶数个 '1'）或全 '1'（需要偶数个 '0'），答案为 "No"。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        int cnt0 = 0;
        int cnt1 = 0;
        for (char c : s) {
            if (c == '0')
                cnt0++;
            else
                cnt1++;
        }
        if (cnt0 % 2 == 1 && cnt1 % 2 == 1) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
        }
    }
}