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

观察到一个性质，这个牌组为顺子当且仅当它在排完序的数组里面正好是公差为

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:

CPP

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

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

文章操作

相关推荐

评论

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