B3949 题解

· · 题解

Source & Knowledge

2024 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定 n,k，求小于 10^n 的正整数中各数位之和小于等于 k 的数个数。

题目分析

注意到，n \le 7、k \le 100，也就是说最多只可能有 10^7 - 1 个数，可以直接使用枚举算法。

我们设小于等于 k 的数有 ans 个。对枚举到的每个数都计算它的数位和，如果小于等于 k 就给答案 ans 加一。最后输出 ans 即可。

int lim = 1;
for (int i = 1; i <= n; ++i) lim *= 10;
for (int i = 1; i < lim; ++i) {
    int sum = 0, tmp = i;
    while (tmp) sum += tmp % 10, tmp /= 10;
    if (sum <= k) ++ans;
}

视频讲解

完整代码见视频题解