JZOJ 3293. 【SHTSC2013】阶乘字符串

( ext{Problem})

给定一个由前 (n) 个小写字母组成的串 (S)。
串 (S) 是阶乘字符串当且仅当前 (n) 个小写字母的全排列（共 (n!) 种）都作为 (S) 的子序列（可以不连续）出现。
判断 (S) 是否是阶乘字符串
多组数据

( ext{Analysis})

一个结论：
当 (n > 21) 时
(ecause |S| <= 450)
( herefore C_{n}^{450} < n!)
( herefore) 结果为 (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])

( ext{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
"); continue;}
		if (solve()) printf("YES
");
		else printf("NO
");
	}
}