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

---

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

---

---

---

💯前言

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

---

---

💯题目描述

以下是题目原文：
P2550 [AHOI2001] 彩票摇奖

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

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

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

中奖规则如下：

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

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

输入格式：

1. 输入的第一行为一个自然数 $n$，表示小明购买彩票数。
2. 第二行存放了 7 个介于 1 和 33 之间的自然数，表示中奖号码。
3. 在随后的 $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. 问题解析

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

主要挑战在于：

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

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

---

💯我的实现

以下是我的实现代码：

#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;    
}

实现逻辑

1. 输入部分：

   • 使用 arr1 存储中奖号码。
   • 使用二维数组 arr2 存储每张彩票的 7 个号码。

2. 匹配逻辑：

   • 使用双重嵌套循环对每张彩票的每个号码和中奖号码进行逐一比对。
   • 统计匹配数量 count，并根据 7 - count 更新中奖等级计数。

3. 输出部分：

   • 按特等奖到六等奖的顺序输出中奖张数。

问题分析

1. 效率低下：
   • 双重嵌套循环导致时间复杂度为 $O(n\times 7\times 7)$，对于较大规模输入，效率较低。
2. 冗余判断：
   • 判断 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;
}

实现逻辑

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

优势分析

1. 逻辑清晰：
   • 将匹配操作和统计结果分离，代码结构简单易懂。
2. 效率合理：
   • 使用 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;
}

优化效果

1. 使用哈希表代替嵌套循环，比对效率从 $O(7\times 7)$ 降为 $O(7)$。
2. 改善代码可读性，增强灵活性。

---

💯小结

• 
  通过对“彩票中奖判定问题”的分析和代码实现，我们理解了从问题分解到优化的完整过程。无论是初步实现还是优化版本，掌握问题的本质和高效解决方案是编程学习的重要目标。希望本篇文章能对读者有所帮助！

---

---