题解

T1 购物

https://ac.nowcoder.com/acm/contest/7612/A

B 题
可以像区间dp断环成链一样,把字符串倍长。

假设序列倍长后长度是

那么对于每个 ,找到区间 的最大连续 1 的长度。

这里可以直接找出倍长后最长的连续 1 的长度,然后对 取个min即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read(){
     int x=0,f=0,ch=getchar();
    while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
    return f?-x:x;
}
const int MAX=2e5+5;
string s;
int ans,pre[MAX],len;
signed main(){
    cin>>s;len=s.length();
    s=s+s;
    for( int i=1;i<=s.length();++i)pre[i]=pre[i-1]+(s[i-1]=='1');
    for( int i=1,l=1;i<=s.length();++i){
        l=i;
        while(pre[i]-pre[l-1]==i-l+1)++i;
        ans=max(ans,i-l);
    }
    printf("%d\n",min(ans,len));
    return 0;
}
全部评论

相关推荐

小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务