• 欢迎光临~

cf1567 D. Expression Evaluation Error

开发技术 开发技术 2022-06-16 次浏览

题意:

构造一个长为 (n) 的十进制数组,要求数组的十进制和为 (s) 且数组的十一进制和最大

注意不需要转成十一进制再做加法,仅仅是把十进制数 “误解” 为十一进制

(1le sle 1e9, 1le n le min (100,s))

思路:

如果不用拆分,直接把 (s) 转成十一进制就是最大的;如果要拆分,每有一次(十进制下的)进位就会造成损失

比如 (20_{10}=10_{10}+10_{10}=11_{10}+9_{10}),而 (10_{11}+10_{11}=20_{11},11_{11}+9_{11}=1A_{11}),损失了 1

事实上,每在第 (k) 位((kge 0))向左边产生一次(十进制)进位,答案就损失 (11^k)。这是因为在十进制下能够正常进位得到原值,但在十一进制下每次进位减去的是 11 而不是 10,多减了 1

我们希望拆出尽量多的数,同时不损失。所有拆一个尽量小的数即 10 的幂。比如 (25=10+10+1+1+1+1+1)。如果不需要这么多数比如 (n=4),就写成 (25=10+10+1+4),最后的 4 就不继续拆了

上述过程得到的数全是 10 的幂,若不足 n 个,说明还要拆。为了减小损失尽量拆小的数。1 是不能拆的,有 10 的话就拆 10,没有的话拆 100,以此类推。拆数的原则也是尽量拆细一点,同时产生的进位次数尽量少。比如对于 100,先拆一个 10 出来变成 (10=10+90),再把 90 拆成 (90=10+80) 等等,这样只在拆 100 的时候产生一次进位。注意不要拆成 (100=1+99),因为这样会产生两次进位。

正确拆法举例:(210=100+100+1+9)

综上,按如下规则拆数:

  • 若只差一个数,直接输出当前(被拆剩)的 (s)

  • 设还差 (n) 个数,考虑从 (s) 中拆一个不大于 (s) 的最大的 10 的幂(记为 (t)),若 (s-tge n-1) 说明拆掉 (t) 之后还能拆出足够的数,当前可以拆 (t)

  • 若现在不能拆 (t),说明当前不能拆这么大的数,考虑拆较小的10的幂:(t/10)

void sol() {
    int s, n; cin >> s >> n;
    int k = 1; while(k * 10ll <= s) k *= 10; //不大于s的最大的10的幂
    while(n) { //还需要n个数
        if(s - k >= n - 1) {
            cout << (n == 1 ? s : k) << ' ';
            s -= k, n--; //拆出k
        }
        else k /= 10; //k太大
    }
}
程序员灯塔
转载请注明原文链接:cf1567 D. Expression Evaluation Error
喜欢 (0)