111qqz的小窝

老年咸鱼冲锋!

hdu 4828 Xor Sum (trie 树模板题,经典应用)

hdu 4825 题目链接

题意:给定n个数,然后给出m个询问,每组询问一个数x,问n中的数y使得x和y的异或和最大。

思路:字典树。。把每个数转化成二进制,注意补全前导0,使得所有数都有相同的位数。

如果想要异或和最大,那么每一位尽可能都是1.

所以做法是,先构建字典树,然后每次find的时候,尽可能按照和当前寻找的数的位相反的位的方向走(如果有的话)

比如当前位是1,那我就往0的方向走。

需要注意的是,多组数据,每次要重新初始化一遍。

做法是 在struct 中重新 root = new Node() 一下。。这样就重新调用了Node中初始化用的构造函数。

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz