【BZOJ 4416】[SHOI2013] 阶乘字符串

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4416
神犇题解Ⅰ：http://blog.csdn.net/flaze_/article/details/52607165
神犇题解Ⅱ：http://309459245.lofter.com/post/1dd7269e_a37f28d

解题报告

第一次做这么神奇的判定性题目
感觉非常神奇啊！神清气爽！

闲来无事写了一份beamer，大家随便看看吧
另外，这货的证明是错的：http://blog.csdn.net/horizon_smz/article/details/50905084
slide

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = (1<<21) + 9;
const int M = 500;
const int SGZ = 21;

int n,m,f[N],last[SGZ],nxt[M][21];
char pat[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read();T;T--) {
		m = read();
		scanf("%s",pat+1);
		n = strlen(pat+1);
		if (m > 21) {
			puts("NO");
			continue;
		}
		for (int i=0;i<m;i++) 
			last[i] = nxt[n+1][i] = n + 1;
		for (int i=n;~i;i--) {
			for (int j=0;j<m;j++) 
				nxt[i][j] = last[j];
			if (i) last[pat[i]-'a'] = i;
		}
		for (int i=1,lim=1<<m;i<lim;i++) {
			f[i] = 0;
			for (int j=0;j<m;j++) {
				if (i & (1 << j)) {
					f[i] = max(f[i], nxt[f[i^(1<<j)]][j]);
				}
			}	
		}
		if (f[(1<<m)-1] <= n) puts("YES");
		else puts("NO");
	}
	return 0;
}