首杀纪念

提供一种思路:二分答案

一:题意:

略

二:正确性

1.答案具有单调性 假设最少操作 $k$ 次,显然操作次数不可能小于 $k$ 次,当操作次数大于k时显然可以成功

所以我们可以得出结论:答案具有单调性,满足二分条件

三:做法:

由题意可知,当 $S$ 和 $T$ 的字母组成不完全相同时,显然无法将 $S$ 操作为 $T$ ,此时输出 $-1$

当S和T字母组成相同时,我们可以得到这样一个结论:

若 $S[k]$ ~ $S[n-1]$ 为T的一个子序列,则只用操作 $S[0]$ ~ $S[k-1]$ 即可将 $S$ 操作为 $T$ ,证明如下:

当 $S$ 自位置 $k$ 后是 $T$ 的子序列,我们可以将位置 $k$ 之前的字母插入所需的位置,如下图所示:

详见代码

四:时间复杂度:

二分为 $log(n)$

每次检查为 $n$

总时间复杂度为 $nlog(n)$ ,可以通过本题

五:提示

需要注意的是,本体数据非常非常水,导致很多错误复杂度(比如不进行二分直接枚举检查)甚至错误方法都可以通过本题,因此建议去提交ARC154 B与本题除数据外完全一致

六:代码

#include<bits/stdc++.h>
using namespace std;
string s,t;
int n;
int sts[30],stt[30];
int op[214514];
int a[214514],cnt;
int ans;
int l,r,mid;
int res;

bool check(int x){//检查 
	res=0;
	for(int i=x;i<n;i++){
		while(s[i]!=t[res]&&res<n)
			res++;	
		if(s[i]!=t[res])
		  return 0;	
		res++;
	}
	return 1;
}

int Main(){
	cin>>n>>s>>t;
	
	for(int i=0;i<n;i++){
		sts[s[i]-'a'+1]++;

	}	
	  
	for(int i=0;i<n;i++)
	  stt[t[i]-'a'+1]++;
	
	for(int i=1;i<=26;i++)//比较S和T字母组成是否相同 
		if(sts[i]!=stt[i])
		  ans=-1;
	
	if(ans==-1){
	  cout<<-1;	
	  return 0;
	}  
	
	l=1,r=n-1;
	while(l<r){//二分 
		mid=(l+r)>>1;
		if(check(mid))
		  r=mid-1;
		else
		  l=mid+1;  
	}
	
	for(int i=max(0,l-50);i<=min(n-1,r+50);i++)//二分防挂 
	  if(check(i)){
	  	cout<<i;
	  	break;
		}
	
	return 0;
}