题目链接:https://ac.nowcoder.com/acm/problem/213314

到主站看:https://blog.csdn.net/weixin_43346722/article/details/109408895

题目

给一个长度为 的 01 序列 ,现在可以至多进行 次如下操作:
选择 ,将 序列变成

输出最长的全为 的子区间长度。

输入

一个 01 字符串,表示序列

输出

输出一个整数表示答案。

样例输入1

1001

样例输出1

2

样例输入2

11111

样例输出2

5

样例输入3

10111010

样例输出3

3

思路

这道题就是一道模拟题。

分开讨论,看不操作和只操作一次最多能有多大的答案。
(因为最多只能操作一次)

第一:
不操作。
那我们就直接 O(n) 扫过去,找到最长的连续是一的序列长度。

第二:
操作一次。
我们可以通过题目看出,它操作其实就是把序列分成两个区间,然后把两个区间整个对调。
那如果要产生更长的都为一的子序列,就一定是在新的序列中两个区间的交界处扩散开来的。
那这个子序列是由新序列左区间的右边和右区间的左边共同构成的。
那变回到翻转之前,就是原本区间右区间的右边和左区间的左边。
那我们就直接枚举两边开头有多少连续的 ,个数加在一起就是操作一次所能得到的最长长度。
(有一个要注意的就是如果两边开头连续 的数量超过了序列长度,那所能得到的最长长度是
(就比如说:,你两边扫过去都是 ,加起来是 ,但是实际只有 个)

然后这两种得出来的值取最大值,就是答案了。

比赛时

一开始把最多看成了最少,想了一会觉得奇怪,就又看了一下题,发现是最多。

然后就想到要分来来求。

然后就码出来了。

图片说明

代码

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int n, ans, now, preerp, to;
char a[100001];

int main() {
    scanf("%s", &a);
    n = strlen(a);

    for (int i = 0; i < n; i++)//不进行操作
        if (a[i] == '1') now++;
            else {
                ans = max(ans, now);
                now = 0;
            }

    if (now) ans = max(ans, now);

    for (to = 0; to < n; to++)//操作一次
        if (a[to] == '0') break;
            else preerp++;

    for (int i = n - 1; i > to; i--)
        if (a[i] == '0') break;
            else preerp++;

    ans = max(ans, preerp);
    printf("%d", ans);

    return 0;
}