文章

40

粉丝

512

获赞

13

访问

375.0k

头像
思路是用-1替换0,然后用前缀和的思想。主要的技巧是用map存begin,刚开始用两个循环直接炸了
Ang VIP
P1490 北京邮电大学2018年机试题
发布于2020年3月13日 18:41
阅读数 10.0k


#include<bits/stdc++.h>
using namespace std;

int main(){
    string str;
    while(cin>>str){
        map<int,int> m;
        int n=str.size();
        int dp[n];
        dp[0]=0;
        for(int i=1;i<=n;i++){
            if(str[i-1]=='0'){
                dp[i] = dp[i-1]-1;
            }else{
                dp[i] = dp[i-1]+1;
            }
        }
        int ans=0;
        int b=0;
        for(int i=1;i<=n;i++){
            b = m[dp[i]];
            if(b==0&&dp[i]!=0){
                m[dp[i]]=i;
            }else{
                if(i-b>ans){
                    ans = i - b;
                }
            }
        }
        cout<<ans<<endl;
    }
}

 

登录查看完整内容


登录后发布评论

1 条评论
laobo
2024年3月25日 20:30

你这代码21-24行太绝了,牛鼻

赞(0)