题意
给一个长度为 \(n\) 的 01 串 \(s\)，可以至多进行 \(k\) 次操作，每次操作可以把任意子串取反，求操作后最长的连续 1 串长度。
分析
\(n\) 的范围“友好” 地告诉我们最大 \(O(n\log n)\)。
最开始想的是把每一块分出来跑 dp，然后发现写不出来 \(O(n)\) 的式子。（去世）
想了一会后注意到题目中 任意一个子串，突然想到双指针。
设 \(l,r\) 分别表示左端点和右端点，\(f_i\) 表示第 \(i\) 位前全 0 的块数。所以使 \([l,r]\) 区间内全为 1 所需要的操作次数为 \(f_r-f_{l-1}\)。若 \(s_l\) 是两块的交界，那么答案还要加一。
总时间复杂度 \(O(n)\)。
Code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll maxn=1e5+5;
ll n,k,f[maxn],ans;
char s[maxn];
signed main(){
n=read(),k=read();
s[0]='1';
for(ll i=1;i<=n;++i)cin>>s[i];
for(ll i=1;i<=n;++i)f[i]=f[i-1]+(s[i-1]=='1'&&s[i]=='0');
ll l=1,r=1;
while(r<=n){
if(l==r||f[r]-f[l-1]+(s[l-1]=='0'&&s[l]=='0')<=k){
++r,ans=max(ans,r-l);
}
else ++l;
}
printf("%lld",ans);
}