RDay1-Problem 1 A

题目描述

给定一个长度为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】

3

1 1 1

【样例输出2】

【数据范围】

对于 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;

}

巴特西

RDay1-Problem 1 A

最新文章

热门文章