Day 6 · 数组进阶：桶计数

题意：Bessie 从 M 数到 N，把每个数都写下来。问数码 0~9 各出现了多少次。

思路

开一个 10 个元素的桶 cnt[0..9]。对区间里每个数，把它拆成各位数字，每拆出一位就往对应的桶里放一颗。

129 137

1 10 2 9 1 1 1 1 0 1

含义：0 出现 1 次、1 出现 10 次、2 出现 2 次 …… 8 出现 0 次、9 出现 1 次。

完整代码

#include <iostream>
using namespace std;

int cnt[10] = {0};          // 桶：cnt[d] = 数码 d 出现的次数

void countNumber(long long x){
    if(x == 0){ cnt[0]++; return; }     // 数字 0 本身（本题 M>=1 用不到）
    while(x > 0){
        cnt[x % 10]++;                  // 取末位，丢进对应的桶
        x /= 10;                        // 去掉末位
    }
}

int main(){
    long long M, N;
    cin >> M >> N;
    for(long long i = M; i <= N; i++){  // 区间长度 ≤ 5×10^5，直接枚举
        countNumber(i);
    }
    for(int d = 0; d < 10; d++){
        if(d) cout << " ";
        cout << cnt[d];
    }
    cout << endl;
    return 0;
}

易错点

• 用 int 存 M、N 是够的（2×10⁹ < 21亿），但用 long long 更保险。
• 输出是 10 个数字用空格隔开，注意最后一个后面不要多打空格（用 if(d) cout << " "; 或判断 d < 9）。
• 拆位必须用临时变量，不能直接改循环变量 i。

题意：在 1 到 n 的所有整数中，数字 x（0 ≤ x ≤ 9）共出现了多少次？

例：1 到 11 中，数字 1 在 1、10、11 里出现，共 4 次。

思路

枚举 1 到 n 的每个数，把每个数拆位，拆出来的每一位和 x 比一下，相等就答案 +1。

11 1

4

完整代码

#include <iostream>
using namespace std;
int main(){
    int n, x;
    cin >> n >> x;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int t = i;                      // ★ 用临时变量拆位，别把 i 本身改掉
        while(t > 0){
            if(t % 10 == x) ans++;      // 末位正好是 x，计数 +1
            t /= 10;                    // 去掉末位
        }
    }
    cout << ans << endl;
    return 0;
}

易错点

• 不要用 i 直接拆位——会用 i /= 10 把外层循环搞坏。必须 int t = i;。
• x = 0 的情况要能正确处理。因为 i 从 1 开始，不会遇到数字 0 本身，但 10、20、100 里的 0 会被正常统计到。
• 没必要求 i 有几位再循环——while(t > 0) 自动处理了。

题意：彩票每张 7 个号码（取值 1~33）。给出中奖号码和 n 张彩票，按「猜中几个号码」分别统计特等奖（7个）到六等奖（1个）各有几张。

不看位置，只看号码在不在中奖号码里。

2
23 31 1 14 19 17 18
12 8 9 23 1 16 7
11 7 10 21 2 9 31

0 0 0 0 0 1 1

第 1 张：中了 23、1 → 2 个 → 五等奖
第 2 张：中了 31 → 1 个 → 六等奖
输出顺序是「特等 一等 二等 三等 四等 五等 六等」。

完整代码

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;

    bool win[34] = {false};             // 桶：win[k] 标记号码 k 是不是中奖号
    for(int i = 0; i < 7; i++){
        int t; cin >> t;
        win[t] = true;
    }

    int result[8] = {0};                // result[k] = 中了 k 个号码的彩票张数
    for(int i = 0; i < n; i++){
        int hit = 0;
        for(int j = 0; j < 7; j++){
            int t; cin >> t;
            if(win[t]) hit++;           // O(1) 查桶
        }
        if(hit >= 1) result[hit]++;
    }

    // 题目要求：先输出特等奖(中7个)，再依次一等奖(6个)…六等奖(1个)
    for(int k = 7; k >= 1; k--){
        if(k < 7) cout << " ";
        cout << result[k];
    }
    cout << endl;
    return 0;
}

易错点

• 输出顺序是倒着的！题目要「特等奖、一等奖……六等奖」，也就是中 7 个的先输出。
  所以循环要写 for(k = 7; k >= 1; k--)，不是从小到大。
• 桶开 bool win[34] 就够（号码最大 33），下标 0 用不上也无所谓，多开一个更安全。
• 中 0 个号码的彩票不计入任何奖项，所以 result[0] 根本用不上，加个 if(hit >= 1) 更清楚。

题意：三个骰子分别有 S₁、S₂、S₃ 个面（面上是 1 到 Sᵢ）。掷出所有组合，哪个「三个点数之和」出现得最频繁？如果有并列，输出最小的那个和。

3 2 3

5

题目提示里给了全部 18 种组合：和 5 与和 6 各出现 5 次并列最多，取小的 → 5。

思路

三重循环枚举所有点数组合（最多 20×20×40 = 16000 种，非常小），把每个「和」丢进对应的桶。然后从小到大扫一遍桶，找出现次数最多的那个和。

完整代码

#include <iostream>
using namespace std;
int main(){
    int s1, s2, s3;
    cin >> s1 >> s2 >> s3;

    // 和的范围：最小 1+1+1 = 3，最大 20+20+40 = 80  ->  数组开到 85
    int cnt[85] = {0};

    // 三重循环枚举所有点数组合，把每个和丢进对应的桶
    for(int a = 1; a <= s1; a++)
        for(int b = 1; b <= s2; b++)
            for(int c = 1; c <= s3; c++)
                cnt[a + b + c]++;       // ★ 和是多少，就加在哪个桶

    int bestCount = 0, bestSum = 0;
    for(int s = 3; s <= 80; s++){       // 从小到大扫描
        if(cnt[s] > bestCount){         // ★ 用 > 而不是 >=
            bestCount = cnt[s];         //   并列时保留先遇到的（最小的和）
            bestSum = s;
        }
    }
    cout << bestSum << endl;
    return 0;
}

易错点

• 桶开太小：只开 20 会越界。记住 S₃ 上限是 40，最大和 80。
• 把 > 写成 >=：会输出最大的和而不是最小的。
• 三重循环的边界是 <= s1 不是 < s1——骰子面数是包含 Sᵢ 的。