想学学「模拟」算法吗？【CSP-J 2024】扑克牌详细解析！

高山

如果你想学习学习「模拟」算法 或正在复习CSP第二轮

那你可以按照本系列的节奏进行

在本系列中，我们将带领鱼油一同回顾算法基础，完成CSP算法真题，帮助他们尽可能在复赛获得更高的分数。

话不多说，让我们先看看题目：

可使用配套的在线OJ评测本题->

                               
登录/注册后可看大图

P11227 [CSP-J 2024] 扑克牌
小 P 从同学小 Q 那儿借来一副 n 张牌的扑克牌。
本题中我们不考虑大小王，此时每张牌具有两个属性：花色和点数。

• 花色共有 4 种：方片、草花、红桃、黑桃。
• 点数共有 13 种，从小到大分别为 A、2、3、4、5、6、7、8、9、T、J、Q、K。
  注意：点数 10 在本题中记为 T。
  
  

【完整的一副牌】

我们称一副扑克牌是完整的，当且仅当对于每一种花色和每一种点数，都恰好有一张牌具有对应的花色和点数。
由此，一副完整的扑克牌恰好有 4 × 13 = 52 张牌。
如图：


【题意】

小 P 借来的牌可能不是完整的，为此小 P 准备再向同学小 S 借若干张牌。可以认为小 S 每种牌都有无限张，因此小 P 可以任意选择借来的牌。
小 P 想知道他至少得向小 S 借多少张牌，才能让从小 S 和小 Q 借来的牌中，可以选出 52 张牌构成一副完整的扑克牌。

【输入格式】

输入的第一行包含一个整数 n，表示牌数。
接下来 n 行：每行包含一个长度为 2 的字符串描述一张牌，其中第一个字符描述其花色，第二个字符描述其点数。
例如 CA 表示草花 A，ST 表示黑桃 T（黑桃 10）。

【输出格式】
输出一行一个整数，表示最少还需要向小 S 借几张牌才能凑成一副完整的扑克牌。

【输入输出样例】
输入 #1

1. 1
   
2. SA

复制代码

输出 #1

1. 51

复制代码

输入 #2

1. 4
   
2. DQ
   
3. DQ
   
4. DT
   
5. H3

复制代码

输出 #2

1. 49

复制代码

输入 #3

1. 52
   
2. DA DK D2 D3 D4 D5 D6 D7 D8 D9 DT DJ DQ C2 C3 C4 C5 C6 C7 C8 C9 CT CJ CQ CK HA HK H2 H3 H4 H5 H6 H7 H8 H9 HT HJ HQ S2 S3 S4 S5 S6 S7 S8 S9 ST SJ SQ SK

复制代码

输出 #3

1. 0

复制代码

【样例解释】
样例 1：这一副牌中包含一张黑桃 A，小 P 还需要借除了黑桃 A 以外的 51 张牌以构成一副完整的扑克牌。
样例 2：这一副牌中包含两张方片 Q、一张方片 T（方片 10）以及一张红桃 3，小 P 还需要借除了红桃 3、方片 T 和方片 Q 以外的 49 张牌。
样例 3：这一副扑克牌是完整的，故不需要再借任何牌。该样例满足所有牌按照点数从小到大依次输入，点数相同时按照方片、草花、红桃、黑桃的顺序依次输入。

【数据范围】

对于所有测试数据，保证：

条件	范围
牌数 n	1 ≤ n ≤ 52
字符串长度	2
首字符	D、C、H、S 之一
第二个字符	A 2 3 4 5 6 7 8 9 T J Q K 之一

【特殊性质】

特殊性质 A：保证输入的 n 张牌两两不同。
特殊性质 B：保证所有牌按照点数从小到大依次输入，点数相同时按照方片、草花、红桃、黑桃的顺序依次输入。

性质	条件
特殊性质 A	输入的 n 张牌两两不同
特殊性质 B	按点数从小到大输入，同点数按 D、C、H、S 顺序

zhangjinxuan

讲的很棒这里提供一个基于 std::set 的做法，用于拓展学习。

第一步转化为 52 - 输入数据中不同牌的个数，因此将所有输入的卡牌加入 std::set 中，根据 std::set 的特性，重复的卡牌不会被插入，最终集合的大小就是不同卡牌的个数。

该算法时间复杂度为 $O(n \log n)$，比原做法慢，但其有极强的通用性，可以支持多种复杂的卡牌类型。

1. 
   
2. // ...
   
3. int main() {
   
4.     set<string> s;
   
5.     int n;
   
6.     cin >> n;
   
7.     for (int i = 1; i <= n; ++i) {
   
8.         string card;
   
9.         cin >> card;
   
10.         s.insert(card);
    
11.     }
    
12.     cout << 52 - s.size() << "\n";
    
13.     return 0;
    
14. }
    

复制代码

FishC

思路

这题本质就是“去重计数”。

一副完整牌有 4 × 13 = 52 个位置。  
你手里每出现一张不同的牌，就占掉一个位置；重复的牌不会多占位置。  
所以答案就是：

52 - 已经出现过的不同牌数

步骤

1. 开一个 bool have[4][13]，表示每个花色、每个点数有没有出现过。
2. 把花色 D、C、H、S 映射成 0、1、2、3。
3. 把点数 A、2、3、…、T、J、Q、K 映射成 0 到 12。  
   注意：点数 T 表示 10，不能直接用 c - 'A'，因为字母不连续。
4. 每读入一张牌，就把对应位置标记成 true。
5. 最后统计 have 里有多少个 true，输出 52 - cnt。

参考代码

1. 
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. 
   
5. int getSuit(char c) {
   
6.     if (c == 'D') return 0;
   
7.     if (c == 'C') return 1;
   
8.     if (c == 'H') return 2;
   
9.     return 3; // S
   
10. }
    
11. 
    
12. int getRank(char c) {
    
13.     string r = "A23456789TJQK";
    
14.     for (int i = 0; i < 13; i++) {
    
15.         if (r[i] == c) return i;
    
16.     }
    
17.     return -1;
    
18. }
    
19. 
    
20. int main() {
    
21.     int n;
    
22.     cin >> n;
    
23. 
    
24.     bool have[4][13] = {false};
    
25. 
    
26.     for (int i = 0; i < n; i++) {
    
27.         string s;
    
28.         cin >> s;
    
29. 
    
30.         int suit = getSuit(s[0]);
    
31.         int rank = getRank(s[1]);
    
32. 
    
33.         have[suit][rank] = true;
    
34.     }
    
35. 
    
36.     int cnt = 0;
    
37.     for (int i = 0; i < 4; i++) {
    
38.         for (int j = 0; j < 13; j++) {
    
39.             if (have[i][j]) cnt++;
    
40.         }
    
41.     }
    
42. 
    
43.     cout << 52 - cnt << endl;
    
44.     return 0;
    
45. }
    

复制代码

注意

重复的牌只算一次，比如两张方片 Q，只会占一个位置。  
所以样例 2 中实际占的位置是：红桃 3、方片 T、方片 Q，共 3 个，答案是 52 - 3 = 49。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

空python

I会成功

犇犇犇

tater

青出于蓝

看看

18770897845

课件制作

青出于蓝 发表于 2026-9-23 10:31
看看