AcWing 143 – 最大异或对

题目链接:AcWing 143

考虑把每个整数看作一个32位的01字符串,并把所有的二进制数对应的01串插入字典树(最低位为叶子结点),然后在字典树上DFS,用两个指针分别往相反的方向走,如果不存在相反方向,则走相同方向(Accepted/112ms)。

当然AcWing上的题解里面提供了另一种方法,就是修改字典树的search函数,每次search一个数字$x$的01串,然后search的时候优先走相反的方向,如果没有的话则走相同的方向,也可以解决这个问题(Accepted/144ms)。(好像我的方法还快一点?)

 

说点什么

avatar
50
  Subscribe  
提醒