题目描述
给定一个长度为n的正整数序列a[i],计算出有多少个i<j的数对,a[i]+a[j]为二的次幂，也就是说存在一个正整数x满足a[i]+a[j]==2^x。
输入
输入文件A.in。
第一行一个整数n。
第二行n个整数，其中第i个整数为a[i]。
输出
输出文件A.out。
一行一个整数表示数对的数量。
样例输入
4
7 3 2 1
样例输出
2
【样例输入2】
3
1 1 1
【样例输出2】
3
【数据范围】
对于 20% 数据 $ n \le 10^3 $
对于 50% 数据 $ n \le 5 \times 10^4 , 0 \le a_i \le 10^9 $
对于 100% 数据 $ n \le 10^6 , 0 \le a_i \le 10^9 $
这个题之前想枚举二的整次幂,然后二分查找判断来着....
于是代码长这样：
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define lowbit(x) ( - x & x )
#define ll long long
const int N = 1e6 + 5 ;
int n,v[N];
ll ans;
ll mi[N];
inline int read(){
int x = 0 , f = 1 ;char ch = getchar () ;
while(ch < '0' || ch > '9'){if(ch == '-') f = - 1 ;ch = getchar () ;}
while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( ch ^ 48 ) ;ch = getchar () ;}
return f * x ;
}
inline bool check ( int l , int r , int val ){
#define mid ( ( l + r ) >> 1 )
while( l <= r ){
if( v[mid] == val ) return true ;
if( v[mid] > val ) r = mid - 1 ;
if( v[mid] < val ) l = mid + 1 ;
}
#undef mid
return false ;
}
int main(){
n = read () ;mi[0] = 1 ;
for(int i = 1 ; i <= 33 ; ++ i ) mi[i] = ( mi[i - 1] << 1 ) ;
for(int i = 1 ; i <= n ; ++ i ) v[i] = read () ;
std::sort( v + 1 , v + n + 1 );
for(int i = 1 ; i <= n ; ++ i ){
int dir = std::upper_bound( mi + 1 , mi + 33 + 1 , v[i] ) - mi ;
int tmp = mi[dir] - v[i];
if( check( i , n , tmp ) ) ++ ans ;
}
printf("%lld\n" , ans );
return 0;
}
显然这个做法会T到飞起！
那么我就想怎么消 $ log $ 然后旁边的 $ wqy \ 大\ 佬\ && zs \ 大\ 佬\ $ 告诉我可以用双指针来优化,做到消除 $ log $
然后我冥思苦想,终于和 \(DYJ\) 在一番激烈争论后确定了这题的双指针怎么搞,于是就AC了
具体思路也不怎么难,大体就是先排一遍序,然后枚举二的整次幂,双指针扫区间,统计答案
扫区间的时候,不断地根据单调性移动指针就好了
要特判一坨一样的值,因为扫到一坨一样的值是可以直接 \(\Theta(1)\) 算出来的,完全不必要去扫
于是,代码长这样:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
#define Noip2018RPINF return 0
#define Ll long long
const int N = 1e6 + 3;
LL a[N];
int n,p[33];
inline int read(){
int v = 0,c = 1;char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') c = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
v = ( v << 3 ) + ( v << 1 ) + ( ch ^ 48 );
ch = getchar();
}
return v * c;
}
int main(){
n = read();
p[0] = 1;
long long ans = 0;
for(int i = 1;i <= 30;++i) p[i] = p[i - 1] << 1;
for(int i = 1;i <= n;++i) a[i] = read();
std::sort(a + 1,a + n + 1) ;
for(int j = 30;j >= 0;--j){
int l = 1,r = n ;
while(l < r){
while(a[l] + a[r] > (long long)p[j]) -- r ;
while(a[l] + a[r] < (long long)p[j]) ++ l ;
if(l >= r) break ;
if(a[l] == a[r]){if(a[l] + a[r] == (long long)p[j]) ans += (long long)(r - l + 1) * (r - l) / 2;break ;}
int ll = l,rr = r ; long long sum1 = 0,sum2 = 0;
if(a[ll] + a[rr] == (long long)p[j]){
while(a[ll] == a[l]) ++ sum1 , ++ ll ;
while(a[rr] == a[r]) ++ sum2 , -- rr ;
}
ans += sum1 * sum2 ; l = ll , r = rr ;
}
}
printf("%lld\n",ans);
Noip2018RPINF;
}