自动搬运

查看原文

来自洛谷，原作者为

	ZnPdCo 「是不是糖的都无所谓了」

搬运于2025-08-24 21:55:17，当前版本为作者最后更新于2023-10-02 22:05:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

给定一个字符串，看其是不是 $n$ 个小写字母全排列组成的子序列（注意不是子串）

更新记录

upd:2023-10-02 22:05:50 第一版，提出反例 abcdabcadbac

upd:2023-10-04 21:34:47 第二版，发现更优的构造方法（By @Ac_forever）

首先，我们可以很容易发现，$n>21$ 时完全构造不出合法的方案，所以答案一定为 NO。

证明：然鹅，网上说 $\dbinom{450}{21}<21!$ 是不正确的， 因为我自己算了一遍发现不对。

然后就是所谓的 $n^2-n+1$ 或 $n(n-1)+1$，是错误的、更优的构造方法为：

设 'a'+n-1 为 x，则重复 $n-3$ 遍从 a 到 x，然后再为 a 到 x-1，再为 a 和 x，再为 a+1 到 x-1，最后为 a。

举个例子可能会更好（$n=5$）：

$$\underbrace{abcde\ abcde}_{n-3\text{遍}}\ \underbrace{abcd}_{\text{去尾}}\ \underbrace{a\ e}_{\text{头、尾}}\ \underbrace{bcd}_{\text{去头去尾}}\ \underbrace{a}_{\text{固定了}} $$

但是我不会证明

但是又有前车之鉴，所以说，只能是最小字符串长度的上限是 $n^2-n$。

那么我们假定就是这个就是最小字符串的大致范围，那么发现当 $n=22$ 时 $n^2-n=462>450$，所以当 $n>21$ 时完全构造不出合法的方案。

---

发现可以状压。

用 $f_s$ 表示进行状态转移，$s$ 表示我们组成的前排列中字母的存在情况。例如 $s=(101)_2$ 表示有字母 a 和 c。

$f_s$ 表示满足条件的最小的字符串前缀长度，还是 $s=(101)_2$，若 $S=acaa$，容易发现 $f_s=3$，因为前 $3$ 的前缀为 aca，有 ac 与 ca，满足题意。

定义函数 $\text{nxt}(i,j)$ 表示第 $i$ 位后面的第一个字符 $j$ 的位置（不含自己）

然后枚举新加入的字符 c，易得：

$$f_{s|c}=\max(f_{s|c},\text{nxt}(f_s,c))\qquad c\not\in s $$

为什么是 $\max$？因为有两种情况：

1. $f_{s|c} > \text{nxt}(f_s,c)$，那么这时候 $f_{s|c}$ 是包含的 $c$ 的，满足条件
2. $f_{s|c} < \text{nxt}(f_s,c)$，那么这时候 $f_{s|c}$ 是不包含的 $c$ 的，要把 $c$ 包括进去

最后判断 $f_{(\underbrace{111\cdots111}_{\text{(n-1)个1}})_2}$，也就是 $f_{(1<<n)-1}$ 是不是合法的即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define INF (ll)(1e17)
using namespace std;
ll t;
ll n;
char S[500];
ll nxt[500][26];
ll f[(1<<21)+10];
int main() {
	scanf("%lld", &t);
	while(t--) {
		scanf("%lld", &n);
		scanf("%s", S + 1);
		ll m = strlen(S + 1);
		
		
		if(n > 21) {
			printf("NO\n");
			continue;
		}
		
		
		
		for(ll c = 0; c < n; c++) nxt[m][c] = INF;
		for(ll s = 0; s < (1 << n); s++) {
			f[s] = 0;
		}
		
		
		
		for(ll i = m; i >= 1; i--) {
			for(ll c = 0; c < n; c++) {
				nxt[i - 1][c] = nxt[i][c];
			}
			nxt[i - 1][(ll)(S[i]) - 'a'] = i;
		}
		
		
		
		
		for(ll s = 0; s < (1 << n); s++) {
			for(ll c = 0; c < n; c++) {
				if((s | (1 << c)) != s) {
					if(f[s] == INF) f[s | (1 << c)] = INF;
					else f[s | (1 << c)] = max(f[s | (1 << c)], nxt[f[s]][c]);
				}
			}
		}
		
		
		if(f[(1 << n) - 1] == INF) printf("NO\n");
		else printf("YES\n");
	} // ( •̀ ω •́ )\
}