【题目来源】
洛谷：P6824 「EZEC-4」可乐 - 洛谷
【题目描述】
pigstd 现在有 \(n\) 箱可乐，第 \(i\) 箱可乐上标着一个正整数 \(a_i\)。
若 pigstd 的聪明值为一个非负整数 \(x\)，对于第 \(i\) 箱可乐，如果 \((a_i\oplus x)≤k\)，那么 pigstd 就能喝到这箱可乐。
现在 pigstd 告诉了你 \(k\) 与序列 \(a\)，你可以决定 pigstd 的聪明值 \(x\)，使得他能喝到的可乐的箱数最大。求出这个最大值。
【输入】
第一行两个由空格分隔开的整数 \(n,k\)。
接下来 \(n\) 行，每行一个整数 \(a_i\)，表示第 \(i\) 箱可乐上标的数。
【输出】
一行一个正整数，表示 pigstd 最多能喝到的可乐的箱数。
【输入样例】
3 5
2
3
4
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P6824 可乐》 #贪心# #字典树,Trie# #差分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量声明
int trie[2000005][3]; // 字典树数组，[0]和[1]表示二进制位，[2]表示计数
int len = 1; // 字典树节点计数器
int k, n, x, maxs; // k:异或阈值，n:数字数量，x:临时变量，maxs:最大满足条件的数对数量/*** 构建字典树* @param x 要插入的数字*/
void build(int x)
{int fa = 0; // 当前父节点索引（从根节点0开始）for (int i = (1 << 20); i > 0; i >>= 1) // 从最高位到最低位处理{bool a = x & i; // 获取当前位的值(0或1)if (!trie[fa][a]) // 如果当前位对应的子节点不存在{trie[fa][a] = len; // 创建新节点fa = len++; // 移动到新节点}else{fa = trie[fa][a]; // 移动到已有节点}trie[fa][2]++; // 增加当前节点的计数}
}/*** 查询满足条件的数对数量* @param x 要查询的数字* @return 满足x^y >= k的数对(x,y)数量*/
int query(int x)
{int fa = 0, ans = 0, child, f = 0; // fa:当前节点，ans:结果计数，child:子节点，f:提前终止标志for (int i = (1 << 20); i > 0; i >>= 1) // 从最高位到最低位处理{bool a = x & i; // 当前数字的当前位bool b = k & i; // 阈值k的当前位if (b) // 如果k的当前位为1{child = trie[fa][1 - (a ^ b)]; // 计算满足条件的子节点ans += trie[child][2]; // 累加满足条件的数量}fa = trie[fa][a ^ b]; // 移动到下一个节点if (fa == 0) // 如果节点不存在{f = 1; // 设置提前终止标志break;}}if (f == 0) // 如果没有提前终止{ans += trie[fa][2]; // 累加最后节点的计数}return ans;
}int main()
{// 输入数字数量和异或阈值cin >> n >> k;// 构建字典树for (int i = 0; i < n; i++){cin >> x;build(x);}// 查找最大满足条件的数对数量for (int i = 0; i <= 2e6; i++){maxs = max(maxs, query(i));if (maxs == n) // 如果已经找到最大可能值{break;}}// 输出结果cout << maxs << endl;return 0;
}
【运行结果】
3 5
2
3
4
3