#1571. [USACO15FEB] Superbull S

[USACO15FEB] Superbull S

题面翻译

Bessie 和她的朋友们正在一年一度的 Superbull 锦标赛中打球,而 Farmer John 负责让比赛尽可能激动人心。总共有 N N 支队伍( 1N2000 1≤N≤2000 )参加了 Superbull 锦标赛。每个团队都有一个 1...2301 1 ... 2 ^ {30} -1 的团队 ID。

Superbull 是一场淘汰赛 - 在每场比赛之后,FJ选择淘汰其中一支球队,而被淘汰的球队再也无法参加任何比赛了。当只剩下一支球队时,比赛就结束了。

FJ 注意到一个不寻常的事情:在任何游戏中,两个团队的总分是两个团队ID的按位异或(XOR)。例如,如果第 12 12 队和第 20 20 队将参加比赛,则该游戏的得分为 24 24 分,因为 12 ^ 20 = 24,注意 ^C++ 的异或符号。

FJ 想要设计一种比赛方案,让所有比赛的得分总和最大。请帮助 Farmer John组织比赛。

输入格式

第一行包括一个整数 N N ,下面 N N 行每行包括一个队伍的 ID。

输出格式

输出一个整数,代表比赛的最大总得分。

4
3
6
9
10
37

提示

3 3 队与 9 9 队进行比赛,并让 9 9 队晋级。然后他让 6 6 队和 9 9 队对决,让 6 6 队获胜。最后,第 6 6 队和第 10 10 队比赛, 10 10 队获胜。总得分为:3 ^ 9 + 6 ^ 9 + 6 ^ 10 = 10 + 15 + 12 = 37