問題概述

原題參考：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<int>
#define vl vector<long long>
#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;
}

問題反思

這個題感覺我的理解還算是清楚的，所以寫出來記錄一手