[AHOI2001] 彩票摇奖

题意

给出 7 个中奖号码和 n 张彩票。每张彩票也有 7 个号码。匹配 7 个是特等奖，匹配 6 个是一等奖，依次到匹配 1 个是六等奖。输出每个奖项各有多少张彩票。

思路

题目不关心号码顺序，只关心是否出现，所以用集合最自然。

把中奖号码存成 winning。对每张彩票，把它也转成集合 ticket，两者交集：

text

1winning & ticket

就是命中的号码集合。交集大小 match_count 表示命中几个号码。

输出顺序是命中 7,6,5,4,3,2,1 个，因此数组下标可以写成：

text

1answer[7 - match_count] += 1

如果 match_count = 0，没有奖项，不统计。

这题是集合统计练习，正解已经直接对应题意，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 map(int, input().split()) 读取号码。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：set 适合做去重和成员关系判断。
winning & ticket 是集合交集。
len(...) 得到命中号码个数。
print(*answer) 按空格输出七个奖项数量。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12ticket_count = int(input())
winning = set(map(int, input().split()))

answer = [0] * 7

for _ in range(ticket_count):
    ticket = set(map(int, input().split()))
    match_count = len(winning & ticket)
    if match_count > 0:
        answer[7 - match_count] += 1

print(*answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int win[7];      // 中奖号码
bool is_win[34]; // 标记某个号码是否中奖号码（号码范围 1~33）
int ans[8];      // ans[i] 表示匹配 i 个号码的彩票数
int n;

int main() {
    cin >> n;
    for (int i = 0; i < 7; i++) {
        cin >> win[i];
        is_win[win[i]] = true;
    }
    for (int i = 1; i <= n; i++) {
        int cnt = 0; // 该张彩票命中个数
        for (int j = 0; j < 7; j++) {
            int x;
            cin >> x;
            if (is_win[x]) cnt++;
        }
        ans[7 - cnt]++; // 匹配 cnt 个对应第 7-cnt 等奖
    }
    for (int i = 0; i < 7; i++) cout << ans[i] << " ";
    return 0;
}

Pythonic 写法

set 交集：

python

1
2
3
4
5
6
7
8n = int(input())
win = set(map(int, input().split()))
ans = [0] * 7
for _ in range(n):
    hit = len(win & set(map(int, input().split())))
    if hit:
        ans[7 - hit] += 1
print(*ans)

复杂度

每张彩票只有 7 个号码，单张处理是常数时间。总时间复杂度是 $O(n)$ ，空间复杂度是 $O(1)$ 。

总结

这题的关键是看出“顺序无关”。用集合求交集，可以直接得到命中号码数量。

[AHOI2001] 彩票摇奖

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结