A50246.午枫的01串翻转

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

小枫有一个长度为 nn0101ss ,这个 0101 串从左往右的第 ii 个数为 sis_i ,小午可以对这个 0101 串做任意次(可以不做)操作:

  • 选择一段区间 [l,r][l,r] 满足 1l<rn,sl=0,sr=11 \leq l < r \leq n, s_l=0,s_r=1
  • 对于这段区间的每一位 si(lir)s_i(l\leq i \leq r) ,将其变为 si1s_i \oplus 1 ,其中 \oplus 表示按位异或。

小枫想知道小午操作后得到的所有可能的 0101 串中,距离最远的两个 00 的距离是多少。

特别的,如果没有 00 或只有一个 00 的情况,我们视为其的距离为 00

距离:两数所在位置差值的绝对值,例如,两个数的位置分别是 aabb ,则两数的距离为 ab|a-b|

输入格式

第一行输入一个正整数 nn (1n106)(1\leq n\leq 10^6) ,表示字符串长度。

第二行输入一个长度为 nn0101ss ,表示初始 0101 串,保证 si{0,1}s_i\in\{0,1\}

输出格式

输出一个整数,表示所有可能的 0101 串中,距离最远的两个 00 的距离是多少。

输入输出样例

  • 输入#1

    5
    10101

    输出#1

    3

说明/提示

可以选择区间 [4,5][4,5] 操作后得到 1011010110 ,此时两个 00 的最远距离为 52=35-2=3

首页