C++(g++ 7.5.0) 解法, 执行用时: 390ms, 内存消耗: 8700K, 提交时间: 2023-06-04 12:54:15

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int T,n,mxb;
int f[2097152],g[460][26];
string s;

int main() {
    for (scanf("%d",&T);T;T--) {
        scanf("%d",&n);
        cin>>s;
        mxb=1<<n;
        int len=s.length();
        if (n>21) {
            printf("NO\n");
            continue;
        }
        for (int i=0;i<n;i++) g[len][i]=g[len+1][i]=len+1;
        for (int i=len;i;i--) {
            for (int j=0;j<n;j++) g[i-1][j]=g[i][j];
            g[i-1][s[i-1]-'a']=i;
        }
        memset(f,0,sizeof f);
        for (int i=1;i<mxb;i++)
            for (int j=0;j<n;j++)
                if (i&(1<<j)) f[i]=max(f[i],g[f[i^(1<<j)]][j]);
        if (f[mxb-1]<=len) printf("YES\n");
        else printf("NO\n");
    } 
}

C++(clang++ 11.0.1) 解法, 执行用时: 576ms, 内存消耗: 16908K, 提交时间: 2023-04-25 15:45:17

#include<bits/stdc++.h>
#define MAXN 505
using namespace std;	int t,n,m;char s[MAXN];
int f[MAXN][30];
int g[1<<22];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%s",&n,s+1);	m=strlen(s+1);
		if(n>21){
			puts("NO");
			continue;
		}
		memset(f,-1,sizeof f);
		for(int i=1;i<=m;++i){
			for(int j=0;j<n;++j)
                f[i][j]=f[i-1][j];
			f[i][s[i]-'a']=i;
		}
		for(int i=0;i<(1<<22);++i)	g[i]=m;
		for(int s=1;s<(1<<n);++s)
			for(int i=0;i<n;++i){
				if(g[s^(1<<i)]==-1){
					g[s]=-1;
					continue;
				}
				if(s&(1<<i))	g[s]=min(g[s],f[g[s^(1<<i)]][i]);
			}
		puts(g[(1<<n)-1]<0?"NO":"YES");
	}
	return 0;
}