蓝桥杯2023年第十四届省赛真题-反异或 01 串

初始有一个空的 01 串，每步操作可以将 0 或 1 添加在左侧或右侧。也可以对整个串进行反异或操作: 取 s ′ = s ⊕ rev(s)，其中 s 是目前的 01 串，⊕ 表示逐位异或，rev(s) 代表将 s 翻转，也就是说取中心位置并交换所有对称的两个位置的字符。例如，rev(0101) = 1010 rev(010) = 010 rev(0011) = 1100。

反异或操作最多使用一次（可以不用，也可以用一次）。

给定一个 01 串 T，问最少需要添加多少个 1 才能从一个空 01 串得到 T。

在本题中 0 可以添加任意个。

输入一行包含一个 01 串表示给定的 T 。

输出一行包含一个整数，表示需要最少添加多少个 1 。

对于 20% 的评测用例，|T| ≤ 10 ；

对于 60% 的评测用例，|T| ≤ 5000 ；

对于 80% 的评测用例，|T| ≤ 10⁵ ；

对于所有评测用例，1 ≤ |T| ≤ 10⁶，保证 T 中仅含 0 和 1 。