本文主要是介绍Did We Get Everything Covered? Codeforces Round 921 (Div. 2) 1925C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - C - Codeforces
题目大意：给出一个长度为m的字符串s，问所有长度为n且由字母表中前k个字母组成的字符串是否都是s的子序列，如果不是须给出反例
1<=n<=26;1<=k<=26;1<=m<=1000;所有样例的m之和不超过1e6
思路：先回顾一下A题是怎么做的，也就是构造一个最短的字符串S使所有长度为n且由字母表中前k个字母组成的字符串都是S的子序列。
当n等于1时，显然我们要让k个字母各自出现一次，顺序任意，我们称这个长度为k的字符串为一个合法段。当n等于2时，k个字母各出现一次后，所有字母还要再出现一次，所以最短的合法字符串就是前后各一个合法段拼在一起，每个合法段内部的字母顺序不影响。同理，n等于几就要有几个合法段。
那么我们可以尝试在s中找合法段，每当k个字母都至少出现一次就是一个合法段，如果找到了n个合法段，就是YES，否则就是NO，然后考虑怎么找反例
因为每个合法段中可能夹杂着其他的字母，比如k=3时aabbcc是一个合法段，那么要排除多余字母的影响，就应该选取这个合法段中最后一个字母加入到反例中。s遍历完了之后再将最后一个合法段中没出现的一个字母加入反例中，这样的反例在s中一定没出现过。如果不够n的话再随便找k以内的字母凑即可
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll n;
bool vis[N];
void init()
{for (int i = 1; i <= 26; i++){//注意初始化vis[i] = 0;}
}
void solve()
{cin >> n;init(); int k;cin >> k;int m;cin >> m;string s;cin >> s;int j = 0;char las;string ans;bool flag = 1;for (int i = 1; i <= n; i++){//找到n个合法段int cnt = 0;for (;j < m; j++){//遍历sif (!vis[s[j]-'a'+1]){//找到第一次出现的字母vis[s[j]-'a'+1] = 1;cnt++;if (cnt == k){//找到了一个合法段las = s[j];ans += las;//将最后一个字母放入for (int ii = 1; ii <= k; ii++){vis[ii] = 0;}j++;break;}}}if(cnt != k){//找不到合法段了 flag = 0;for (int ii = 1; ii <= k; ii++){if (!vis[ii]){//找到一个没出现的字母，加入反例中ans+= char('a' + ii - 1);break;}} }}if (!flag){cout << "NO\n";for (int i = 0; i < ans.length(); i++){cout << ans[i];}cout << '\n';return;}cout << "YES";cout << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t; cin >> t;while (t--){solve();}return 0;
}这篇关于Did We Get Everything Covered? Codeforces Round 921 (Div. 2) 1925C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
