Points and Powers of Two

题目链接:http://codeforces.com/contest/988/problem/D
意思:从一堆数中选一个最大子集,使得任意两个数相减的绝对值都是2的幂。
思考:首先很难的一点,需要想到子集最多只能有三个,四个及以上的子集一定不存在(可以下去证明一下),有了这一条,我们可以考虑从三个的开始搜索,用set集合储存并对齐进行遍历。当有三个元素时,则必有其中两对元素之差相等(自行证明),那么可以对set中元素加上2的某次幂,减去2的某次幂,然后判断是否再set中,是的话即可输出。 对于两个元素和一个元素类比。(注意如果集合中只有一个元素不管是否为2的幂都要输出。)

注意:<<位运算优先级比+低,需要打括号。

代码:
#include<iostream>
#include<set>
using namespace std;

set<long long int> a;

int main(){
long long int n;
cin>>n;
long long int now;
while(n--){
cin>>now;
a.insert(now);
}
if(a.size()==1){
for(int i:a){
cout<<"1\n"<<i<<endl;
}
}
else{
int judge = 1;//判断是否已经存在解

for(long long int i:a){
    if(!judge)break;
for(int j=0;j<32;j++){
    if(a.count(i-(1LL<<j))&&a.count(i+(1LL<<j))){
    cout<<"3\n"<<i<<" "<<(i+(1LL<<j))<<" "<<(i-(1LL<<j))<<endl;//i-2的幂,i,i+2的幂 都要在set内即有解
    judge = 0;
    break;
    }
}
}

if(judge){
for(long long int i:a){
if(!judge)break;
for(int j=0;j<32;j++){
if(a.count(i+(1LL<<j))){
cout<<"2\n"<<i<<" "<<(i+(1LL<<j))<<endl;
judge = 0;
break;
}
}
}
}
if(judge){
for(int i:a){
if(!judge)break;
for(int j=0;j<32;j++){
if(i==(1LL<<j)){
cout<<"1\n"<<i<<endl;
judge = 0;
break;
}
}
}
}
}
return 0;
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。