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

zhujianheng · 2025-08-16 22:51:51 · 题解

观察到一个性质，这个牌组为顺子当且仅当它在排完序的数组里面正好是公差为 1，项数为 K 的等差数列，很容易证明。

然后只要询问这样的等差数列存不存在就可以了。

对于这样的询问，我们考虑排序后的数组 a。

假设我们当前遍历到第 i 个数。

如果 a_i=a_{i-1}+1，那么最长的顺子的长度就加 1。如果加后，这个最长的顺子的长度达到 K，那么就存在这样一个数列。

如果 a_i=a_{i-1}，那么最长的顺子的长度不会增加，因为我们可以选 a_{p_1},a_{p_2},\cdots,a_{p_{cnt-1}},a_i，也可以选 a_{p_1},a_{p_2},\cdots,a_{p_{cnt-1}},a_{i-1}，其中 cnt 是当前的顺子的长度，p_i 是第 i 个选出的数的编号。所以这种情况没有变化。

如果 a_i>a_{i-1}+1，那么最长的顺子的长度就会到此终止，需要重新从 i 开始计算最长顺子长度。

这样，如果最后还没有找到顺子长度等于 K 的一种，那么就不存在，注意我们从 2 开始遍历，因为 a_1 不一定等于 1。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=300009;
int a[N];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    int cnt=1;
    for(int i=2;i<=n;i++)
        if(a[i]==a[i-1]+1){
            cnt++;
            if(cnt==k){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
        else if(a[i]==a[i-1]) continue;
        else cnt=1;
    cout<<"No"<<endl;
    return 0;
}