发财兔1A

题目描述

给定一个长度为n的正整数序列a[i],计算出有多少个i<j的数对,a[i]+a[j]为二的次幂，也就是说存在一个正整数x满足a[i]+a[j]==2^x。

输入

第一行一个整数n。
第二行n个整数，其中第i个整数为a[i]。

输出

一行一个整数表示数对的数量。

样例输入

4
7 3 2 1

样例输出

提示

对于 20% 数据 n<=1000。
对于 50% 数据 n<=50000,0<=a[i]<=10^9。
对于 100% 数据 n<=1000000,0<=a[i]<=10^9。

思路：这里我是用字典树做的；

因为我们把一个数变成二进制后；

我们找的相对应的符合条件的字符串是确定的，例如如果我们找和3对应的符合要求的数时候；

我们可以知道3的二进制是11；

因此相对应的所要找的是1,101,1011,10111等;

如果二进制是9，二进制是1001；那么我们需要找的是111，11101，111011，1110111等

我们可以得到结论，满足条件的最小的值肯定是和需要找的串（长度为K）相加为2^K;

即与1000101满足条件的最小的值和他想加为00000001；

次大的数相加肯定为000000001，然后是000000001........;

因此我们对于一个值，我们只要找出这些满足条件的串就可以；

需要注意的是a[i]可能等于0，因此这种情况要单独处理；

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
int tree[5*maxn][3];
int sum[5*maxn];
int tot;
void insert_(int *str,int len)
{
   int root=0;
   for(int i=0;i<len;i++)
   {
       int id=str[i];
       if(!tree[root][id]) tree[root][id]=++tot;
       if(i==len-1)
       {
            sum[tree[root][id]]++;//记录节点访问次数
       }
       root=tree[root][id];
   }
   //root在此对应某个单词，一一对应
}
int find_(int *str,int len)
{
    int root=0;
    for(int i=0;i<len;i++)
    {
        int id=str[i];
       if(!tree[root][id]) return 0;
        root=tree[root][id];
    }
    return sum[root];//返回当前字符串结尾节点的访问次数，也就是作为前缀的出现次数
}
int main()
{
    tot=0;
    int n,m;
    cin>>n;
    ll ans=0;
    int ans0=0;
    int ans2=0;
    for(int i=0;i<n;i++)
    {
        int ss;
        int a[33];
        int b[33];
        scanf("%d",&ss);
        int k=0;
        if(ss==0)//记录零的个数,0不需要插入,只需要找到有多少个2^X就可以
        {
            ans+=ans2;
            ans0++;
            continue;
        }
        int temp=0;
        while(ss>0)
        {
            a[k++]=ss%2;
            if(ss%2==1)
            {
                temp++;
            }
            ss/=2;
        }
        if(temp==1&&k!=1)//记录多少个2^k,不能是1,k>0;
        {
            ans+=ans0;
            ans2++;
        }
        int po;
        for(int i=0;i<k;i++)
        {
           if(a[i]==1)
           {
               b[i]=1;
               po=i;
               break;
           }
           else
           {
               b[i]=0;
           }
        }
        for(int j=po+1;j<k;j++)
        {
            if(a[j]==0)
            {
                b[j]=1;
            }
            else
            {
                b[j]=0;
            }
        }
        int tempp;
        for(int jj=k-1;jj>=0;jj--)
        {
            if(b[jj]==1)
            {
                tempp=jj;
                break;
            }
        }
        ans+=find_(b,tempp+1);
        for(int ii=k;ii<32;ii++)
        {
            b[ii]=1;
            ans+=find_(b,ii+1);
        }
        insert_(a,k);
    }
    printf("%lld
",ans);
    return 0;
}