专栏文章

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

DDoraeman
P13672题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodppgl
此快照首次捕获于
2025/12/02 17:31
3 个月前
此快照最后确认于
2025/12/02 17:31
3 个月前
查看原文

思路

当某个数包含相同的数字，此时需要多种这样的数字牌子。
例如：如果要表示出 3333333333，那么必须要有至少 55 个数字 33 牌子。
也就是说，对于除了 00 之外的所有的数字 a∈[1,9]a\isin[1,9]，我们要找最大的 0≤aa⋯a‾≤n0\le\overline{aa\cdots a}\le n（共 bb 个 aa）。
此时，需要至少 bb 个 aa 数字牌子来表示这个数 aa⋯a‾\overline{aa\cdots a}，为答案贡献 bb。

具体统计方法

可以首先求出最大的 0<11⋯1‾≤n0<\overline{11\cdots1}\le n，设有 cc 个 11。
接下来，将这个数分别 ×1,×2,…,×9\times1,\times2,\dots,\times9，得到 11⋯1‾, 22⋯2‾,…, 99⋯9‾\overline{11\cdots1},\ \overline{22\cdots2},\dots,\ \overline{99\cdots9}。
注：每个数都包含 cc 个数字。
再分别将这些数从大到小与 nn 比大小，如果小于等于 nn 就结束比较。这样就可以找到最大的 aa⋯a‾\overline{aa\cdots a} 以及其对应的 bb，此处显然满足 b=cb=c。
找到这个 aa 之后，可以发现：
  • 0∼n0\sim n 的倒计时中包含 11⋯1‾∼aa⋯a‾\overline{11\cdots 1}\sim\overline{aa\cdots a}（cc 个数字），所以它们一共需要 a×ca\times c 个数字牌。
  • 0∼n0\sim n 的倒计时中也包含 (a+1)(a+1)⋯(a+1)‾∼99⋯9‾\overline{(a+1)(a+1)\cdots(a+1)}\sim\overline{99\cdots9}（c−1c-1 个数字），所以它们一共需要 (9−a)×(c−1)(9-a)\times(c-1) 个数字牌。
  • 这个倒计时中还包含 100⋯0‾\overline{100\cdots0}（c−1c-1 个 00），所以还额外需要 (c−1)(c-1) 个数字牌。
最后求出答案：a×c+(9−a)×(c−1)+(c−1)=ac+(10−a)ca\times c+(9-a)\times(c-1)+(c-1)=ac+(10-a)c。

特判

如果 nn 是一位数，即 b=c=1b=c=1，我们的统计方法没有统计 00，应该加上。
为了避免麻烦，可以直接算出来：当 nn 是一位数时，需要 (n+1)(n+1) 个数字牌。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...