Superbull

题目描述

Bessie 和她的朋友们正在一年一度的 Superbull 锦标赛中玩 hoofball，而农夫 John 负责让比赛尽可能精彩。\n共有 $N$（$1 <= N <= 2000$）支队伍参加 Superbull。每支队伍都会被分配一个不同的整数队伍 ID，范围在 $1...2^{30}-1$，以便与其他队伍区分。\nSuperbull 是一项淘汰赛——每进行一场比赛后，农夫 John 会选择将哪支队伍从 Superbull 中淘汰，被淘汰的队伍将不能再参加任何比赛。Superbull 在只剩下一支队伍时结束。\n\n农夫 John 注意到比赛得分有一个非常不寻常的性质！在任何一场比赛中，两支队伍的总得分总是等于两队伍 ID 的按位异或（XOR）。例如，如果队伍 12 和 20 进行比赛，那么该场比赛会得到 24 分，因为 01100 XOR 10100 = 11000。\n\n农夫 John 认为一场比赛得分越高，比赛就越精彩。正因如此，他希望选择一系列要进行的比赛，使得 Superbull 中的总得分最大。请帮助农夫 John 安排比赛。

输入格式

第一行包含一个整数 $N$。\n接下来的 $N$ 行包含 $N$ 个队伍 ID。

输出格式

输出在 Superbull 中可能得到的最大总得分。

4\n3\n6\n9\n10

37

提示

输出说明：一种得到 37 的方式如下：FJ 让队伍 3 和 9 比赛，并决定 9 获胜，因此锦标赛中还剩下队伍 6、9 和 10。接着他让队伍 6 和 9 比赛，并让队伍 6 获胜。此时锦标赛中剩下队伍 6 和 10。最后，队伍 6 和 10 对决，队伍 10 获胜。总得分为 (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37。\n\n注：按位异或运算（bitwise exclusive OR），通常用 ^ 符号表示，是一种按位运算，对两个二进制整数的每一位分别进行逻辑“异或”运算。每一位的结果在仅当第一位为 1 或第二位为 1（两者恰有一个为 1）时为 1；如果两者都为 0 或都为 1，则为 0。例如：10100（十进制 20） XOR 01100（十进制 12） = 11000（十进制 24）\n[题目来源：Alex Yang, 2015]

标签: USACO|2015|Silver

来源

USACO|2015|Silver