题解：CF2125F Timofey and Docker

· · 题解

ez 题。

首先 docker 是由 6 个不同字母组成，所以不用考虑存在它的前缀和后缀有公共子串。

我们设 f_i 表示有 i 个 docker 时的最少修改次数，如果原串有 now 个 docker，那么当 i\le now 时，f_i=now-i。

接着考虑 i>now 的情况，容易发现，f 在 (now,\frac{n}{6}) 是单调不降的，所以我们只用找到最小的 x，满足 x 是被 [l_i,r_i] 包含次数最多并且大于 now 的，那么我们就只用算这一个 f_x 即可。

不难发现，其实 f 在 (now,\frac{n}{6}) 不仅是单调不降，还是一个下凸包，所以我们直接考虑 wqs 二分，check 的时候做一个 dp 即可。

#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
using namespace std;
inline int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int Maxn=5e5+5,inf=1e9+7;
char s[Maxn];
int n,m;
int id,val;
int b[Maxn];
struct node{
    ll val;int i;
}f[Maxn];
inline node Min(node a,node b){return a.val==b.val?(a.i<b.i?a:b):a.val<b.val?a:b;}
inline node check(int k){
    f[0]={0,0};
    for(int i=1;i<=n;i++)f[i]={inf,0};
    for(int i=0;i<n;i++){
        f[i+1]=Min(f[i+1],f[i]);
        if(i+6<=n){
            f[i].i++;f[i].val+=(s[i+1]!='d')+(s[i+2]!='o')+(s[i+3]!='c')+(s[i+4]!='k')+(s[i+5]!='e')+(s[i+6]!='r')-k;
            f[i+6]=Min(f[i+6],f[i]);
        }
    }
    return f[n];
}
inline void solve(){
    scanf("%s",s+1);
    n=strlen(s+1);
    int now=0;
    for(int i=1;i+5<=n;i++)
        now+=(s[i]=='d'&&s[i+1]=='o'&&s[i+2]=='c'&&s[i+3]=='k'&&s[i+4]=='e'&&s[i+5]=='r');
    for(int i=0;i<=n/6;i++)b[i]=0;
    m=read();
    for(int i=1;i<=m;i++){
        int l=read(),r=min(n/6,read());
        if(l<=r)b[l]++,b[r+1]--;
    }
    id=val=0;
    for(int i=1;i<=n/6;i++)b[i]+=b[i-1],val=max(val,b[i]);
    int ans=1e9+7;
    for(int i=0;i<=now;i++)if(b[i]==val)ans=now-i;
    for(int i=now+1;i<=n/6;i++)if(b[i]==val){id=i;break;};
    if(!id)return void(printf("%lld\n",ans));
    int l=0,r=n,mid,res=0;
    while(l<=r){
        mid=l+r>>1;
        node tp=check(mid);
        if(tp.i<=id)res=mid,l=mid+1;
        else r=mid-1;
    }node tp=check(res);
    printf("%lld\n",min(ans,tp.val+id*res));
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T=read();
    while(T--)solve();
    return 0;
}