Sofia and Strings

题面翻译

\(t\) 组数据。

每一次测试，有长度为 \(n\) 的序列 \(s\)，长度为 \(m\) 的序列 \(t\)。

你可以对 \(s\) 进行两种操作：

1. 删除 \(s_i,1\le i\le |s|\)（\(s\) 从 \(1\) 开始标号）.

2. 将 \(s_l,s_{l+1},\dots,s_r\) 排序（\(1\le l\le r\le|s|\)）。

上面 \(|s|\) 是 \(s\) 的长度。

判断 \(s\) 是否可以变成 \(t\)，输出 YES 或者 NO。

\(1\le t\le10^4,1\le\Sigma n,\Sigma m\le2\times10^5\)。

题目描述

Sofia has a string $ s $ of length $ n $ , consisting only of lowercase English letters. She can perform operations of the following types with this string.

1. Select an index $ 1 \le i \le |s| $ and remove the character $ s_i $ from the string.
2. Select a pair of indices $ (l, r) $ ( $ 1 \le l \le r \le |s| $ ) and sort the substring $ s_{l} s_{l+1} \ldots s_r $ in alphabetical order.

Here, $ |s| $ denotes the current length of $ s $ . In particular, $ |s| = n $ before the first operation. For example, if $ s = \mathtt{sofia} $ , then performing the operation of the first type with $ i=4 $ results in $ s $ becoming $ \mathtt{sofa} $ , and performing the operation of the second type with $ (l, r) = (2, 4) $ after that results in $ s $ becoming $ \mathtt{safo} $ .Sofia wants to obtain the string $ t $ of length $ m $ after performing zero or more operations on string $ s $ as described above. Please determine whether it is possible or not.

输入格式

