题解 CF2164D Copy String

【本版】25/11/2025 更新：怎么忘记打代码块了呜呜……实在抱歉，一篇题解交了三次
25/11/2025 更新：修复了数学语言问题。~~不过 OI 不都是这么写吗（ $s[l,r]$ 表示从 $s_l$ 到 $s_r$ 的子串）~~

题意

给定字符串

s,t

，令

s_0=s

，你可以进行若干次操作，第

i

次操作得到

s_i

，其中

s_{i,j}

可以从

s_{i-1,j}

和

s_{i-1,j-1}

中选一个（

j=1

时显然不能选后者）。

试问能否用不超过

k_{\max}

次操作使得最后一次操作得到的

s_k=t

，如果可以，求出最小的

k

并给出一组构造方案。

数据范围：多测，

\sum nk_{\max}\le 10^6

。

做法

容易想到一种直接匹配的方法：枚举

s_i

并维护指针

p

使其与

t

中各项匹配并记录每个

i

匹配到的

p

（记作

r_i

），这个过程中如果枚举到某个

i

时

p<i

则匹配失败（依照题意字符只能往右移动），匹配成功后若

\max\{r_i-i\}>k_{\max}

仍视为匹配失败，否则操作次数即为

\max\{r_i-i\}

，依题意模拟即可。

但是这个东西跑样例 #5 会输出

-1

。

CPP

10 3
vzvylxxmsy
vvvvvllxxx

原因是

t_0,t_1,\dots,t_4

全部匹配给了

s_0

。

所以上述方法求出来的方案不是最优的。

于是考虑当当前

r_i-i=k_{\max}

时强行结束

s_i

的匹配。

然后会发现我把

k_{\max}

开大点它又炸了。

然后发现他是放

nk_{\max}

过的，所以直接从小到大枚举操作次数，然后用上上面强行结束匹配的思路，匹配完输出答案之前再确定一遍是否能够到达最终状态（有时只判

p<i

判不掉一些情况）即可。复杂度

O(nk_{\max})

。

代码

CPP

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<cassert>
#define ll long long
#define lf double
#define ld long double
using namespace std;
ll T,n,k,l[1000010],r[1000010],lst[30];
string s,t;
bool work(ll now){
	ll p=0;
	bool flg=0;
	memset(lst,-1,sizeof(lst));
	for(int i=0;i<n;i++){
		if(p<i){
			flg=1;
			break;
		}
		l[i]=p;
		while(p<n&&t[p]==s[i]){
			if(p-1-i==now)break;
			p++;
		}
		r[i]=p-1;
	}
	if(flg){
		return false;
	}
	string tmp=s;
	for(int i=1;i<=now;i++){
		for(int j=0;j<n;j++){
			if(j+i<=r[j]){
				tmp[j+i]=s[j];
			}
		}
	}
	if(tmp!=t){
		return false;
	}
	cout<<now<<endl;
	tmp=s;
	for(int i=1;i<=now;i++){
		for(int j=0;j<n;j++){
			if(j+i<=r[j]){
				tmp[j+i]=s[j];
			}
		}
		cout<<tmp<<endl;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		cin>>n>>k>>s>>t;
		bool flg=0;
		for(int i=0;i<=k;i++){
			if(work(i)){
				flg=1;
				break;
			}
		}
		if(!flg){
			cout<<-1<<endl;
		}
	}
	return 0;
}

题解 CF2164D Copy String

文章操作

题解 CF2164D Copy String

题意

做法

相关推荐

评论

题解 CF2164D Copy String