题解 P5650 【基础字符串练习题】

· · 题解

蒟蒻的题解

原题在这里
向管理员致歉：\LaTeX 爆炸了 调试了好多遍，浪费了管理员的时间，抱歉
鄙人蒟蒻又来水比赛了。。。虽然其余题目大红大紫这道题\color{green}\mathfrak{AC}还是真的。。。
先让我们来捋一下思路：
标题——基础字符串题，所以这道题一定和字符串有关
背景——没有用不过还要不明就里地膜拜YSGHdalao
描述——重要！

S是一个01串，这就可以减去很多特判

T这个串是S的 非空 子串，这就告诉我们 当出现111111这样的S串时答案 不可以是-1！！！
T要满足 0 的个数减去 1 的个数最大

然后窝们可以来思考：这道水题怎样做呢？？？
第一我们可以想到，可以忽略掉所有的1，统计连续出现的最多的 0
但是反例不难举出：当串为 00100 时答案是 3 而不是 2
所以我们继续深入探究，不难发现可以用两个计数器统计 0 和 1 的个数，然后比较两计数器的值并且和最大值打擂台
所以 \color{green}\mathfrak{AC}代码如下，代码里也有分析： 

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;//头文件不解释 
int main(){
    char a[100001];//定义char数组
    cin>>a;//神犇同学3300872109a告诉我输入可以用int，具体是scanf("%1d",&a[i]); 
    int lena=strlen(a),tm1=0,tm0=0,maxx=-1;//定义出现的1的次数，0的次数
    //划重点：题目中说了子串S不为空所以maxx必须等于-1 
    //为了应对极端情况1111111111 
    for(int i=0;i<lena;i++){
        if(a[i]=='0'){//如果对应字符是0 
            tm0++;//0的次数++ 
        }
        if(a[i]=='1'){//如果对应是1 
            tm1++;//1的次数++ 
        }
        if((tm0-tm1)>=maxx){//如果两个个数相减大于maxx 
            maxx=tm0-tm1;//maxx被替换 
        }
        if(tm1>=tm0){//如果1的个数 大于了0的个数 
            tm0=0; 
            tm1=0;//重置进入下一个循环 
        } 
    }
    printf("%d",maxx);//咻~~输出了 
    return 0;//完结撒花 
}

题解到此结束，蒟蒻不易，如果诸位大佬不嫌弃，点个赞 再走呗~