1. A. Did We Get Everything Covered?(构造、思维)

本文主要是介绍1. A. Did We Get Everything Covered?(构造、思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. A. Did We Get Everything Covered?(构造、思维)

题目链接

---

A. Did We Get Everything Covered?

---

题意

---

给$n，k$以及长度为$m$的一个小写的字符串。
字符串的子序列是否包含用前$k$个小写字母构成的长度为n的字符串的所有情况

---

题解

1. 首先判断有没有解：
   要构成所有的字符串，我们可以把原串进行拆分，拆分成n个段，每段如果都包含前k个小写字母至少一次，则说明有解，反之说明无解。
2. 无解的情况下，考虑如何构造答案。
   用每一段最后一次出现的字符，加上不满足的段中没有出现的字符
   正确性？每一段最后出现的字符一定在前面没出现过，只能在后面出现，这样构造出来的子序列是正确的

代码

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;
const int mod=998244353;
void solve() {int n,k,m;string s;cin>>n>>k>>m;cin>>s;set<char>cnt;int cur=0;string ans;rep(i,0,m-1) {cnt.insert(s[i]);if(cnt.size()==k) {ans+=s[i];++cur;cnt.clear();}if(cur>=n) {cout<<"YES"<<endl;return;}}cout<<"NO"<<endl;int len=ans.size();rep(i,0,k-1) {char c='a'+i;if(cnt.count(c)==0) {rep(j,1,n-len)	ans+=c;break;}}cout<<ans<<endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

总结

有判定正确性的思路，但是不会构造
wa了几发。最开始是构造的思路是错的
后面有一个小细节处理的不好，当要修改$string$时，就不能用$string$的$size$作为循环的控制条件，这样很容易寄。
很好的一道构造题目

---

这篇关于1. A. Did We Get Everything Covered?(构造、思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---