差点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() << ‘\n‘; return 0; }