Codeforces 1513D - GCD and MST(設計解題)

解法

使用 greedy 的方式最快判斷出 yes or no, 如果是 no 則是缺少哪個單字。

由於這題是排列組合子字串，n 個字母只能夠出現 k 個不同英文字母，因此，只需要判斷需要多少長度的字元，才可以包括 k 個不同字母，反覆 n 次測試，如成功則 yes、反之則 no。

如果是 no，則發現 no 之後的字母輸出沒有包括地英文字母就好，前面任意。

程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 0x3f3f3f
#define int long long int
using namespace std;
int t, n, k, m;
string str;
vector<int> pos[30];

void process(){
    for(int i = 0; i < 30; i++){
        pos[i].clear();
    }
    for(int i = 0; i < m; i++){
        int char_pos = (int)(str[i]-'a');
        pos[char_pos].push_back(i);
    }
    for(int i = 0; i < 30; i++){
        pos[i].push_back(m+10); //表示已經跑到字串最後一個
    }

    string ans = "";
    //high_pos: 在這次中特定字母出現的最遠位數
    //pre_high: 上次中特定字母出現最遠次數
    int high_pos = -1, high, pre_high = -1;
    char high_char;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            //從上次最遠次數，尋找後面下一個更遠位數。
            high = *upper_bound(pos[j].begin(), pos[j].end(), pre_high);
            //cout << "j high high_pos " << j << " " << high_pos << "\n";
            if(high >= high_pos){
                high_char = (char) ('a' + j);
                high_pos = high;
            }
        }
        pre_high = high_pos;

        if(high_pos == m+10){ //是否已超出字串長度
            cout << "NO\n";
            for(;i < n; i++) ans += high_char;
            cout << ans << "\n";
            return;
        }
        ans += str[high_pos];

    }
    cout << "YES" << "\n";
    return;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k >> m;
        cin >> str;
        process();
    }

    return 0;
}