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

题目描述比太郎持有 张卡片第 张卡片1≤≤上写有一个整数 。他希望从这些卡片中选出满足以下条件的三张卡片。条件选出的三张卡片上所写的整数彼此相差 3。更精确地说选出的三张卡片上的整数可以表示为某个整数 以及 3、6。例如若比太郎持有 5 张卡片上面分别写着 2,4,5,7,10则选择写有 4,7,10 的三张卡片即可满足条件。给定比太郎所持卡片的信息请编写一个程序判断是否能够选出满足条件的三张卡片。输入格式输入以如下格式给出1 2 ⋯ 输出格式若能够选出满足条件的三张卡片则输出Yes否则输出No。输入输出样例 #1输入 #13 2 5 8输出 #1Yes输入输出样例 #2输入 #24 1 4 6 4输出 #2No输入输出样例 #3输入 #38 9 8 11 1 1 6 10 4输出 #3No输入输出样例 #4输入 #420 2 15 4 30 6 8 11 27 14 3 16 26 19 2 23 21 18 13 28 6输出 #4Yes说明/提示样例解释样例 1 可以选择 2,5,8样例 2,3 不存在可以选择的情况样例 4 可以选择 15,18,21约束3≤≤200000。1≤≤2000001≤≤。所有输入的值均为整数。子任务20 分3。20 分≤71≤≤。30 分≤100。30 分无额外约束。题解题意给出一个含有 N 个数的数组判断是否能够选出满足彼此相差 3的三个整数思路3≤≤200000。所以三重循环肯定是不行的。但是我们又知道了1≤≤2000001≤≤。所以可以运用桶数组用 m 记录最大值从 1 到 m-6 遍历一遍开始判断如果其中出现了 x、x3 和 x6 都存在的情况直接coutYes然后return 0。AC代码#includebits/stdc.h using namespace std; #define int long long bool z[100000005];//布尔类型避免MLE int a[111]; signed main(){ int t,n,m,i,x,j,k,l; // for(cint;t0;t--){ cinn; if(n100){//n100时三重循环不会TLE for(i1;in;i){ cina[i]; } sort(a1,an1); x0; for(j1;jn-2;j){ for(kj1;kn-1;k){ for(lk1;ln;l){ if(a[k]-a[j]3a[l]-a[k]3){ x1; break; } } if(x) break; } if(x) break; } if(x) coutYes\n; else coutNo\n; } else{//桶数组 m0; for(i1;in;i){ cinx; z[x]1; mmax(m,x); } x0; for(i1;im-6;i){ if(z[i]z[i3]z[i6]){ x1; break; } } if(x) coutYes\n; else coutNo\n; } // } // for(cint;t0;t--){//二分不会写﹏ // cinn; // for(i1;in;i){ // cina[i]; // } // sort(a1,an1); // bool x30,x60; // for(i1;in;i){ // x30,x60; // int si1,bn; // while(sb){ // int sb(sb)/2; // if(a[sb]a[i]3){ // bsb-1; // } // else if(a[sb]a[i]3){ // ssb1; // } // else{ // x31; // break; // } // } // if(!x3) // continue; // while(sb){ // int sb(sb)/2; // if(a[sb]a[i]6){ // bsb-1; // } // else if(a[sb]a[i]6){ // ssb1; // } // else{ // x61; // break; // } // } // if(x6){ // break; // } // } // if(x6) // coutYes\n; // else // coutNo\n; // } return 0; }