Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-反异或 01 串
题目 3170:

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

时间限制: 2s 内存限制: 320MB 提交: 383 解决: 64

题目描述

初始有一个空的 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 。

样例输入

00111011

样例输出

3

提示

对于 20% 的评测用例,|T| ≤ 10 ;

对于 40% 的评测用例,|T| ≤ 500 ;

对于 60% 的评测用例,|T| ≤ 5000 ;
对于 80% 的评测用例,|T| ≤ 105
对于所有评测用例,1 ≤ |T| ≤ 106,保证 T 中仅含 0 和 1 。


标签