111qqz的小窝

老年咸鱼冲锋!

hdu 5536 || 2015 长春区域赛 J Chip Factory (带删除操作的trie树)

hdu 5536 题目链接

题意:给出n个数,然后问最大的(a[i]+a[j])^a[k]  (i,j,k互不相同)

思路:异或和最大很容易想到字典树。。但是如何保证i,j,k互不相同这里没有想明白。。。。。我的想法是加一个标记代表之前的id,但是我加的标记是只有在叶子节点上才有的。。。也就是会出现走到了最后一步才发现这个节点是不能走的情况。。。

正确的做法是,加一个cnt标记。

每次插入的时候,这个数从根节点到叶子节点每个节点的cnt都+1

删除的时候做就是每个节点的cnt都-1.

这样子每次Find的时候只走cnt>0的点。。

 

这种做法的正确性基与:

两个不同的数。。一定有至少一位的二进制数不同。。。保证了当只出现过一次的数x被删掉以后,其他的数y的存在不会导致经过x的路径

两个相同的数,每一位二进制数位都是相同搞的。  保证了id不同的相同的数。。即使一个被删掉。。另外的也可以继续访问。。。因为cnt仍然是大于0的。。。

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz