P13885 [蓝桥杯 2023 省 Java/Python A] 反异或 01 串题解

zpy12345 · 2026-08-07 20:26:11 · 题解

• Problem

假设一个 T 的一个子串是经过反异或操作得到的，那么有以下性质。

• 这个子串一定是回文串。
• 如果子串大小为奇数，则子串的回文中心一定为 0。
• 如果子串的某个位置为 1，那么原来一定是一个 0 一个 1。
• 如果子串的某个位置为 0，为了使用最少的 1，那么原来一定是两个 0。

于是这样一个子串可以使我们少使用该子串内 1 的个数 /2 个 1。

Manacher 即可。