【985系列】985的0-1串难题

1895: 985的0-1串难题

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 270   Solved: 79 Submit Status Web Board

Description

985有一个长度为n的0-1串，已知他最多可以修改k次（每次修改一个字符即0->1 或者 1->0），他想知道连续的全1子串最长是多少。

Input

第一行输入一个整数t，代表有t组测试数据。 每组数据第一行输入两个整数n，k分别代笔上面的信息。 注：1 <= t <= 12，1 <= n <= 100000，0 <= k <= 100000。

Output

一个整数代表可以得到的最大长度。

Sample Input

2 6 3 010100 6 2 010100

Sample Output

5 4

HINT

Source

hpu

为什么说经典呢，因为本题思维过程很巧妙，你要1的连续的串最长就要把0改为1，不可能把1改为0；

然后用一个数组存储，下标存储0的个数，实际存储的是0在整个序列中出现的次序，就是第几次出现的。

如果k个0的区间内实际数组值序列相差最大就说明此区间1的个数最多，也就是题目所求。

注意要把整个串的前面和后面都加一个0。

ac代码：

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N = 100005; int cu[N]; char s[N]; int main() { int T; scanf("%d",&T); while(T--) { int n,k,cnt=0; scanf("%d%d%s",&n,&k,s); cu[cnt++]=0; for(int l=0; l<n; l++) { if(s[l]=='0') cu[cnt++]=l+1; } cu[cnt++]=n+1; if(k>=cnt-2) { printf("%d\n",n); continue; } int ans=0; for(int i=k+1; i<cnt; i++) { ans=max(ans,cu[i]-cu[i-k-1]-1); } printf("%d\n",ans); } return 0; }我为什么说这题好呢，以为用二分也能做 ac代码： #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 100005; char c[N]; int cnt[N]; int n,k; void charge() { if(c[0]=='0') cnt[0]=1; for(int i=1; i<n; i++) { if(c[i]=='0') cnt[i]++; cnt[i]+=cnt[i-1]; //printf("%d--\n",cnt[i]); } } bool judge(int mid) { if(cnt[mid-1]<=k) return true; for(int i=0; i+mid<n; i++) { if(cnt[i+mid]-cnt[i]<=k) return true; } return false; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d%s",&n,&k,c); memset(cnt,0,sizeof(cnt)); charge(); int l=0,r=n; int mid,ans=0; while(l<=r) { mid=r+l>>1; if(judge(mid)) { ans=mid; l=mid+1; } else { r=mid-1; } } printf("%d\n",ans); } return 0; } 题目地址：http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1895