专栏文章

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

DDoraeman
P13733题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioaeity
此快照首次捕获于
2025/12/02 15:59
3 个月前
此快照最后确认于
2025/12/02 15:59
3 个月前
查看原文

顺子的性质

根据顺子的定义和顺子的组成方式，显然可以得到以下性质：
  1. 顺子中所有牌最多使用 11 次；
  2. 顺子是有序的。

数据处理

根据性质 11，我们可以在输入时检查：如果这个元素出现过，就不必将其加入到 AA 序列中。得到无重复元素的 A′A' 序列。
显然这样做不会对结果造成任何影响。
根据性质 22，我们可以在将 A′A' 从小到大排序，得到有序的无重复元素的 A′′A'' 序列。
这个环节可以方便我们判断顺子是否存在。

说明解释

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

顺子判断

在有序不重序列 A′′A'' 中，如果存在连续的至少 KK 个数能满足：
A′′i+1=A′′i+1A′′i+1+1=A′′i+2… …A′′i+K−2+1=A′′i+K−1{A''}_i+1={A''}_{i+1}\\ {A''}_{i+1}+1={A''}_{i+2}\\ \dots\ \dots\\ {A''}_{i+K-2}+1={A''}_{i+K-1}\\
即从第二个数开始，每个数等于前一个数加 11，一共 KK 个数，那么这个子串就是包含 KK 个元素的顺子。
再次观察上式，可以发现，当 AA 序列任意两元素互不相等时，上述判定式可以等价为：
A′′i+K−1=A′′i+K−1{A''}_i+K-1={A''}_{i+K-1}
由此，每次只需要判断下标，就可以判断出是否存在顺子。

细节

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

代码

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...