题解：P13733 [JOIGST 2025] 扑克 / Poker

Doraeman · 2025-08-17 14:01:48 · 题解

顺子的性质

根据顺子的定义和顺子的组成方式，显然可以得到以下性质：

1. 顺子中所有牌最多使用 1 次；
2. 顺子是有序的。

数据处理

根据性质 1，我们可以在输入时检查：如果这个元素出现过，就不必将其加入到 A 序列中。得到无重复元素的 A' 序列。
显然这样做不会对结果造成任何影响。

根据性质 2，我们可以在将 A' 从小到大排序，得到有序的无重复元素的 A'' 序列。
这个环节可以方便我们判断顺子是否存在。

说明解释

事实上，C++ 标准模板库（STL）中有一个容器叫做 set，可以实现以上所有功能。
但是为了方便接下来的下标处理，我们不使用 set。

顺子判断

在有序不重序列 A'' 中，如果存在连续的至少 K 个数能满足：

即从第二个数开始，每个数等于前一个数加 1，一共 K 个数，那么这个子串就是包含 K 个元素的顺子。

再次观察上式，可以发现，当 A 序列任意两元素互不相等时，上述判定式可以等价为：

由此，每次只需要判断下标，就可以判断出是否存在顺子。

细节

很有可能遇到 i+K-1 超出 A'' 数组下标的情况，会发生数组越界导致 RE，所以需要特殊判断。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;

int n, k, a[N], cnt;
// 判断查重 
map <int, bool> p;

int main(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        // 如果不重复, 加入x
        if(!p[x]){
            p[x] = 1;
            a[++cnt] = x;
        } 
    }
    // 排序, 到此实现了set的功能 
    sort(a + 1, a + cnt + 1);

    // 检查顺子 
    for(int i=1; i<=cnt; i++)
        // 下标越界, 不检查 
        if(i+k-1 > cnt) continue;
        // 下标判断成功, 是顺子 
        else if(a[i]+k-1 == a[i+k-1]){
            cout << "Yes";
            return 0;
        }
    // 从始至终都没有找到顺子 
    cout << "No";
}