笔试刷题-头条2018-07-04

题目描述：

/**
给定整数m以及n各数字A1,A2,..An，
将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，
请求出这些结果中大于m的有多少个。
输入描述:
第一行包含两个整数n,m.
第二行给出n个整数A1，A2，...，An。
数据范围
对于30%的数据，1 <= n, m <= 1000
对于100%的数据，1 <= n, m, Ai <= 10^5
输出描述:
输出仅包括一行，即所求的答案
输入例子1:
3 10
6 5 10
输出例子1:
2
*/

思路如下：

建立数据的Trie树，并根据m进行剪枝即可
为了能剪枝，要在建立的时候再节点加入该节点下有多少个数的信息即可
这里的数字范围最多10^5, 所以17位就可以了
这里的插入全是17位的数据都是等长的

代码如下：

#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
 
#define MAX 100000
#define MAX_N 100000
#define MAX_DIGIT_NUM 17
//#define MAX_DIGIT_NUM 4
#define MAX_CHILDREN_NUM 2
 
typedef long long LL;
 
using namespace std;
 
struct TrieNode
{
    int numOfLeaves=0;
    TrieNode *children[MAX_CHILDREN_NUM];
    TrieNode()
    {
        for(int i=0; i<MAX_CHILDREN_NUM; i++)
            this->children[i]=NULL;
    }
};
 
class Dict
{
public:
    Dict() {}
 
    void add(int num)
    {
        int mask=1<<(MAX_DIGIT_NUM-1);
        TrieNode *curNode=this->root;
        for(int digitNum=MAX_DIGIT_NUM-1; digitNum>=0; digitNum--)
        {
            int curDigitOfNum=mask#
            curDigitOfNum=curDigitOfNum>>digitNum;
            TrieNode **children=curNode->children;
            if(children[curDigitOfNum]==NULL)
            {
                children[curDigitOfNum]=new TrieNode();
            }
            children[curDigitOfNum]->numOfLeaves++;
            //往下走
            curNode=children[curDigitOfNum];
            //掩码更新
            mask=mask>>1;
        }
    }
 
    int findQualifiedLeaves(int num, int target)
    {
        int accQualifiedLeaves=0;
        int mask=1<<(MAX_DIGIT_NUM-1);
        TrieNode *curNode=this->root;
        for(int digitNum=MAX_DIGIT_NUM-1; digitNum>=0; digitNum--)
        {
            if(curNode==NULL)
                break;
            int curDigitOfNum=mask#
            curDigitOfNum=curDigitOfNum>>digitNum;
            int curDigitOfTarget=mask⌖
            curDigitOfTarget=curDigitOfTarget>>digitNum;
            TrieNode **children=curNode->children;
            if(curDigitOfTarget==1){
                //此时不可能组合出比目标大的
                if(children[curDigitOfNum^1]==NULL){
                    break;
                    //return accQualifiedLeaves;
                }
                //还有可能组合出比目标大的，但只能走当前位的相反的位
                curNode=children[curDigitOfNum^1];
            }
            else if(curDigitOfTarget==0){
                //此时直接存在一个孩子的子树组合出比目标大的
                if(children[curDigitOfNum^1]!=NULL){
                    accQualifiedLeaves+=children[curDigitOfNum^1]->numOfLeaves;
                }
                //只需要往下走到跟当前位置相同的节点即可
                curNode=children[curDigitOfNum];
            }
            //掩码更新
            mask=mask>>1;
        }
        return accQualifiedLeaves;
    }
 
private:
    TrieNode *root=new TrieNode();
};
 
int nums[MAX_N];
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    //建立字典
    Dict *dict=new Dict();
    for(int i=0; i<n; i++){
        int num;
        scanf("%d", &num);
        if(num<1 || num>MAX)
            return -1;
        nums[i]=num;
        dict->add(num);
    }
    //计算总的对数包含了顺序
    LL totalPairs=0;
    for(int i=0; i<n; i++)
    {
        totalPairs+=(LL)dict->findQualifiedLeaves(nums[i], m);
    }
    printf("%lld", totalPairs/2);
    return 0;
}