【最大异或和】

题目背景

USACO 2015 FEBRUARY CONTEST,SILVER——PROBLEM 3 SUPERBULL

题目描述

给定 N 个正整数 X1,X2 … XN 。
每次从 N 个正整数中选择两个数 Xi 和 Xj ,计算两数的异或值并累加入答案 S(S初始为0),然后删掉其中一个数(Xi或Xj),……,如此反复,直到只剩一个数为止,请你计算最后答案 S 的最大值是多少。

输入格式

第一行包含一个正整数 N(1≤N≤2000)。
接下来 N 行,每行一个正整数 Xi(1<=Xi<=230-1)。

输出格式

输出答案 S 的最大值。

样例数据 1

输入

4
3
6
9
10

输出

37

备注

【样例说明】
(1)第一次选择 3 和 9 进行异或,异或值为 10,并删除 3。此时剩下 6,9,10。
(2)第二次选择 6 和 9 进行异或,异或值为 15,并删除 9。此时剩下 6,10。
(3)第三次选择 6 和 10 进行异或,异或值为 12,并删除 6。此时剩下 6。结束。
所以最后的答案 S 为:(3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37

万万没想到是一道MST的题……对于一个i,把它跟所有其他点连一条边,权值就是a[i]^a[j],然后直接跑一遍最大生成树就OK了……

这种结合图论的思想还很需要学习啊!

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*