while 循环的应用03-枚举与统计¶

这里结合 for 和 while，一个负责逐个选数，一个负责拆数位。

枚举入门¶

什么时候用？

如果候选答案不多，可以全部试一遍：检查每一个，把符合条件的留下来。这种方法叫“枚举”。

写循环之前，回答三个问题

枚举谁？例如整数 x、购买数量 a、位置 i。
从哪里到哪里？必须保证答案不会漏掉。
怎样判断符合要求？把题目条件变成 if。

最后再想：要输出所有答案、数答案个数，还是找最好的一个？

例一：找出 1 到 n 中能被 3 整除的数

约定 1 <= n <= 1000。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int x = 1; x <= n; x++) {
        if (x % 3 == 0) {
            cout << x << ' ';
            cnt++;
        }
    }
    cout << '\n' << cnt << '\n';
    return 0;
}

输入 10，第一行输出 3 6 9（末尾有空格），第二行输出 3。输入 2，第一行为空行，第二行是 0。

这里同时输出符合条件的数和个数。做题时，按要求保留对应的输出。

例二：两种笔，正好花完 n 元

一种笔 3 元一支，另一种 5 元一支。每种可以买 0 支，正好花完 n 元，有多少种购买方案？同一种笔的购买顺序不区分。

这里 0 <= n <= 1000，n 已经读入。

设两种笔各买 a、b 支，条件就是 3 * a + 5 * b == n。

两层枚举

这里用到了循环嵌套，没学过可以学完循环嵌套再看。

int cnt = 0;
for (int a = 0; a <= n / 3; a++) {
    for (int b = 0; b <= n / 5; b++) {
        if (3 * a + 5 * b == n) {
            cnt++;
        }
    }
}
cout << cnt << '\n';

输入 15，输出 2，方案是 (a, b) = (0, 3) 和 (5, 0)。输入 1 输出 0。

为什么从 0 开始？因为某种笔可以不买。为什么最多 n / 3 支？再多一支，光第一种笔就超预算了。

少试一些：枚举 a，算出 b

已知买了 a 支第一种笔，剩余 rest = n - 3 * a 元。只要剩余钱能被 5 整除，就恰好对应一种非负整数 b。

int cnt = 0;
for (int a = 0; a <= n / 3; a++) {
    int rest = n - 3 * a;
    if (rest % 5 == 0) {
        cnt++;
    }
}
cout << cnt << '\n';

本例允许 n 为 0，此时“不买任何笔”是一种方案，答案是 1。如果题目要求至少买一支，就要额外排除它。

第一种写法，a 每选一个值，都要把 b 从头试一遍。

第二种写法，只枚举 a，剩余钱数直接算，所以少了一层循环。

容易出错的地方

漏端点：题目包括 R，就不能写成 x < R。
重复计数：选两个人组队时，(1, 2) 和 (2, 1) 通常是同一队，可以令第二个编号从 i + 1 开始。
遗漏零：允许“不选”“不买”时，要考虑从 0 开始。
找到一个就停止：要统计所有方案时，不能找到第一种就 break。
范围太大：先估计要试多少次，不能不看数据范围就直接枚举。

L 到 R 中有多少个 2¶

这里也用到了循环嵌套。外层逐个选数，内层拆当前数的每一位。

先弄清楚：数“出现次数”，还是数“整数个数”？

本题统计闭区间 [L, R]（包括 L 和 R）中，所有整数的十进制写法里，数字 2 一共出现多少次。不添加前导零。

例如从 20 到 23：

整数	数字 2 出现次数
20	1
21	1
22	2
23	1

答案是 5，不是 4。如果题目问“有多少个整数含有 2”，答案才是 4。

拆成两件小事

外层：从 L 到 R，一个数一个数地选。
内层：拆开当前数的每一位，碰到 2 就让总次数加一。

拆数时必须使用副本 x。不能在内层一直修改外层变量 i，否则会破坏遍历顺序。

统计整个区间

这里 0 <= L <= R <= 1000000。

#include <iostream>
using namespace std;

int main() {
    int L, R;
    cin >> L >> R;
    long long cnt = 0; // 整个区间的总次数
    for (int i = L; i <= R; i++) {
        int x = i; // 每次换一个新的副本
        while (x) {
            if (x % 10 == 2) {
                cnt++;
            }
            x /= 10;
        }
    }
    cout << cnt;
    return 0;
}

输入 20 23，输出 5。

输入 0 0，循环不拆数位，结果为 0，也是正确的。统计数字 0 时，则要另外处理整数 0。

为什么变量放在这里？

cnt 在外层循环之前初始化：它要保留整个区间的总数。
x 在外层循环里面初始化：每换一个 i，都从这个新数开始拆。
遇到一个 2 后不能 break：22 中还有第二个 2。

若只统计“有多少个数含有 2”，才可以发现一个 2 就计数并停止拆当前数。

区间太大时，不能逐个数枚举。这里先处理不超过 1000000 的范围。

用这些数据检查自己

输入	输出	检查什么
`0 0`	`0`	0 里没有 2
`2 2`	`1`	L 和 R 相等也要检查
`22 22`	`2`	一个数可以贡献多次
`1 30`	`13`	十位和个位都要统计
`99 101`	`0`	区间跨位数也没关系