[CSP-J 2024] 扑克牌

GitHub跳转原题关系图返回列表

用布尔表记录已经出现过的花色和点数组合，答案就是完整牌库中未出现的种类数。

OJ: luogu

题目 ID: P11227

难度:入门

标签:模拟计数

日期: 2026-07-05 21:24

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

一副完整扑克牌有 44 种花色、1313 种点数，共 5252 种不同的牌。

现在给出小 P 已经借到的 nn 张牌，其中可能有重复。小 S 可以提供任意多张任意种类的牌。要求最少再借多少张，才能从所有牌中选出一副完整的 5252 张牌。

思路

这题的关键是：重复牌没有额外贡献。比如已经有两张 DQ，完整牌库中仍然只算“方片 Q 已经有了”。

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，枚举完整牌库中的 52 种牌，检查原牌中缺多少种。
#include <bits/stdc++.h>
using namespace std;

bool have[256][256];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string card;
        cin >> card;
        have[(int)card[0]][(int)card[1]] = true;
    }

    string suits = "DCHS";
    string ranks = "A23456789TJQK";
    int missing = 0;

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 13; j++) {
            if (!have[(int)suits[i]][(int)ranks[j]]) {
                missing++;
            }
        }
    }

    cout << missing << '\n';
    return 0;
}

brute.cpp 直接枚举完整牌库中的 4×134 \times 13 种牌，检查每种牌是否已经出现。

由于牌的种类只有 5252 种，正解可以更直接：读入每张牌时，用 seen[花色][点数] 记录这种牌是否出现过。第一次出现时，已拥有的不同牌种数 distinctcountdistinct_count 加一；重复出现则忽略。

最后答案就是：

text
52 - 已经拥有的不同牌种数

实现时可以直接用字符作为数组下标，例如 seen['D']['Q'] 表示方片 Q 是否出现过。这样不需要额外把花色和点数映射成编号。

代码

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

bool seen[256][256]; // seen[suit][rank] 表示这种花色和点数的牌是否已经出现

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int distinct_count = 0;
    for (int i = 1; i <= n; i++) {
        string card;
        cin >> card;
        char suit = card[0];
        char rank = card[1];
        if (!seen[(int)suit][(int)rank]) {
            seen[(int)suit][(int)rank] = true;
            distinct_count++;
        }
    }

    cout << 52 - distinct_count << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)，只需要记录固定的牌种。

总结

本题不要被“借多少张牌”绕进去，本质是统计已有牌中覆盖了多少种不同牌。重复牌不能减少需要补的牌数。