A50246.午枫的01串翻转
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
小枫有一个长度为 n 的 01 串 s ,这个 01 串从左往右的第 i 个数为 si ,小午可以对这个 01 串做任意次(可以不做)操作:
- 选择一段区间 [l,r] 满足 1≤l<r≤n,sl=0,sr=1 。
- 对于这段区间的每一位 si(l≤i≤r) ,将其变为 si⊕1 ,其中 ⊕ 表示按位异或。
小枫想知道小午操作后得到的所有可能的 01 串中,距离最远的两个 0 的距离是多少。
特别的,如果没有 0 或只有一个 0 的情况,我们视为其的距离为 0 。
距离:两数所在位置差值的绝对值,例如,两个数的位置分别是 a 和 b ,则两数的距离为 ∣a−b∣ 。
输入格式
第一行输入一个正整数 n (1≤n≤106) ,表示字符串长度。
第二行输入一个长度为 n 的 01 串 s ,表示初始 01 串,保证 si∈{0,1}
输出格式
输出一个整数,表示所有可能的 01 串中,距离最远的两个 0 的距离是多少。
输入输出样例
输入#1
5 10101
输出#1
3
说明/提示
可以选择区间 [4,5] 操作后得到 10110 ,此时两个 0 的最远距离为 5−2=3 。