[ZJOI2010]COUNT 数字计数

[编程题][ZJOI2010]COUNT 数字计数

热度指数：1926 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

输入描述:

输入文件中仅包含一行两个整数a、b，含义如上所述。

输出描述:

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

示例1

输入

1 99

输出

9 20 20 20 20 20 20 20 20 20

备注:

对于30%的数据，保证；
对于100%的数据，保证 。

算法知识视频讲解

C++

腾云糕

问题转化为求1~n中每个数字出现的次数

参考leetcode剑指offer同类题“统计1~n中1出现的次数题目”中k神的思路：

统计每一位上1出现的次数并加和。将n分为high|cur|low，cur为当前数位值，digit为对应位数的整数中最高位为cur的个数，即low的位数的10次幂。

cur==0时，cur位上出现1的数有1|*, 1|1|*, 2|1|*,...,high-1|1|*，共high*digit个；

cur==1时，cur位上出现1的数有cur==0时的个数再加上high|1|0,high|1|1,...,high|1|low这low+1个；

cu>1时，cur位上出现1的数有1|*,1|1|*,2|1|l*,...,high|1|*，共(high+1)*digit个；

初始为个位，low=0，cur=n%10，high=n/10，digit=1；

随后low+=cur*digit，cur=high%10，high=high/10，digit*=10

问题可推广为求0~9各自出现的总次数，对于1~9套用上述模板即可，

对于0因为不存在最高位为0的数，即没有0|*这种情况，

所以cur==0时个数为(high-1)*digit+low+1个，cur>0时为high*low个。

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

long count(long n, int k) { // 1~n中数字k出现的次数
    long low = 0, cur = n % 10, high = n / 10;
    long digit = 1, res = 0;
    while (high || cur) {
        if (k == 0) { // 0单独处理
            if (cur == 0)
                res += (high - 1) * digit + low + 1;
            else
                res += high * digit;
        }
        else {
            if (cur < k)
                res += high * digit;
            else if (cur == k)
                res += high * digit + low + 1;
            else
                res += (high + 1) * digit;
        }
        low += cur * digit;
        cur = high % 10;
        high /= 10;
        digit *= 10;
    }
    return res;
}
int main() {
    long a, b;
    cin >> a >> b;
    for (int k = 0; k < 10; k++)
        cout << count(b, k) - count(a - 1, k) << " ";
    cout << endl;
    return 0;
}

发表于 2022-07-10 18:41:06 回复(0)

Python 3

pein531

数位DP模板题，可以参考灵茶山艾府的模板“https://leetcode.cn/problems/count-special-integers/solution/shu-wei-dp-mo-ban-by-endlesscheng-xtgx/”，例题是力扣周赛第306场的压轴题，对模板稍作修改即可通过本题。

from functools import lru_cache

a, b = map(int, input().split())

@lru_cache(None)
def dfs(i: int, tot: int, is_limit: bool, is_num: bool) -> int:
    if i == n:
        return tot
    cnt = dfs(i + 1, tot, False, is_num) if not is_num else 0
    ub = int(s[i]) if is_limit else 9
    # 当前位置的数可以是[1-is_num, ub]
    for d in range(1 - int(is_num), ub + 1):
        cnt += dfs(i + 1, tot + int(digit == d), is_limit and d == int(s[i]), True)
    return cnt

for digit in range(0, 10):
    s = str(a - 1)
    n = len(s)
    lb = dfs(0, 0, True, False)
    dfs.cache_clear()
    s = str(b)
    n = len(s)
    ub = dfs(0, 0, True, False)
    dfs.cache_clear()
    print(ub - lb, end=' ')

发表于 2023-02-10 17:39:19 回复(0)