【例题2】The XOR Largest Pair（信息学奥赛一本通- P1472）

【题目描述】在给定的 N 个整数 A1,A2,…,AN 中选出两个进行异或运算得到的结果最大是多少【输入】第一行一个整数 N。第二行 N 个整数 Ai​​ 。【输出】一个整数表示答案。【输入样例】5 2 9 5 7 0【输出样例】14【提示】对于 100% 的数据1≤N≤10^5,0≤Ai2^31​​ 。题目分析本题是一道极其经典的算法面试与竞赛题要求在一个长度为 N 的数组中找出两个数字使得它们的异或XOR结果最大。 数据范围给到了 N≤10^5如果采用暴力的双重for循环两两匹配时间复杂度是 O(N^2)运算次数高达 10^10 级别毫无悬念会超时。这就逼迫我们必须寻找一个 O(Nlog(maxA)) 级别的高效算法。处理“最大异或值”问题的绝对标配就是01字典树。解题思路与思考过程异或运算的核心法则是相同为 0不同为 1。 要想让异或得到的值尽量大在二进制表示下我们必须秉持一个极其贪心的策略高位的 1 绝对比低位的 1 更重要。因此当我们拿着一个数字 X 去找它的“最佳异偶”时我们希望从它的最高位开始每一位都尽量找和它相反的数。思路演进初级思维字符串具象化最直观的想法是把所有的整数像十进制转二进制那样用%2和/2拆开存进vector补齐前导 0 后拼接成string然后当成普通的英文字符串插入字典树。这种做法逻辑上是通的也最符合人类的直觉思维。进阶思维位运算在计算机底层整数本身就是以 32 位二进制的形式静态躺在内存里的我们根本不需要脱裤子放屁去借助vector和string拆解它。直接利用位运算(xi)1就能在 1 个 CPU 时钟周期内瞬间精准提取出我们要的第 i 位是 0 还是 1。算法设计建树Insert把数组中所有的数从最高有效位第 30 位到最低位第 0 位依次取出其二进制的 0 或 1插入到一棵只有两个分叉0 通道和 1 通道的字典树中。查询Query拿着数字 X同样从最高位开始在树上遍历。取出 X 的当前位 Y。我们极其渴望走与它相反的路径 ZYˆ1。如果字典树中 Z 路径存在nxt[Z]!0果断走进去并且让最终答案累加 2^i因为这一位异或出了 1。如果 Z 路径不存在被逼无奈只能走相同的路径 Y。这一位异或结果为 0答案不累加。统计让数组里的每个数字都去树上跑一遍query维护全局最大值。时空复杂度分析时间复杂度每个数字插入和查询都需要遍历 31 位。建树复杂度为 O(31×N)查询复杂度为 O(31×N)。总体时间复杂度为 O(N)严格来说是 O(Nlog(maxA))面对 10^5 的数据运算不过几百万次速度极快。空间复杂度由于每个数字最多贡献 31 个节点总节点数不会超过 31×10^5。采用静态数组tree[4000000][2]空间复杂度为 O(Nlog(maxA))在正常内存限制内绝对安全。坑点总结pow函数的精度刺客使用cmath里的pow(2,k)计算 2 的次幂返回的是浮点数。在位数较高时极易因浮点精度丢失导致最终转成int时少 1。必须使用位运算1k来代替。字典树通道有效性判定判断一个节点是否存在是看它的nxt是否被分配过有效编号即nxt[v]!0不能写成nxt[v]1这会导致只认第一个分配的节点丢弃后续所有路径。0 的边界死角如果采用除 2 取余法拆解数字遇到 x0 时while(x!0)会直接跳过导致存入空串。位运算写法天然免疫此问题。两个版本代码的区别与演进下面展示这段代码的进化史。版本一普通字典树写法把十进制转二进制、位数对齐补 0、反转拼接成字符串的逻辑强行闭环非常直观但由于频繁申请vector和string内存常数极大且存在pow精度风险。版本二纯位运算标程剔除了所有多余的容器直接操作底层二进制位代码极度精简执行效率是版本一的数十倍以上属于竞赛必背的满分模板。版本一直观具象化写法普通字典树思想//普通字典树写法 可以全部ac 但是常数开销大 #include iostream #include algorithm//对应max函数 #include cmath//对应pow函数 算法竞赛中极不推荐用pow算2的次幂 #include vector using namespace std; int n; //a数组里每一行是一个vector用来暂存每个数字拆解后的二进制位 //注意由于是x%2拆解存入的顺序是 从低位到高位 vectorint a[100010];//存整数转换为二进制的结果 int sum;//计算最后异或结果的最大值 //字典树节点 struct treenode{ //状态转移表记录通往0和1两个方向的下一个节点编号门牌号 //里面存的是整数编号不能当成bool值来判断1 int nxt[2]; }tree[4000000]; int pc;//记录当前开辟到了第几个节点 //字典树插入(接受纯0/1组成的字符串) void insert(string s){ int p0;//每一轮从根节点开始 int lens.size(); for(int i0;ilen;i){ //如果该字符分支不存在 就开辟一个新空间给到它 if(tree[p].nxt[s[i]-0]0) tree[p].nxt[s[i]-0]pc; //更新指针位置 继续往下走 ptree[p].nxt[s[i]-0]; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; int len10;//存储所有整数转化为二进制后最长的那个位数 //先把所有整数转化为二进制数存起来 //a里面每一行存的是每一个整数二进制表示下从低位到高位 for(int i1;in;i){ int x; cinx; //先把x转换为二进制存储到a数组中 while(x!0){ a[i].push_back(x%2);//剥离最后一位 xx/2;//右移一位 } int len2a[i].size(); //更新最大二进制位数 len1max(len1,len2); } //接下来把每个整数位数不足len1的都在最后补0最高位 for(int i1;in;i){ //当前整数总位数 int len2a[i].size(); //补len1-len2个0 for(int j1;jlen1-len2;j) a[i].push_back(0); } //接下来把a每一行倒着存进s //这样就可以实现高位在前 低位在后 for(int i1;in;i){ string s; //倒着遍历实现 高位在前低位在后 的正确插入顺序 for(int jlen1-1;j0;j--) s(a[i][j]0); //接下来再把s插入字典树 insert(s); } //所有数字二进制插入完成后 //开始遍历每一个数字 然后与字典树进行异或 //如果1有通路就进入1否则进入0 计算最大值 for(int i1;in;i){ int ans0;//存储本轮选中数字与字典树异或的最大值 int p0;//每一轮从字典树根节点开始 string s; for(int jlen1-1;j0;j--){ s(a[i][j]0); } //从最高位往最低位遍历 for(int j0;jlen1;j){ //当s[j]1时 去看对应位数的字典树是否存在通往0路径 if(s[j]1){ //如果0存在 就加上这一位的值 if(tree[p].nxt[0]!0){ anspow(2,len1-j-1); //然后移动指针位置 ptree[p].nxt[0]; } //否则就值不变 移动位置 else ptree[p].nxt[1]; } //当s[j]0时 去看对应位数的字典树是否存在通往1路径 else if(s[j]0){ if(tree[p].nxt[1]!0){ anspow(2,len1-j-1); //然后移动指针位置 ptree[p].nxt[1]; } //否则就值不变 移动位置 else ptree[p].nxt[0]; } } summax(ans,sum); } coutsum; return 0; }版本二位运算写法竞赛标程//前面写法其实常数开销非常大 同时存在pow函数可能的精度问题 //是容易被卡掉的 //下面展示一个精简的位运算写法 运行速度是版本一的数十倍 #include iostream #include algorithm//对应max函数 using namespace std; int n; int a[100010];//原数组直接存十进制整数即可 struct treenode{ int nxt[2]; }tree[4000010]; int pc;//记录当前开辟到了第几个节点 int sum;//异或得到的结果的最大值 //字典树异或查询 int query(int x){ int ans0;//记录x能在字典树内异或得到的最大异或结果 int p0; for(int i30;i0;i--){ //(xi)1是位运算 通过将x右移i位并按位与1 //能够快速精准地提取出x的第i位是0还是1 int y(xi)1; //y^1也是位运算 0变1 1变0 //z就是我们当前这一步希望走进去的相反通道 int zy^1; //如果渴望的相反分支被开辟过存在 if(tree[p].nxt[z]!0){ ans(1i);//异或成功 加上这一位的权重 ptree[p].nxt[z];//走进相反分支 } //如果相反分支是死路 只能走进与自己相同的分支 //异或结果为0 不加分 else ptree[p].nxt[y]; } //走到树底 返回这次异或最大值 return ans; } //字典树插入 void insert(int x){ int p0; //统一从30位向下剥离 确保所有数字都在树上拥有相同长度的路径 for(int i30;i0;i--){ int y(xi)1;//提取当前位 //路径不存在 开辟新节点 if(tree[p].nxt[y]0) tree[p].nxt[y]pc; //下移 ptree[p].nxt[y]; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; //将每个整数插入字典树 for(int i1;in;i){ cina[i]; insert(a[i]); } //遍历每个数字与字典树进行异或找最大值 for(int i1;in;i){ summax(sum,query(a[i])); } coutsum; return 0; }