PS:(刚刚在吃饭)这题考试没完成,也就60%的完成度,思想是有的,只不过有的有点晚,刚刚又改了一下,过了,现在讲一下我的解题思路
拿到这题我也有点懵,首先我想到暴力,但数据量就否定了我的想法,而且刚开始我也不知道他最多能有几个数,
可能有几千,几万个数,那这更不可能循环了,那怎么做呢,我陷入了思考(思考了很长时间)。
我想还是根据题意来思考这个子集和里的数都是什么关系,任选两个数的差的绝对值一定要是2的整数次幂,即1
,2,4,8……,那我构造一些数据看看它有什么规律,例如我第一个数取1,第二个数取个2,第三个呢?只能取3,因为取其他的都不满足,这三个差值为1,1,2均为2的整数幂,符合条件,那么,第四个应该取什么值才能延续这种正确性呢?我试了很多数,都不行,因为你新插的数与3一定要差2的整数幂,那不管怎么算,加上之前的差值,必然不能满足差的还是2的整数幂(大家可以写一写) 这时,我还以为是我取的数有问题,因为我取的是一个等差序列了,所以我重新取数,第一个为2,第二个为4,第三个呢这回不取差值为2的数了,那么取什么呢?没有了,因为取其它的差值,如果他不为2(跟之前一样),那么怎么加都不可能为2的整数次幂,即不符合要求。
我这时其实其实还是有点懵,因为我以为是我能力有限连数据都构造不出来,但当我开始任意写数据测试时,发现,好像真的不能超过3这个集合的大小,没有任何一种可能。然后,我就联想到我以前写过有一道题,题目很长,很复杂,读完也是很懵,感觉可能性太多了,但最后就只有一种可能,其他的都否定了,题干就是迷惑人用的,我想到这,基本就肯定了这题答案就是在1~3之间,接下来就是写代码了。
我会在代码上写详细注释
#pragma GCC optimize(2) //o2优化,非常快,牛客竞赛网上也能用
#pragma GCC optimize(3) //o3优化
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[200010],n,maxx;
vector<ll> vec; //用来存储最终的正确答案
int main ()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&f[i]);
sort(f+1,f+1+n); //排序,因为我们要用二分来快速查找我们想要的值,所以得有单调性
for(int i=1;i<=n;i++)
{
vector<ll> p;
p.push_back(f[i]); //先把这个数放进去,好查找下一个数
for(int j=0;j<=30;j++) //注意,这里不能在循环一次集合,太慢了,我们要枚举差值,构造下一个数
{
int pos1=lower_bound(f+1,f+1+n,p[0]+pow(2,j))-f; //找第二个数,差值为2的j次幂
if(pos1>n||f[pos1]!=p[0]+pow(2,j)) //没找到跳过
continue;
p.push_back(f[pos1]);
int pos2=lower_bound(f+1,f+1+n,2*p[1]-p[0])-f; //找第三个数,看看能否找到
if(pos2<=n&&f[pos2]==2*p[1]-p[0]) //找到了,加入
p.push_back(f[pos2]);
if(p.size()>maxx) //更新最大值
{
maxx=p.size();
vec=p;
}
p.erase(p.begin()+1,p.end()); //记得找没找到第三个数都要删除后面的数,只保留第一个
if(maxx==3) //3就是最大的,如果的3了,直接退出循环即可
break;
}
if(maxx==3) //已经最大了,直接退出
break;
}
if(maxx==0) //我这里只讨论了2和3的情况,如果最大值为0,意味着即为1,输出随便一个数即可
{
printf("1\n");
printf("%lld",f[1]);
}
else
{
cout<<maxx<<endl;
for(int i=0;i<vec.size();i++)
cout<<vec[i]<<" ";
}
return 0;
}
厉害厉害orz