CF1925 AC

link & link

EV

直接输出 \(n\) 遍前 \(k\) 个小写字母即可。

证明

考虑对于一个题目要求的串 \(s\)，能不能满足要求。

显然 \(s_1\) 可以在第一遍小写字母中找到。

DV

考虑题目给出的什么时候一定合法。

显然，如果和我们 EV 构造的串原理一致，那就一定合法。

我们注意到 \(n=2,k=3,aabccab\) 也是合法的。这就提示我们当从题目给出的串中去掉一些字母后得到的串与 EV 原理相同，也是合法的。

读者可以自证。

我们发现无法找到其它合法的串了，于是判断除了上面的情况，其它串都是不合法的。

构造

我们现在有一个不能找到 \(n\) 遍前 \(k\) 个小写字母的串。设这个串只能找到 \(m\) 遍小写字母（\(m<n\)）。

我们一定可以构造出一个串 \(s\) ，使得其无法作为题目串的一个子序列。

设题目串中每遍前 \(k\) 个小写字母中的最后一个为 \(l_i\)。

我们令 \(s_i=l_i(i\le m)\)。

设字母 \(c\) 在第 \(m+1\) 遍无法找到，容易发现 \(c\) 是一定存在的。

令 \(s_{m+1}\sim s_n=c\)，可以发现 \(s\) 一定无法作为一个子序列出现。

稍加思考可以发现，这个结论是正确的。非要用语言表述出来反而会很乱。

于是我们就可以按照这种构造方式通过此题。

#include<bits/stdc++.h>

typedef long long LL;
typedef std::pair<int,int> pii;

#define ok putstrln("OrzFinderHT")
//#define check_time printf("%.8f\n",clocks()/CLOCK_PER_SEC)

template<typename T>
void abs(T &N){
	if(N>=0) N=N;
	else N=-N;
}

namespace G_{
	template<typename T>
	inline void read(T &a){
		a=0;
		int f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-') f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9') a=(a>>1)+(a>>3)+(c&15),c=getchar();
		a*=f;
	}
	inline void get_enter(){
		getchar();
	}
	inline void get_str(std::string &str){
		char c=getchar();
		while(c!=' '&&c!='\n') str+=c,c=getchar();
	}
	template<typename T>
	inline void putN(T N){
		char stk[70];
		short top=0;
		if(N<0) putchar('-'),abs(N);
		do{
			stk[++top]=N%10+48;
			N/=10;
		}while(N);
		while(top) putchar(stk[top--]);
	}
	template<typename T>
	inline void putsp(T N){
		putN(N);
		putchar(' ');
	}
	template<typename T>
	inline void putln(T N){
		putN(N);
		putchar('\n');
	}
	inline void putstr(std::string str){
		int sz=str.size()-1;
		for(int i=0;i<=sz;i++) putchar(str[i]);
	}
	inline void putstrln(std::string str){
		putstr(str);
		putchar('\n');
	}
	inline void Yes(){
		putstrln("Yes");
	}
	inline void No(){
		putstrln("No");
	}
}

//using namespace get_give;

using namespace G_;

int vis[30];

int c_i(char c){
	return c-'a'+1;
}

signed main(){
	int T;
	std::cin>>T;
	while(T--){
		int n,k,m;
		std::cin>>n>>k>>m;
		std::string s;
		std::cin>>s;
//		get_enter();
		memset(vis,0,sizeof(vis));
		int cnt=0,sum=0;
		std::string las;
		for(int i=0;i<s.size();i++){
			if(c_i(s[i])>k) continue;
			if(vis[c_i(s[i])]==sum) cnt++,vis[c_i(s[i])]++;
			if(cnt==k) cnt=0,sum++,las+=s[i];
		}
		if(sum>=n){
			std::cout<<"YES\n";
			continue;
		}
		std::cout<<"NO\n";
		if(las.size()!=0) std::cout<<las;
		int ne=n-las.size();
		for(int i=1;i<=k;i++){
			if(vis[i]==sum) {
				char c=(char)('a'+(i-1));
				for(int j=1;j<=ne;j++) putchar(c);
				break; 
			}
		}
		putchar('\n');
	}
	return 0;
}
/*
-读入字符一定检查回车
- 能不能搜索？
-函数要有返回值！
-想好了再写！
*/