• • 问题概述
  • 思路想法
  • 参考代码
• include <bits/stdc++.h>
• define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
• define endl '\n'
• define pll pair<long long, long long>
• define pii pair<int, int>
• define vi vector
• define vl vector
• define ll long long
• define ull unsigned long long
• ifdef xrl
• endif
• ifdef xrl
• endif
  • 问题反思

问题概述

原题参考：C.Did We Get Everything Covered?
给出n、k、m和一个字符串，要求判断字符串是否可以包含前k个字母的长度为n的全排列，如果可以，输出yes，如果不行，输出no并给出反例

Input:
3
2 2 4
abba
2 2 3
abb
3 3 10
aabbccabab

Output:
YES
NO
aa
NO
cc

看到这个输出，不得不想夸cf一句，不拘小节，yes、YES、Yes之类的全都算对，其余oj平台就emmm，看缘分了

思路想法

其实这个题是有一个简单版本的，要求给出满足n、k的最短字符串构造，由改题可知，最短字符串是n*k的，就是将前k个字符重复n遍，这个m显然是没有用的；由上面的一题可以得知，要想满足题意中的字符串要求，就需要有n个完整包含前k个字符的区间，也就是说，这样我们就可以从每个区间内选择字符去构造任意排列。但是该题的难点在于如何输出一个反例，我之后看了一些题解，也感觉有点模糊不清，琢磨了一阵子，大致可以这样理解
由第一题的提示我们可以大致将字符串分为n个区间，最极限的情况就是字符串的构建需要n个区间的字符，也就是无可替代的，但是对于反例我们是否直接输出n*i即可，显然是不行的，因为其他区间可以帮助他，也就是说，其他区间还有余力帮助不属于该区间的任务，对于字符串aabbccabab就可以将其分为aabbc\cab\ab，假如我们要ccc，其实可以在第二个区间加上c变成aabbc\ccab\ab，这样基本上是一样的(不知道大家能不能get到我的点)，那什么时候每个区间不能帮助其他区间呢，就是取末尾字符的时候，这时候假如再加，那么可能造成区间的移动，从而变得不是自己，

参考代码

include <bits/stdc++.h>

using namespace std;

define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

define endl '\n'

define pll pair<long long, long long>

define pii pair<int, int>

define vi vector

define vl vector

define ll long long

define ull unsigned long long

const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
int n, k, m, ktmp, nCnt = 0;
bool sFind[27];
string s, ans = "";
void solve() {
memset(sFind, 0, sizeof sFind);
ktmp = 0, ans = "", nCnt = 0;
cin >> n >> k >> m >> s;
for(auto x:s) {
if(!sFind[x-'a'+1]) {
ktmp ++;
sFind[x-'a'+1] = 1;
}
if(ktmp == k) {
nCnt ++;
ktmp = 0;
ans += x;
memset(sFind, 0, sizeof sFind);
}
}
if(nCnt >= n) cout << "YES" << endl;
else {
cout << "NO" << endl;
for(int i=1; i<=k; i++) {
if(!sFind[i]) {
ans += string(1, i+'a'-1);
break;
}
}
int i = ans.size();
for(; i<n; i++) ans += "a";
cout << ans << endl;
}
}
int main() {

ifdef xrl

freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);

endif

FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();

ifdef xrl

cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";

endif

return 0;

}

问题反思

这个题感觉我的理解还算是清楚的，所以写出来记录一手