题目理解

题目 1955E - Long Inversions 要求：
给定长度为 $n$ 的二进制字符串 $s$，选择一个整数 $k$（$1 \le k \le n$），可以进行任意次操作：选择连续 $k$ 个字符，将它们全部翻转（0→1，1→0）。
求最大的 $k$，使得可以通过若干次操作将字符串变成全 $1$。

解题思路

1. 关键观察

• 同一个子串不需要翻转两次，因为两次翻转等于没有操作。
• 对于固定的 $k$，我们可以用贪心策略检查是否可行：
  • 从左到右处理字符串，保证前 $i$ 个字符已经是 $1$。
  • 如果第 $i+1$ 个字符是 $0$，则必须翻转从 $i+1$ 到 $i+k$ 的区间（长度为 $k$）。
  • 不能翻转前面的字符，否则会破坏已经变成 $1$ 的部分。

2. 朴素检查的缺陷

如果每次遇到 $0$ 都真的去翻转 $k$ 个字符，检查一个 $k$ 的时间复杂度是 $O(n \cdot k)$，总复杂度会达到 $O(n^3)$，无法通过。

3. 优化方法：差分数组 + 翻转计数器

我们可以用一个变量 cnt 记录当前字符被翻转的次数（实际只需要奇偶性）。

• 当遍历到位置 $i$ 时，cnt 减去在 $i$ 处结束的翻转次数（用 end[i] 记录）。
• 当前字符的实际值 = 原值 $\oplus$ ( cnt % 2 )。
• 如果实际值是 $0$，则需要从 $i$ 开始进行一次翻转：
  • 在 $i+k$ 处标记这次翻转结束：end[i+k]++
  • cnt++（增加一次翻转影响）
  • 当前字符变为 $1$

这样，每次遇到 $0$ 只需要 $O(1)$ 时间更新，整个检查过程是 $O(n)$。

4. 算法步骤

1. 从大到小枚举 $k$（$k = n$ 到 $1$）。
2. 对每个 $k$ 用 $O(n)$ 时间检查可行性：
   • 初始化 cnt = 0，end 数组全 $0$。
   • 遍历 $i = 0$ 到 $n-1$：
     • cnt -= end[i]
     • 实际值 = $s[i] \oplus (cnt \& 1)$
     • 如果实际值为 $0$：
       • 若 $i + k \le n$，则进行翻转：end[i+k]++, cnt++
       • 否则，这个 $k$ 不可行
   • 遍历结束后，检查是否所有位置都变成 $1$
3. 找到第一个可行的 $k$ 并输出。

5. 复杂度分析

• 枚举 $k$：$O(n)$ 次
• 每次检查：$O(n)$
• 总复杂度：$O(n^2)$
• 题目保证所有测试用例的 $\sum n^2 \le 25 \times 10^6$，可以接受。

代码详解

void solve() {
    int n;
    string s;
    cin >> n >> s;
    
    // 从大到小枚举 k
    for (int k = n; k > 0; --k) {
        vector<char> t(n), end(n + 1);
        
        // 将字符转为数字 0/1
        for (int i = 0; i < n; ++i) {
            t[i] = s[i] - '0';
        }
        
        int cnt = 0;  // 当前翻转次数（只关心奇偶）
        
        for (int i = 0; i < n; ++i) {
            cnt -= end[i];           // 移除在 i 处结束的翻转
            t[i] ^= (cnt & 1);       // 应用翻转效果
            
            if (t[i] == 0) {         // 需要翻转
                if (i + k <= n) {
                    ++end[i + k];    // 标记翻转结束位置
                    ++cnt;           // 增加翻转次数
                    t[i] = 1;        // 当前位置变成 1
                } else {
                    break;           // 无法完成
                }
            }
        }
        
        // 检查是否全为 1
        if (*min_element(all(t)) == 1) {
            cout << k << '\n';
            return;
        }
    }
    assert(false);  // 理论上至少 k=1 可行
}

示例验证

输入：

5
00100

枚举 $k=5$：检查失败（最后一个 $0$ 无法覆盖）
$k=4$：检查失败
$k=3$：检查成功，输出 $3$

符合题意。