题意:
一个整数被称为 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,不用脑子
(待补)