1 /*  2 本程序说明：  3   4 [编程题] 异或  5 时间限制：1秒  6 空间限制：32768K  7 给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。  8 输入描述:  9 第一行包含两个整数n,m. 10  11 第二行给出n个整数A1，A2，...，An。 12  13 数据范围 14  15 对于30%的数据，1 <= n, m <= 1000 16  17 对于100%的数据，1 <= n, m, Ai <= 10^5 18  19  20 输出描述: 21 输出仅包括一行，即所求的答案 22  23 输入例子1: 24 3 10 25 6 5 10 26  27 输出例子1: 28 2 29  30  31 链接：https://www.nowcoder.com/questionTerminal/fc05f68c5f47438db54c6923ef23cf4a 32 来源：牛客网 33  34 /* 35 C++ 36 思路来源：牛客网“潇潇古月”,在此表示感谢。 37 思路： 38     直接计算肯定是超时的，所以这问题不能使用暴力破解，考虑到从高位到地位，依次进行位运算， 39     如果两个数异或结果在某高位为1，而m的对应位为0，则肯定任何这两位异或结果为1的都会比m大。 40     由此，考虑使用字典树（TrieTree）从高位到第位建立字典，再使用每个元素依次去字典中查对应 41     高位异或为1， 而m为0的数的个数，相加在除以2既是最终的结果；直接贴出代码如下，非原创，欢迎讨论； 42     补充：queryTrieTree在搜索的过程中，是从高位往低位搜索，那么，如果有一个数与字典中的数异或结果 43     的第k位大于m的第k位，那么该数与对应分支中所有的数异或结果都会大于m， 否则，就要搜索在第k位异或 44     相等的情况下，更低位的异或结果。queryTrieTree中四个分支的作用分别如下： 45     1. aDigit=1， mDigit=1时，字典中第k位为0，异或结果为1，需要继续搜索更低位，第k位为1，异或结果为0，小于mDigit，不用理会； 46     2. aDigit=0， mDigit=1时，字典中第k位为1，异或结果为1，需要继续搜索更低位，第k位为0，异或结果为0，小于mDigit，不用理会； 47     3. aDigit=1， mDigit=0时，字典中第k位为0，异或结果为1，与对应分支所有数异或，结果都会大于m，第k位为1，异或结果为0，递归获得结果； 48     4. aDigit=0， mDigit=0时，字典中第k位为1，异或结果为1，与对应分支所有数异或，结果都会大于m，第k位为0，异或结果为0，递归获得结果； 49  50 改进： 51     1.字典树17位即可保证大于100000，移位范围为1~16位，则字典树构建时从16~0即可。 52        字典树第一层不占位，实际上是15~-1层有数据，这也是数据中next的用法。 53     2.queryTrieTree函数需要考虑到index为-1时的返回值。 54  55 时间复杂度：O(n)； 56 空间复杂度O(k),k为常数(trie树的高度)，因此可以认为O(1)。 57  */ 58 #include <iostream> 59 #include <vector> 60 using namespace std; 61  62 struct TrieTree 63 { 64     int count;//每个节点存的次数 65     struct TrieTree* next[2]{NULL,NULL};//每个节点存储两个节点指针 66     TrieTree():count(1){} 67 }; 68  69 TrieTree* buildTrieTree(const vector<int>& array) 70 { 71     TrieTree* trieTree = new TrieTree(); 72     for(int i=0;i<(int)array.size();++i) 73     { 74         TrieTree* cur = trieTree; 75         for(int j=16;j>=0;--j) 76         { 77             int digit = (array[i] >> j) & 1; 78             if(NULL == cur->next[digit]) 79                 cur->next[digit] = new TrieTree(); 80             else 81                 ++(cur->next[digit]->count); 82             cur = cur->next[digit]; 83         } 84     } 85     return trieTree; 86 } 87  88 //查询字典树 89 long long queryTrieTree(TrieTree*& trieTree, const int a, const int m, const int index) 90 { 91     if(NULL == trieTree) 92         return 0; 93  94     TrieTree* cur = trieTree; 95  96     for(int i=index;i>=0;--i) 97     { 98         int aDigit = (a >> i) & 1; 99         int mDigit = (m >> i) & 1;100 101         if(1==aDigit && 1==mDigit)102         {103             if(NULL == cur->next[0])104                 return 0;105             cur = cur->next[0];106         }107         else if(0 == aDigit && 1==mDigit)108         {109             if(NULL == cur->next[1])110                 return 0;111             cur = cur->next[1];112         }113         else if(1 == aDigit && 0 == mDigit)114         {115             long long val0 =  (NULL == cur->next[0]) ? 0 : cur->next[0]->count;116             long long val1 =  queryTrieTree(cur->next[1],a,m,i-1);117             return val0+val1;118         }119         else if(0 == aDigit && 0 == mDigit)120         {121             long long val0 =  queryTrieTree(cur->next[0],a,m,i-1);122             long long val1 =  (NULL == cur->next[1]) ? 0 : cur->next[1]->count;123             return val0+val1;124         }125     }126     return 0;//此时index==-1,这种情况肯定返回0（其他情况在循环体中都考虑到了）127 }128 129 //结果可能超过了int范围，因此用long long130 long long solve(const vector<int>& array, const int& m)131 {132     TrieTree* trieTree = buildTrieTree(array);133     long long result = 0;134     for(int i=0;i<(int)array.size();++i)135     {136         result += queryTrieTree(trieTree,array[i],m,16);137     }138     return result /2;139 }140 141 int main()142 {143     int n,m;144     while(cin>>n>>m)145     {146         vector<int> array(n);147         for(int i=0;i<n;++i)148             cin>>array[i];149         cout<< solve(array,m) <<endl;150     }151     return 0;152 }