F2. Nearest Beautiful Number (hard version) （思维+分类讨论+枚举）

差点AKdiv3www

 首先这道题肯定不能暴力了啦。之后我们发现这道题其实跟数位dp非常的相像。那么数位dp的时候，一旦某一位变大了，那么后面的数字其实是随便选的，因为不管怎么选，这个数字肯定是大于之前的数的。

比如122245与123***肯定不管怎么取*的数字肯定是比122245大的。

之后这道题又要取最小，我们可以想到从最后开始枚举，因为修改的数位越小，那么肯定是越小的。

所以就能想到暴力枚举每一位，如果出现了合法的答案就肯定是这个了。

那么如果是两个for进行枚举（枚举当前修改的数字，以及后面的所有要变成的数字）是会T的，T了3发。

所以我们考虑优化这个过程。

如果当前数位改变了，如果算上当前这位数，不同的数字是< k的，那么我们就将后面的所有数字变成0。

如果 == k 那么我们就需要从前面的k个数里选最小的数进行填充。

之后判断是否合法就好了。

用string和set写的常数好像有点大。

#include <bits/stdc++.h>
using namespace std;
string n;
int k;

int cal(string ss) {
    set<char> s;
    for (auto c : ss) s.insert(c);
    return s.size();
}

string solve() {
    cin >> n >> k;
    if (cal(n) <= k) return n;
    int len = n.size();
    for (int i = len-1; i >= 0; i --) {
        string temp = n;
        ///如果当前位提高了1，那么后面的数只有取0或者取之前最小的情况
        for (char j = n[i]+1; j <= '9'; ++ j) {
            set<char> ck;
            for (int l = 0; l < i; ++ l) ck.insert(n[l]);
            temp[i] = j;
            ck.insert(j);
            if (cal(temp.substr(0, i)) > k) continue;

            char p = cal(temp.substr(0, i+1)) < k ? '0' : *ck.begin();
            for (int l = i+1; l < len; ++ l) temp[l] = p;
            if (stoi(temp) >= stoi(n))
                return temp;
        }

    }
    return "";
}

int main() {
    int t; cin >> t;
    while (t--)
        cout << solve() << '
';
    return 0;
}