\(\text{Problem}\)

给定一个由前 \(n\) 个小写字母组成的串 \(S\)。

串 \(S\) 是阶乘字符串当且仅当前 \(n\) 个小写字母的全排列（共 \(n!\) 种）都作为 \(S\) 的子序列（可以不连续）出现。

判断 \(S\) 是否是阶乘字符串

多组数据

\(\text{Analysis}\)

一个结论：

当 \(n > 21\) 时

\(\because |S| <= 450\)

\(\therefore C_{n}^{450} < n!\)

\(\therefore\) 结果为 \(NO\)

于是我们只需考虑 \(n \le 21\) 的情况

此时状压可行

设 \(f_s\) 表示字符串 \(S\) 中的一个位置，使得集合 \(s\) 中的字母的全排列都在 \([1,f_s]\) 中出现过

那么我们只需要看 \(f_{2^n-1}\) 是否合法

设 \(nxt_{i,j}\) 表示串 \(S\) 中位置 \(i\) 以后（不包括 \(i\)） \(j\) 出现的位置

则 \(f_s = \max_{i \in s} nxt[f_{s - 2 ^ i}][i]\)

\(\text{Code}\)

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int MAXN = 21;

int T, n, len, nxt[455][26], f[1 << MAXN];

char s[455];

inline int solve()

{

	memset(nxt, 0x3f3f3f3f, sizeof nxt), memset(f, 0, sizeof f);

	len = strlen(s + 1);

	for(int j = 0; j <= len + 1; j++)

		for(int k = 0; k < 26; k++) nxt[j][k] = len + 1;

	for(int j = len; j >= 0; j--)

	{

		for(int k = 0; k < 26; k++) nxt[j][k] = nxt[j + 1][k];

		nxt[j][s[j + 1] - 'a'] = j + 1;

	}

	for(int i = 1; i < (1 << n); i++)

	{

		for(int j = 0; j < n; j++)

		if (i & (1 << j)) f[i] = max(f[i], nxt[f[i - (1 << j)]][j]);

	}

	return f[(1 << n) - 1] != len + 1;

}

int main()

{

	scanf("%d", &T);

	for(int i = 1; i <= T; i++)

	{

		scanf("%d%s", &n, s + 1);

		if (n > 21){printf("NO\n"); continue;}

		if (solve()) printf("YES\n");

		else printf("NO\n");

	}

}

巴特西

JZOJ 3293. 【SHTSC2013】阶乘字符串

\(\text{Problem}\)

\(\text{Analysis}\)

最新文章

热门文章