TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3214
  • 题目
  • P3214【USACO 2015 Feb Silver】犇
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    贝西和她的朋友们在参加一年一度的“犇”(足)球锦标赛。FJ的任务是让这场锦标赛尽可能地好看。
    一共有N支球队参加这场比赛,每支球队都有一个特有的取值在1-230-1之间的整数编号(即:所有球队编号各不相同)。
    “犇”锦标赛是一个淘汰赛制的比赛——每场比赛过后,FJ选择一支球队淘汰,淘汰了的球队将不能再参加比赛。锦标赛在只有一支球队留下的时候就结束了。
    FJ发现了一个神奇的规律:在任意一场比赛中,这场比赛的得分是参加比赛两队的编号的异或(Xor)值。例如:编号为12的队伍和编号为20的队伍之间的比赛的得分是24分,因为 12(01100) Xor 20(10100) = 24(11000)。
    FJ相信比赛的得分越高,比赛就越好看,因此,他希望安排一个比赛顺序,使得所有比赛的得分和最高。请帮助FJ决定比赛的顺序

    输入格式

    第一行包含一个整数N
    接下来的N行包含N个整数,第i个整数代表第i支队伍的编号

    输出格式

    一行,一个整数,表示锦标赛的所有比赛的得分的最大值

    样例输入

    4
    3
    6
    9
    10

    样例输出

    37

    提示

    1<=N<=2000
    样例解释:
    FJ先让编号为3和编号为9的队伍进行比赛,然后让编号为9的队伍赢得比赛(淘汰编号为6的队伍),现在剩下了编号为6 9 10 的队伍。
    然后他让编号为6和编号为9的队伍比赛,然后让编号为6的队伍赢得比赛。现在编号为 6 10 的队伍留了下来
    最后让编号为6和编号为10的队伍比赛,让编号为10的队伍赢得比赛。
    所有比赛的得分和就是: (3 Xor 9)+(6 Xor 9)+(6 Xor 10)=10+15+12=37