题解：P13672 [GCPC 2023] German Conference for Public Counting

· · 题解

思路

当某个数包含相同的数字，此时需要多种这样的数字牌子。
例如：如果要表示出 33333，那么必须要有至少 5 个数字 3 牌子。

也就是说，对于除了 0 之外的所有的数字 a\isin[1,9]，我们要找最大的 0\le\overline{aa\cdots a}\le n（共 b 个 a）。
此时，需要至少 b 个 a 数字牌子来表示这个数 \overline{aa\cdots a}，为答案贡献 b。

具体统计方法

可以首先求出最大的 0<\overline{11\cdots1}\le n，设有 c 个 1。

接下来，将这个数分别 \times1,\times2,\dots,\times9，得到 \overline{11\cdots1},\ \overline{22\cdots2},\dots,\ \overline{99\cdots9}。
注：每个数都包含 c 个数字。

再分别将这些数从大到小与 n 比大小，如果小于等于 n 就结束比较。这样就可以找到最大的 \overline{aa\cdots a} 以及其对应的 b，此处显然满足 b=c。

找到这个 a 之后，可以发现：

最后求出答案：a\times c+(9-a)\times(c-1)+(c-1)=ac+(10-a)c。

特判

如果 n 是一位数，即 b=c=1，我们的统计方法没有统计 0，应该加上。

为了避免麻烦，可以直接算出来：当 n 是一位数时，需要 (n+1) 个数字牌。

代码

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

// 求 b 
int digit(int x){
    int sum = 0;
    while(x) x/=10, sum++;
    return sum;
}

int main(){
    int x; cin >> x;
    int d = digit(x);

    // 特殊处理 
    if(d == 1){
        cout << x + 1;
        return 0;
    }

    // 求最大的 11...1≤n
    int base = 0;
    for(int i=1; i<=d; i++)
        base *= 10, base++;

    // 直接相除得到对应的 a
    int t = x / base;
    // 答案 // b=c
    int ans = t*d + (10-t)*(d-1);
    cout << ans;
}