题解：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 即可。

CPP

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

题解：CF2125F Timofey and Docker

文章操作

相关推荐

评论

题解：CF2125F Timofey and Docker