题解：AT_arc183_b [ARC183B] Near Assignment

妙妙题。

先将 B 缩起来（颜色段缩成一个点），判掉颜色集不包含等显然的情况。

接下来处理

k=1

。我们发现操作只能将颜色向两边推，不能改变顺序。则可行条件是 A 存在一个字串与缩小后 B 串相等。

如果

k\ge 2

，考虑有连续的三个数 abc，可以通过操作产生 aab，baa。设 c 是无用的，则可以将与其相邻的两个数交换，也可以自己穿过两个数而不交换位置。

若缩小后 B 串长度小于

n

，则答案一定可以。因为我们可以先构造出一个乱序的 B 串，然后用空着的位置排序。若等于

n

，为了将 A 串排成 B 串的顺序，至少也得破坏一个点的数值。那个点需要在排序结束后用旁边相同颜色的点染回来。

CPP

/*

		2025.11.26

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=500005,inf=0x3f3f3f3f;
int n,a[MAXN],b[MAXN],tb[MAXN],tot,k;
map<int,int>vis,lst;
void solve(){
	vis.clear();lst.clear();
	cin>>n>>k;bool flag=1;tot=0;
	for(int i=1;i<=n;i++)cin>>a[i],vis[a[i]]=1,lst[a[i]]=-inf;
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)if(a[i]!=b[i])flag=0;
	if(flag){cout<<"Yes\n";return ;}
	for(int i=1;i<=n;i++)if(b[i]!=b[i-1])tb[++tot]=b[i];
	for(int i=1;i<=n;i++)if(vis.find(b[i])==vis.end()){cout<<"No\n";return ;}
	if(k==1){
		int l=1;
		for(int i=1;i<=n;i++)if(l<=tot&&a[i]==tb[l])l++;
		if(l==tot+1)cout<<"Yes\n";
		else cout<<"No\n";
		return ;
	}
	if(tot==n){
		for(int i=1;i<=n;i++){
			if(i-lst[b[i]]<=k){cout<<"Yes\n";return ;}
			lst[b[i]]=i;
		}
		cout<<"No\n";
	}
	else cout<<"Yes\n";
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--)solve();
	return 0;
}

题解：AT_arc183_b [ARC183B] Near Assignment

文章操作

相关推荐

评论

题解：AT_arc183_b [ARC183B] Near Assignment