正文
将原式 \(a_i+a_j=2^p\) 转化为 \(a_j=2^p-a_i\),对于,每个 \(a_i\),枚举 \(p\),可以有效地降低时间复杂度。
设 \(num\leftarrow 0\),若 \(2^p-a_i\) 存在相等的 \(a_j\),则 \(num\leftarrow num+1\),最后输出 \(n-num\),可以通过 unordered_map
实现匹配。
代码:
#include<iostream>
#include<unordered_map>
#define gg long long
using namespace std;
const gg INF=2e9+5;
gg n,a[120005],ans;
unordered_map<gg,gg> s;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(gg i=1;i<=n;i++) cin>>a[i],s[a[i]]++;
for(gg i=1;i<=n;i++){
s[a[i]]--;
gg p=1;
bool flag=true;
while(p<=INF){
if(s[p-a[i]]>0) flag=false;
p<<=1;
}
if(flag) ans++;
s[a[i]]++;
}
cout<<ans;
}
提交记录。
后附
日志
v1.0 on 2022.11.11: 发布
标签:false,leftarrow,CodeForces,gg,num,1005,unordered From: https://www.cnblogs.com/wanguan/p/16884387.html