• 周日. 6月 26th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

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

admin

11月 28, 2021

差点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;
}

发表评论

您的电子邮箱地址不会被公开。