Codeforces 1231E Middle Out 题解

发表于 | 阅读次数：
本文字数： 1k 字 | 阅读时长 ≈ 4 分钟

题意简述

（$q$ 组数据）你有两个串，$s$ 和 $t$，长度都是 $n$。现在你可以对 $s$ 做若干次操作：选择某一个字符，把它移到最前面或者最后面（二选一）。

你现在要把 $s$ 变成 $t$，请问最少需要多少步操作。不行输出 $-1$。

$1\le q,n\le100$。

思路

先放结论：求出最长的串 $a$ 使得 $a$ 是 $s$ 的子序列（不一定连续），并且是 $t$ 的子串（必须连续），答案是 $n-|a|$，$|a|$ 表示 $a$ 的长度

怎么想到的

首先我们发现能任意从中间取字符放到首尾，根据某些直觉，我们发现：把不同的往两边放，把相同的留在中间对齐。

那么留在中间的“相同的”部分，想一想，应该是某一段公共子序列。

这一段公共子序列一定是最长公共子序列吗？不一定，发现我们 只能 对 $s$ 操作，不能动 $t$，所以这段公共子序列在 $t$ 中必须是连续的，不能有断开的。

就比如说样例第一个里面的第三组数据，$s=\texttt{“tste”}$，$t=\texttt{“test”}$，最长公共子序列应该是 $\texttt{“tst”}$，长度为 $3$。可是剩下的那一个字符 $\texttt{e}$ 并不能直接归位，因为要让它归位必须去动 $t$，但是我们只能动 $s$。最优策略应该是把 $\texttt{“st”}$ 放在中间，然后把 $\texttt{t}$ 和 $\texttt{e}$ 动两次归位。

然后现在还有一个问题：移动次数一定是 $n-|a|$ 吗？也就是说，剩下的 $n-|a|$ 个不同的恰好一定能在 $n-|a|$ 步之内归位？

分两步证，先证一定不小于这个数，然后证可以做到 $n-|a|$ 步，又因为我们要步数最小，就只能恰好是这个答案了。

一定不小于：如果能小于，那么我们的最长公共子序列 $a$ 就能变的更长了。所以一定不会小于这个数。

一定能取到：在 $t$ 中，由于 $a$ 是一个子串，于是 $t$ 中和 $s$ 不匹配的地方，就是 $t$ 中抠掉 $a$ 剩下的部分，一定是一段前缀加一点后缀。先从右到左遍历剩下的前缀，在 $s$ 中找一个相等的，放到最前面来。再从左到右遍历剩下的后缀，在 $s$ 中找一个相等的，放到最后面来。然后这个步数显然可以做到 $n-|a|$ 步。（附：关于这个从左到右还是从右到左，可以简单的概括为：从里到外）（为啥是从里到外，可以自己手玩一下）

怎么求

枚举这一段公共子序列在 $t$ 中的起点，然后写两个指针，匹配一下即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
#define N 122
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)
#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
#define p_b push_back
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define iter(a,p) (a.begin()+p)
#define Flandre_Scarlet int
#define IsMyWife main
char _c;
int I()
{
    int x=0; int f=1;
    while(_c<'0' or _c>'9') f=(_c=='-')?-1:1,_c=getchar();
    while(_c>='0' and _c<='9') x=(x<<1)+(x<<3)+(_c^48),_c=getchar();
    return (x=(f==1)?x:-x);
}
void Rd(int cnt,...)
{
    va_list args; va_start(args,cnt);
    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
    va_end(args);
}

int n;
string a,b;
void Input()
{
	n=I();
	cin>>a>>b;
}
void Soviet()
{
	int ans=1e9;
	F(i,0,n-1)
	{
		int pos=i;
		F(j,0,n-1) if (pos<n and b[pos]==a[j]) ++pos;
        // pos 表示在 t 中的位置，j 表示在 s 中的位置
        // pos-i 就是求出来的长度
		ans=min(ans,n-(pos-i));
	}

	sort(all(a)); sort(all(b)); if (a!=b){puts("-1");return;} // 判一下无解
	printf("%d\n",ans);
}
Flandre_Scarlet IsMyWife()
{
	int t=I();
	F(i,1,t)
	{
		Input();
		Soviet();
	}
	getchar();
	return 0;
}
w