本文主要是介绍Codeforces Round 921 (Div. 2) C. Did We Get Everything Covered? (思维题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
思路:
div.2的A题是本题的铺垫, A题的意思是将前k个字母循环出现m次即可, 则将前k个字母看成一个循环节。
本题则是在长为m的字符串中找循环节，注意循环节的意思是前k个字母出现至少一次， 则可知当找到一个循环节的时候，这个循环节的最后一个字母一定是第一次出现且只出现一次。若能找到大于等于n个的循环节，则答案是yes。若小于n个循环节，则最后一个循环节中未出现的字母的若干个加上前面每个循环节的最后一个就是不满足条件的子序列。
代码：
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
const int inf = 0x3f3f3f3f;
const ll infinf = 0x3f3f3f3f3f3f3f3f;//const int N = void solve() {int n, k, m; cin >> n >> k >> m;string s; cin >> s;set<char> st; int cnt = 0; vector<char> ans;for (int i = 0; i < m; i ++) {st.insert(s[i]);if (st.size() == k) {cnt ++; // 找循环节ans.push_back(s[i]); // 将每个循环节的最后一个字母存储st.clear();}}if (cnt >= n) {cout << "YES" << endl; }else {cout << "NO" << endl;vector<int> a(30);for (int i = 1; i <= 26; i ++) a[i] = 0;for (auto itr = st.begin(); itr != st.end(); ++ itr) {a[*itr - 'a' + 1] ++; // 将最后一个不满的循环节中的字母记录}for (int i = 1; i <= k; i ++) {if (a[i] == 0) { // 找缺少了哪个字母for (int j = 0; j < ans.size(); j ++) cout << ans[j]; // 输出之前的每个循环节的最后一个字母for (int j = ans.size() + 1; j <= n; j ++) { // 补上差的字母, 就一定是不满足的子序列cout << char(i + 'a' - 1);}break;}}cout << endl;}}int main() {ios::sync_with_stdio(false);cin.tie(0);int t; cin >> t;while (t --) solve();return 0;
}这篇关于Codeforces Round 921 (Div. 2) C. Did We Get Everything Covered? (思维题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
