P12505 「ROI 2025 Day2」充实的假期

Back to the problem.。

better service。

标签：贪心，分类讨论。

前置知识：小学数学，for,if。

题面

给一个 01 字符串，每次问插入 $x$ 个 1，求最多的连续的 1 的数目（当有两个及以上的 1 在一起，他们就是连续的 1）。

思路

注意到求 1 的数目而不是最大长度，所以考虑每次加 1 的贡献最大的直接贪心，即贡献越大越优先，可进行分类讨论。

（按贡献从大到小）：

1. 形如 101，发现如果将中间的 0 填补，有 $3$ 个贡献。

2. 形如 10 或 01，发现将中间（旁边？）的 0 填补，有 $2$ 个贡献。

3. 形如 0，将其填充获得 $1$ 个贡献。

特别的，不能重复贡献，所以设置 $1$ 个 vis 数组记录是否已经算进贡献里了。

其中的第 $3$ 点中形如 0 填充的可以算 $1$ 个贡献其实并不需要考虑是否连续，因为按照优先级肯定可以到有 1 的旁边达成连续。这种情况也有特殊，如全是 0，需要进行特判。

代码

欣赏吧。

#include<bits/stdc++.h>
const int M=1e5+5;;
using namespace std;
int n,q,ans=0,a1=0,a2=0,a3=0,ys=0;
bool vis[M];//不能重复贡献
string c;
void calc(){//计算每一种 010，01,0 的个数
	for(int i=1;i<c.size();i++){
		if(!vis[i]&&c[i-1]=='1'&&!vis[i-1]&&c[i]=='0'&&c[i+1]=='1'&&!vis[i+1]){a1++;vis[i-1]=1;vis[i]=1;vis[i+1]=1;}
	}
	for(int i=1;i<c.size();i++){
		if(!vis[i]&&c[i-1]=='1'&&!vis[i-1]&&c[i]=='0'){a2++;vis[i-1]=1;vis[i]=1;}
		else if(!vis[i]&&c[i+1]=='1'&&!vis[i+1]&&c[i]=='0'){a2++;vis[i+1]=1;vis[i]=1;}
	}
}
int query(int sl){//O(1)进行计算
	if(ys==0)return sl<=1?0:sl;
	if(sl<=a1)return sl*3;
	if(sl>a1&&sl<=a1+a2)return a1*3+(sl-a1)*2;
	return a1*3+a2*2+sl-a1-a2;
}
int main(){
	memset(vis,0,sizeof(vis));
	scanf("%d%d",&n,&q);
	cin>>c;
	for(int i=0;i<c.size();i++)if(c[i]=='1')ys++;
	for(int i=1;i<c.size();i++){
		if(c[i]=='1')ys++;
		if(c[i]=='1'&&c[i-1]=='1'){
			if(!vis[i-1]){
				ans++;vis[i-1]=1;
			}
			ans++;vis[i]=1;
		}
	}
	calc();
//	cout<<a1<<' '<<a2<<'\n';
//  调试代码
	while(q--){
		int x;scanf("%d",&x);
		printf("%d\n",ans+query(x));
	}
}