cf1560 F2. Nearest Beautiful Number | hard version

题意：

一个整数被称为 k-beautiful 的，当且仅当不同的数位数量 \(\le k\)

输入 \(n,k\)，求大于等于 \(n\) 的最小的 k-beautiful 数

\(T\le 1e4, 1\le n \le 1e9, 1\le k \le10\)

思路：

法一（要脑子）：

找一段最短的、不同数位数恰为 k+1 的前缀 \(n[1\sim p]\)

显然这段前缀 \(n[1\sim p]\) 不合要求，需要改变。我们将这段前缀视为一个 p 位整数，把它加一；然后把 \(n[p+1\sim end]\) 置 0。

一直循环上面两步即可。

上面的做法其实分为两步：首先把前缀一直加一，直到前缀中不同数位数 \(\le k\)。然后把后面的 0 全部加成前缀中的最小数位

例子：n = 789152352 k = 3

789200000 → 789300000 → 789700000

然后把后面的0都变成7 → 789777777

复杂度 \(O(Tm^2)\)，m 为位数

string n; int k;bool ok() {    set<char> S; for(char c : n) S.insert(c);    return S.size() <= k;}void sol() {    cin >> n >> k;    while(!ok()) {        set<char> S;        for(int i = 0; ; i++) {            S.insert(n[i]);            if(S.size() > k) {                while(n[i] == '9') i--;                n[i]++;                for(int j = i + 1; j < n.size(); j++)                    n[j] = '0';                break;            }        }    }    cout << n << endl;}

法二：数位dp，不用脑子

（待补）