题目链接

Codeforces 2276 B - Replace and Compress

题目描述

给定一个长度为 \(n\) 的字符串 \(s\)，其中只包含字符 0 和 1。你需要恰好执行一次由以下两步组成的操作：

1. 选择至多一个下标在 \(2\) 到 \(n-1\)（含）之间的字符，并将其取反：0 变为 1，或 1 变为 0。也可以不修改任何字符。字符串的第一个和最后一个字符不能修改。
2. 将每个由相同字符连续组成的极大块替换为一个该字符。

如果一个块无法向左或向右扩展相同字符，则称其为“极大块”。例如，第二步后，字符串 100111011 会变为 10101。

请计算执行该操作后，能够得到多少个不同的字符串。

输入

第一行包含整数 \(t\)（\(1 \le t \le 10^4\)），表示测试用例数量。

每个测试用例包含一行字符串 \(s\)：

• \(3 \le |s| \le 3 \times 10^5\)
• \(s\) 仅由 0 和 1 构成。

额外保证：所有测试用例的字符串长度之和不超过 \(3 \times 10^5\)。

输出

对于每个测试用例，输出一个整数：执行操作后可得到的不同字符串数量。

示例

输入：

7
001
000
010
00010
100111011
001011010
1111

输出：

1
2
2
3
3
2
2

说明

第一个测试用例中，可以不修改字符，或修改第二个字符：

• 001 → 压缩后为 01
• 011 → 压缩后也为 01

因此答案为 1。

第五个测试用例 100111011 中：

• 不修改字符：压缩后得到 10101
• 修改第 2 个字符：110111011 → 10101
• 修改第 5 个字符：100101011 → 1010101
• 修改第 7 个字符：100111111 → 101

因此，一共能得到 3 个不同字符串：101、10101、1010101。

思路

首先我们注意到，一切的结果都是0和1的交替块，然后首字符是固定的。因此，压缩后的字符串只能通过块的数量来决定。那样问题就变成了统计能够得到多少种不同的块数量。

设原字符串块的数量为 \(r\), 反转内部 $i$ ($2 \le i \le n-1$) 后，块的数量可能会增加或减少。而这个增加与减少的情况取决于当前字符和其相邻字符的关系。

1. triple. 当位于一段的中间时，条件为 s[i-1] == s[i] == s[i+1]，反转后块的数量会增加 2。
2. isolated. 当是孤立的字符时，条件为 s[i-1] == s[i] != s[i+1]，反转后块的数量会减少 2。
3. 其他情况下，块的数量不会改变。

不反转的情况下可以直接得到 \(r\) 。而反转后，块数量只可能增加 2、减少 2 或保持不变。因此，答案为：

代码

#include <iostream>

using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();

        bool triple = false;
        bool isolated = false;

        for (int i = 1; i <= n - 2; i++) {
            if (s[i - 1] == s[i] && s[i] == s[i + 1]) {
                triple = true;
            } else if (s[i - 1] == s[i + 1] && s[i] != s[i - 1]) {
                isolated = true;
            }
        }

        cout << 1 + triple + isolated << '\n';
    }
    return 0;
}

复杂度

时间复杂度：\(O(n)\)

空间复杂度：\(O(1)\)