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

Dear 丶 2022-09-25 06:22 82阅读 0赞

## 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][http_acm.zzuli.edu.cn_zzuliacm_problem.php_id_1895]

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=1895
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1895
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1895
[hpu]: http://acm.zzuli.edu.cn/zzuliacm/problemset.php?search=hpu
[http_acm.zzuli.edu.cn_zzuliacm_problem.php_id_1895]: http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1895