题解：P12505 「ROI 2025 Day2」充实的假期

· · 题解

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));
    }
}