ZRound#1

题目

• [x] A - Nearest Beautiful Number (easy version) 【1900】
• [ ] B - Nearest Beautiful Number (hard version) 【2100】
• [x] C - Expression Evaluation Error 【2000】
• [ ] D - Rescue Niwen! 【2500】

还想冲一冲 2500 分的题， 有点做梦了， 2100 分的题都没有 a 出来， 最近的训练还是要1900 - 2200 为主

做 C 的时候心态崩了， 写的越来越乱， 其实 C 不难， 只要稳住心态好好想一想实现就可以比较快的 A 掉

A. Nearest Beautiful Number（easy version）

Tag: 1900 暴力

题意：

给一个整数 (n) , 求大于等于 (n) 的第一个 (k-beautiful) 数， 指数字中数位总数小于等于 (k)

如 122221，11111，770 都是 2-beautiful 数

Easy-version : (1 le k le 2)

Hard-version: (1le k le 10)

对于 easy-version ，直接暴力求出所有数， 然后 lower_bound 即可

B. Nearest Beautiful Number (hard version)

补题

大致有两种解法， 一种是贪心的解法， 只能说是妙哇， 找到 k + 1 个不同数字的前缀， 然后 ++， 不停这样操作即可

#include<bits/stdc++.h>
using namespace std;

int count(int v){
    int res = 0;
    while(v){
        res |= (1 << (v % 10));
        v /= 10;
    }
    return __builtin_popcount(res);
}
int T, n, k;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> T;
    while(T--){
        cin >> n >> k;
        while(count(n) > k){
            int f = n, t = 1;
            while(count(f / 10) > k){
                f /= 10;
                t *= 10;
            }
            f++; n = f * t;
        }
        cout << n << '
';
    }
    
}

还有一种是数位 dp + 二分的做法， 先 m 住， 后边刷 dp 后再来补

C. Expression Evaluation Error

Tag： 2000 贪心

题意：

给 (s) 和 (n) ， 有长度为 (n) 的数组 (A) ， 满足 (sum_{i=1}^n A_i = s) , 现在用 11-base 进制来解释 (A)​ ，要使得其在 11-base 的意义下和最大， 给出任意符合要求的构造， (1 le A_i)

思路：

对于向上的进制转换，贪最高位即可。

D. Rescue Niwen