题解：P14292 [JOI2024 预选赛 R2] 卡牌游戏 / Card Game 2

分析题目

有

N

张卡牌，每张卡牌上都有一个整数

A_i

，其中

1 \le i \le N

。判断能否从中选出三张卡牌，选出的三张卡牌从大到小依次为

x,x+3,x+6

，

x

为某个整数。

代码思路

套三层循环，第二层循环从当前第一层循环的下标加一开始，依次向后枚举，如果当前的数为第一层循环的数加三，则第三层循环从这个数下标加一开始，依次向后枚举。如果当前的数为第二层的数加三，则直接输出 Yes 并结束程序。若三层循环循环完了也没有符合条件的，相当于没有输出 Yes，则输出 No。看不懂可以看一下代码。

CPP

for(int i=1;i<=n;++i)
{
	for(int j=i+1;j<=n;++j)
	{
		if(a[j]-a[i]==3)
		{
			for(int q=j+1;q<=n;++q)
			{
				if(a[q]-a[j]==3)
				{
					cout<<"Yes";
					return 0;
				}
			}
		}
	}
}
cout<<"No";
return 0;

不过这样时间复杂度为

\mathcal O(n^3)

，

n

最大为

200 \, 000

，很明显会超时，交上去后子任务 2 和 4 都出现了超时，因此需要优化一下代码。

想优化这个代码，可以选择减少无效判断的次数。对此，我们可以先将序列按升序排序，直接使用 sort 即可。当判断时，若这个数减去上一层循环的数大于三时，说明从这个数及以后的数减去上一层循环的数也大于三，因此直接结束这层循环即可。

CPP

sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
{
	for(int j=i+1;j<=n;++j)
	{
		if(a[j]-a[i]==3)
		{
			for(int q=j+1;q<=n;++q)
			{
				if(a[q]-a[j]==3)				
				{
					cout<<"Yes";
					return 0;
				}
				if(a[q]-a[j]>3) break;
			}
		}
		if(a[j]-a[i]>3) break;
	}
}
cout<<"No";
return 0;

这次代码可以解决子任务 4 的大部分超时，但子任务 2 的超时测试点与上次一样，因此还需优化。

注意到子任务 2 中

1 \le A_i \le 7

（

1 \le i \le N

），当数据过小时，会出现很多相同的数，因此还有很多无效判断，因此要对序列进行去重。对于去重，我选择是开一个新数组，当

i=1

或旧数组中当前下标对应的数与前一个数不同，则加入新数组，同时定义新变量存储当前新数组下标，初始为

0

，只要有可以加入新数组的数这个变量就加一，加完所有能加的数后该变量还能当作新数组的长度。之后的所有操作都变成对新数组的操作就行了。代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+5];
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	int b[n+5],l=0;
	for(int i=1;i<=n;++i)
	{
		if(i==1||a[i]!=a[i-1])
		{
			l++;
			b[l]=a[i];
		}
	}
	for(int i=1;i<=l;++i)
	{
		for(int j=i+1;j<=l;++j)
		{
			if(b[j]-b[i]==3)
			{
				for(int q=j+1;q<=l;++q)
				{
					if(b[q]-b[j]==3)
					{
						cout<<"Yes";
						return 0;
					}
					if(b[q]-b[j]>3) break;
				}
			}
			if(b[j]-b[i]>3) break;
		}
	}
	cout<<"No";
	return 0;
}

记录。

题解：P14292 [JOI2024 预选赛 R2] 卡牌游戏 / Card Game 2

文章操作

分析题目

代码思路

相关推荐

评论

题解：P14292 [JOI2024 预选赛 R2] 卡牌游戏 / Card Game 2