The first line contains one integer $ t $ ( $ 1 \leq t \leq 10,000 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ , $ m $ ( $ 1\leq m \leq n \leq 2\cdot 10^5 $ ) — the lengths of string $ s $ and $ t $ , respectively.

The second line of each test case contains the string $ s $ of length $ n $ , consisting only of lowercase English letters.

The third line of each test case contains the string $ t $ of length $ m $ , consisting only of lowercase English letters.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, output "YES" if Sofia can obtain the string $ t $ from $ s $ using the operations above. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

样例 #1

样例输入 #1

8
5 5
sofia
afios
3 2
cba
bc
5 1
sofia
e
15 7
anavolimilovana
aamanan
26 4
abcdefghijklmnopqrstuvwxyz
nope
26 4
zyxwvutsrqponmlkjihgfedcba
nope
7 3
apricot
cat
3 3
cba
acb

样例输出 #1

YES
YES
NO
YES
NO
YES
NO
YES

提示

In the first test case, Sofia can perform the following operation:

1. operation of the second type with $ l=1 $ and $ r=5 $ : string $ s $ becomes $ \mathtt{afios} $ after it.

In the second test case, Sofia can perform the following operations:

1. operation of the second type with $ l=1 $ and $ r=2 $ : string $ s $ becomes $ \mathtt{bca} $ after it;
2. operation of the first type with $ i=3 $ : string $ s $ becomes $ \mathtt{bc} $ after it.

In the third test case, it can be shown that it is impossible to obtain $ t $ from $ s $ using the provided operations.

洛谷
cf

2200的题目，我能看出来解题必要的性质，但是在使用的时候却遇到了无从下手的问题。
其实可能还是有一个性质没有想通，使用没写出来。

首先说说思考过程。

删除操作很明显，就是删除多余的字符。
很明显，我先进行删除操作还是先进行排序是不会影响答案的，而先删除明显思考起来更加方便。

而删除并不能直接对一个字符的位置造成影响，只能间接的通过对字符的取舍达到一个类似交换位置的操作。

能对位置产生影响的是排序。而排序是不可逆的。这个部分其实有一个很不错的思路，就是用冒泡排序的思考方式。

我们不要把排序操作当作指定一个区间的操作，而是当作只能对相邻数字使用的操作。
可以证明，这两个操作是完全可以等价的。证明参考冒泡排序。
那么这个时候，问题被简化了，有一些性质就浮出水面了。
既然我只能通过交换逆序的相邻数字对来实现位置的交换，那些情不可能成功的情况就很好判断了。
假如我s串现在是顺序，而t串现在是逆序，这明显就是无法成功的情况。因为这个字符没办法被排序到比它小的数字后去。
而如果s串是逆序，那么不管怎么样，总能被交换为顺序。

我的思路就卡在了这里。
我不知道怎么利用这个明显是正确的思路的东西来实现。
第一个想法是先找到\(t\)中最大的字符的位置，然后找次大，这样后面的更小的字符能够产生的区间和需要他去的区间就被划定了可行性也可以判断了。
但是没有一个可以被证明正确的贪心，也就是从这个角度这不是一个贪心能解决的问题。
就从第一个点开始，不论我怎么取，总是没法证明这种取法是最优的，或者是这种取法相对于其他取法是不劣的。而不是最优的意思就是有可能导致正确答案被排除。

这个时候我的思路就断了。
从我看完题解后的角度来看，我这里的思路其实是随机走的。
就是我不知道为什么我会这样去考虑，没有在题目里找到一个明确的启发性的情况下，我选择了这种实现思路。

而在这种情况下我需要选择什么思路就是我这个总结需要解决的问题。
让我们再把我们得到的需要用起来的结论列一遍。

1.对于\(t[i]<t[j]\)，\(t[i]\)在\(s\)中的位置的限制是\(s[i-1]\leq s[i]\)，其他没了。
2.对于\(t[i]>t[j]\)，\(t[i]\)在\(s\)中的位置的限制是\(s[i-1]\leq s[i] \leq s[j]\)，比上面多一个限制。

其实这里，应该有一个贪心是我需要发现的。
就是对于任何情况下，当能够选择的区间的一边固定，另一边更大总是更优秀的，反正是不劣的。
想到这个的问题在于"固定一个区间边界"，也就是想到从后往前选。也许很多人看来这个很自然就能想到，我有时候也觉得，但是这次没有。这次我先选择了另一种可能的贪心思路。

其实我这上面的贪心的意思就是，\(s[i]\)的\(i\)越大越好。
那就很恍然大悟了。而我自己想的时候没想到呢。这个就是"固定一个区间边界"这个思路的应用吧，这个思路就能够启发出从后往前的做法。可能是其他的吗？其实看那个需要用的结论就能看出来一点，左边的限制都是相同的，而右边的限制并不同。这说明了什么？
意味着左边更有可能因为同一种情况而变得更优秀，我们可以形象的把这比喻成左边的"利益"，也就是不管左边是什么情况，我是能够采取一些操作让左边的利益变大的。（这边应该说一下，上面这个对\(s[i]\)的限制同时也可以理解为是对\(s[i-1]\)的限制）
也就是如果我从左往右匹配，也就是假设左边都取到了能让目前他们取到答案的答案，那这对于后面的匹配是否有利，需要取决于后面的具体情况。
而如果我从右往左匹配，相当于我总是能够估计这个操作对于之后的选择的影响，这个变成了可量化的东西，而上面的做法找不到。
可量化也就意味着我总是能找到最优的操作。
所以这是贪心。

其实是可以说是，更喜欢固定量，而更不喜欢不确定量。

我理解的时候，把这两种情况都不小心多理解了一些，导致我没有意识到这个限制的特性。

这题，要是能想到从后往前做，那就直接秒了，就是纯纯的2200的难度。
而我上面的所有分析都是建立在我想不到的时候，要怎么样通过题目来找到一定的启发性做出这个题目的情况下。

更多时候，还是提升题感，也就是看到上面的这些东西就去想想从后往前是不是更好做，事实上这个不难想到。因为限制的特性还是很明显的。
我做这些总结的目的其实也是在于加速这种感觉的形成。不需要让我做更多题目才有这种感觉，也让它更加的准确吧。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
	char c=getchar();int a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int n,m;string ss,st;
int s[200001],t[200001],last[200001][27],nxt[200001],tag[27];
bool vis[200001],ans;
int get(int x)
{
	if(vis[x]==0)return x;
	return nxt[x]=get(nxt[x]);
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout); 
	int T=read();
	while(T--)
	{
		for(int i=1;i<=n;i++)vis[i]=0;
		n=read(),m=read();
		cin>>ss>>st;
		for(int i=1;i<=n;i++)
			s[i]=(int)(ss[i-1]-'a'+1);
		for(int i=1;i<=m;i++)
			t[i]=(int)(st[i-1]-'a'+1);
		ans=1;
		if(m>n)
		{
			cout<<"No"<<endl;
			continue;
		}
		for(int i=1;i<=n;i++)
		{
			nxt[i]=last[i-1][s[i]];
			for(int j=1;j<=26;j++)
			{
				last[i][j]=last[i-1][j];
			}
			last[i][s[i]]=i;
		}
		for(int i=1;i<=26;i++)
		{
			tag[i]=n;
		}
		for(int i=m;i>=1;i--)
		{
			int x=last[tag[t[i]]][t[i]];
			x=get(x);
			last[tag[t[i]]][t[i]]=nxt[x];
			if(x==0)
			{
				ans=0;
				break;
			}
			vis[x]=1;
			for(int j=t[i];j<=26;j++)
			{
				tag[j]=min(tag[j],x);
			}
		}
		if(ans==0)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
}
/*
1
5 5
sofia
afios

*/

代码实现又不会了...

怎么回事。
这个把链表当邻接表写的办法确实不错。