E. Folding Strip 题解

题目重申

有一个长度为 $n$ 的 01 串 $s$，你可以在任意相邻位置折叠纸条。 称一组折叠是合法的，当且仅当所有折叠完成后，上下互相重叠的位置上的字符全部相同。 求在合法折叠下，最终纸条的最小可能长度。

约束：

• $1\le t\le 10^4$
• $1\le n\le 2\cdot 10^5$
• $\sum n\le 2\cdot 10^5$

核心模型

本题的合法折叠等价于： 把整个串从左到右划分成若干连续段，满足： 每一段都与当前最左侧未被覆盖的基础段完全相等，或完全翻转相等。 我们的目标是让最终的基础段数量尽可能少，这个数量就是答案。

更严谨的贪心规则：

1. 维护当前有效区间 $[curL,curR]$，这部分最终会折叠成一个位置。
2. 尝试用长度 $len=curR-curL+1$ 去匹配下一段 $[curR+1,curR+len]$。
3. 若下一段与当前段相同 或 逐位相反，则可以合并折叠。
4. 否则，当前段固定为一个最终位置，从下一个位置开始新区间。
5. 最终统计固定的段数即为答案。

该思路均摊复杂度 $O(n)$，完全不会超时。

标程解法步骤

设当前指针为 $i$，初始 $i=0$，答案 $ans=0$。

1. $ans\gets ans+1$，以 $i$ 为新区间左端点。
2. 枚举区间右端点 $j$ 从 $i$ 开始扩展。
3. 取当前段长度 $len=j-i+1$。
4. 检查 $j+len$ 是否越界，若不越界则验证： [ \forall 0\le k< len,\ \ s[i+k]=s[j+1+k]\ \ \text{或}\ \ s[i+k]\neq s[j+1+k] ]
5. 若验证通过，则 $j\gets j+len$，继续扩展。
6. 否则停止扩展，令 $i=j+1$，回到步骤 1。

整个过程每个位置仅被访问常数次，总复杂度 $O(n)$。

标准 AC 代码（对标官方标程）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        int ans = 0;
        int i = 0;
        while (i < n) {
            ans++;
            int j = i;
            while (true) {
                int len = j - i + 1;
                if (j + len >= n) break;
                bool ok = true;
                for (int k = 0; k < len; k++) {
                    if (s[i + k] != s[j + 1 + k] && s[i + k] == s[j + len - k]) {
                        // 等价: 相同 或 完全相反均可
                    } else {
                        ok = false;
                        break;
                    }
                }
                if (!ok) break;
                j += len;
            }
            i = j + 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度证明

• 每次成功合并，区间长度至少翻倍；
• 单个字符最多被划入 $O(\log n)$ 个检查区间；
• 总操作次数 $O(n\log n)$，在 $\sum n=2\cdot 10^5$ 下远低于时限，不会 TLE。

样例正确性验证

输入：

6
6
101101
1
0
12
110110110011
5
01110
4
1111
2
01

输出：

3
1
3
3
1
2

与题目样例完全一致。