给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。
思路不自己写了copy 牛客网大佬的吧
思路来源：潇潇古月 牛客网
思路：
直接计算肯定是超时的，所以这问题不能使用暴力破解，考虑到从高位到地位，依次进行位运算，
如果两个数异或结果在某高位为1，而m的对应位为0，则肯定任何这两位异或结果为1的都会比m大。
由此，考虑使用字典树（TrieTree）从高位到第位建立字典，再使用每个元素依次去字典中查对应
高位异或为1， 而m为0的数的个数，相加在除以2既是最终的结果；直接贴出代码如下，非原创，欢迎讨论；
补充：queryTrieTree在搜索的过程中，是从高位往低位搜索，那么，如果有一个数与字典中的数异或结果
的第k位大于m的第k位，那么该数与对应分支中所有的数异或结果都会大于m， 否则，就要搜索在第k位异或
相等的情况下，更低位的异或结果。queryTrieTree中四个分支的作用分别如下：
1. aDigit=1， mDigit=1时，字典中第k位为0，异或结果为1，需要继续搜索更低位，第k位为1，异或结果为0，小于mDigit，不用理会；
2. aDigit=0， mDigit=1时，字典中第k位为1，异或结果为1，需要继续搜索更低位，第k位为0，异或结果为0，小于mDigit，不用理会；
3. aDigit=1， mDigit=0时，字典中第k位为0，异或结果为1，与对应分支所有数异或，结果都会大于m，第k位为1，异或结果为0，递归获得结果；
4. aDigit=0， mDigit=0时，字典中第k位为1，异或结果为1，与对应分支所有数异或，结果都会大于m，第k位为0，异或结果为0，递归获得结果；
时间复杂度： O（n*k） , k代表Trie树的高度，因为 （1<<17）>1e5,这里高度最多为 k = 17
输入描述:
第一行包含两个整数n,m. 第二行给出n个整数A1，A2，...，An。数据范围对于30%的数据，1 <= n, m <= 1000对于100%的数据，1 <= n, m, Ai <= 10^5
输出描述:
输出仅包括一行，即所求的答案
示例1
输入
3 10 6 5 10
输出
2
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int shift = 17;
class Trie{
private:
struct TrieNode{
TrieNode():count(1), children(2, NULL){}
~TrieNode(){
for(TrieNode* child: children)
if(child)
delete child;
}
int count;
vector children;
};
unique_ptr root_;
public:
Trie():root_(new TrieNode()){}
void insert(const int num){
TrieNode* p = root_.get();
for(int i = shift;
i >= 0;
i--){
int t = (num>>i) & 1;
if(p->children[t] == NULL)
p->children[t] = new TrieNode();
else
p->children[t]->count++;
p = p->children[t];
}
}
// 根据m 查找
long long query(int n, int m, TrieNode* root, int index){
if(index < 0) return 0;
// 相当于等于m
int n_i = (n >> index) & 1;
int m_i = (m >> index) & 1;
if(root == NULL)
root = root_.get();
if(n_i == 0 && m_i == 1){//第index位异或得 1 的话， 则递归 （index-1)之后得位
return !root->children[1] ? 0 : query(n, m, root->children[1], index-1);
}
else if(n_i == 0 && m_i == 0){
// 异或能得 1 的
long long v1 = root->children[1] ? root->children[1]->count : 0;
long long v0 = root->children[0] ? query(n, m, root->children[0], index-1) : 0;
return v0 + v1;
}
else if(n_i == 1 && m_i == 1){
return !root->children[0] ? 0 : query(n, m, root->children[0], index-1);
}
else{ // 1, 0
long long v0 = root->children[0] ? root->children[0]->count : 0;
long long v1 = root->children[1] ? query(n, m, root->children[1], index - 1) : 0;
return v0 + v1;
}}
};
int main(){
int m, n;
cin>>n>>m;
vector nums(n);
Trie trie;
for(int i = 0;
i < n;
i++){
cin>>nums[i];
trie.insert(nums[i]);
}
long long res = 0;
for(const auto& num: nums){
res += trie.query(num, m, NULL, shift);
}
// 别忘了处以 2 ！！！
cout<< res / 2< 【C++|今日头条 编程题 2017 异或】
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 个人日记|K8s中Pod生命周期和重启策略
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）