当前位置：首页 > news >正文

【C++】P2550 [AHOI2001] 彩票摇奖

news 2025/7/7 19:49:26

在这里插入图片描述

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

文章目录

💯前言
💯题目描述
- 输入格式：
- 输出格式：
- 输入输出样例：
💯题解思路
- 1. 问题解析
💯我的实现
- 实现逻辑
- 问题分析
💯老师的实现
- 实现逻辑
- 优势分析
💯代码优化与拓展
- 优化方案
- - 改进代码
- 优化效果
💯小结

在这里插入图片描述

💯前言

在C++编程学习中，理解和解决复杂问题的能力是关键。本篇文章围绕一个实际的竞赛题目展开——“彩票中奖判定问题”，从题目描述、我的实现、老师的实现到代码优化和拓展，逐步展开详细的分析和讲解，希望帮助读者提升编程思维。
C++ 参考手册

💯题目描述

以下是题目原文：
P2550 [AHOI2001] 彩票摇奖
在这里插入图片描述

题目编号：P2550 [AHOI2001] 彩票摇奖

为了丰富人群的生活，支持某些社会公益事业，北塔市设置了一项彩票。该彩票的规则是：

每张彩票上印有 7 个各不相同的号码，且这些号码的取值范围为 1~33。
每期开奖时随机摇出一个由 1~33 这 33 个自然数构成的中奖号码。
共设置 7 个奖项，特等奖——一等奖至六等奖。

中奖规则如下：

特等奖： 要求彩票上 7 个号码都出现在中奖号码中。
一等奖： 要求彩票上 6 个号码出现在中奖号码中。
二等奖： 要求彩票上 5 个号码出现在中奖号码中。
三等奖： 要求彩票上 4 个号码出现在中奖号码中。
四等奖： 要求彩票上 3 个号码出现在中奖号码中。
五等奖： 要求彩票上 2 个号码出现在中奖号码中。
六等奖： 要求彩票上 1 个号码出现在中奖号码中。

注意：先忽略开奖号码与彩票号码中各个号码出现的顺序。例如，如果中奖号码为 23 31 11 14 19 17 18，则彩票 12 8 9 23 11 16 7 中由于其有两个号码（23 和 11）出现在中奖号码中，所以以该彩票算作五等奖。

输入格式：

输入的第一行为一个自然数 $n$ ，表示小明购买彩票数。
第二行存放了 7 个介于 1 和 33 之间的自然数，表示中奖号码。
在随后的 $n$ 行中，每行有 7 个介于 1 和 33 之间的自然数，分别表示小明所买的 1 张彩票。

输出格式：

依次输出小明所买的彩票的中奖情况（中奖的张数），首先输出特等奖的中奖张数，然后依次输出一等奖至六等奖的中奖张数。

输入输出样例：

输入：

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

输出：

0 0 0 0 0 1 1

💯题解思路

1. 问题解析

本题的关键是如何高效判断每张彩票和中奖号码之间的匹配程度，并据此统计各个奖项的中奖张数。

主要挑战在于：

号码匹配的效率： 如何快速比较彩票号码和中奖号码。
中奖等级的计算： 根据匹配数量归类到正确的奖项。

下面将从我的实现和老师的实现分别展开分析。

💯我的实现

以下是我的实现代码：

#include <iostream>
#include <cmath>
using namespace std;
int arr1[1005];
int arr2[1005][1005];
int arr3[7];
int main()
{int n = 0;cin >> n;for(int i = 0; i < 7; i++)cin >> arr1[i];for(int i = 0; i < n; i++){for(int j = 0; j < 7; j++){cin >> arr2[i][j];}}for(int i = 0; i < n; i++){int count = 0;for(int j = 0; j < 7; j++){for(int m = 0; m < 7; m++){if(arr1[m] == arr2[i][j])count++;}}if(count != 0)arr3[7 - count]++;}for(int i = 0; i < 7; i++){cout << arr3[i] << " ";}return 0;    
}

在这里插入图片描述

实现逻辑

输入部分：
- 使用 arr1 存储中奖号码。
- 使用二维数组 arr2 存储每张彩票的 7 个号码。
匹配逻辑：
- 使用双重嵌套循环对每张彩票的每个号码和中奖号码进行逐一比对。
- 统计匹配数量 count，并根据 7 - count 更新中奖等级计数。
输出部分：
- 按特等奖到六等奖的顺序输出中奖张数。

问题分析

效率低下：
- 双重嵌套循环导致时间复杂度为 $\times 7 \times 7)$ ，对于较大规模输入，效率较低。
冗余判断：
- 判断 if(count != 0) 是多余的，因为即使匹配数量为 0，更新 arr3[7 - count] 也不会出错。

💯老师的实现

以下是老师的实现代码：

#include <iostream>
using namespace std;int ans[7]; // 中奖数字
int ans_c[7]; // 中奖个数int main()
{int n = 0;int num = 0;cin >> n;// 输入中奖号码for (int i = 0; i < 7; i++){cin >> ans[i];}// n次测试while (n--){int cnt = 0; // 统计匹配的号码数量// 循环输入彩票上的7个号码for (int i = 0; i < 7; i++){cin >> num;// 每个号码和一次中奖号码比较for (int j = 0; j < 7; j++){if (num == ans[j]){cnt++;break;}}}ans_c[7 - cnt]++; // 更新中奖个数}for (int j = 0; j < 7; j++){cout << ans_c[j] << " ";}return 0;
}

在这里插入图片描述

实现逻辑

输入部分：
- 使用数组 ans 存储中奖号码。
匹配逻辑：
- 使用嵌套循环对比彩票号码与中奖号码，统计匹配数量 cnt。
- 使用 break 提前终止内层循环，减少多余操作。
结果更新：
- 根据 7 - cnt 更新中奖等级。

优势分析

逻辑清晰：
- 将匹配操作和统计结果分离，代码结构简单易懂。
效率合理：
- 使用 break 提前退出循环，优化部分操作。

💯代码优化与拓展

优化方案

通过引入哈希表进一步提升效率。

改进代码

#include <iostream>
#include <unordered_set>
using namespace std;int main() {int n; // 彩票数量cin >> n;unordered_set<int> winning_numbers; // 存储中奖号码for (int i = 0; i < 7; i++) {int number;cin >> number;winning_numbers.insert(number);}int prize_count[7] = {0}; // 统计每个奖项的中奖张数while (n--) {int match_count = 0; // 当前彩票匹配的号码数量for (int i = 0; i < 7; i++) {int ticket_number;cin >> ticket_number;if (winning_numbers.count(ticket_number)) {match_count++;}}prize_count[7 - match_count]++;}for (int i = 0; i < 7; i++) {cout << prize_count[i] << (i == 6 ? "" : " ");}return 0;
}