Anye
Anye
Published on 2019-11-13 / 16 Visits
0
0

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

建议

做此题前先去看看这道题:P1739 表达式括号匹配

这道题是作为入门题出现的,主要的思路是用 解决,为什么这么讲呢,emmmm~ STL也算是我们 C++ 党的一大优势对吧

思路

进入正题

我们其实可以将相邻的两个不同的数字给消去,舍去开头的 1 ,例如样例中给的 0111100101 我们按照规则对其进行处理,得到 01 111 00 10 1

可以发现,这里最后就剩下两个 0 了,可能有人会问:为什么最后的那个 1 不取呢? 这里解答一下,因为题目中未对子串进行要求,所以我们的子串可以取任意长度,只需使结果最大就可以了,如果这里把 1 取到了,就会使结果更小,所以这个 1 当然就会被舍去了。

对比

为什么说这道题很像 P1739 表达式括号匹配 呢,不知大家有没有发现,这里的 与 0 相邻的 1 可以看做是括号匹配中的 ‘ )’,把 0 看做是‘(’,那么就会发现,其实这道题就是在寻找不能匹配的括号数。

那么我们就可以用栈来进行 0 1 的配对消除

if(a[i]=='0')	cxk.push(1);
if(a[i]=='1'&&(!cxk.empty()))	cxk.pop();		
maxx=max(maxx,k);

但是我们真的已经考虑到所有情况了吗?

想一想,会有两种特殊情况,一种是全是 1 的情况,另一种是全 0 的情况,那么我们会发现,我们需要对全 1 的情况进行特判;只需要在扫描的过程中加入对 1 的计数即可(当 1 的个数==size时,输出 -1(全 1 的话 0 的个数为0,那么0-1=-1)

鉴于这个难度,那么最后附上 AC (chou) 代码

代码

#include<bits/stdc++.h>
using namespace std;
string a;
int mn;
long long maxx;
signed main(){
    ios::sync_with_stdio(false);
    cin>>a;
    stack<int>cxk;
    for(int i=0;i<=a.size();i++)
    {	if(a[i]=='1') mn++;
        long long k=cxk.size();
        if(a[i]=='0')	cxk.push(1);
        if(a[i]=='1'&&(!cxk.empty()))	cxk.pop();		
        maxx=max(maxx,k);
    }
    if(mn==a.size()) cout<<"-1";
    else cout<<maxx<<endl;
    return 0;
}

最重要的一点就是任何题一定要考虑特殊情况 (貌似没特判全 1 情况的话是90分?)

码风及代码习惯不好,莫效仿


Comment