题目名称	1941. 超牛冠军赛
输入输出	`superbull.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cqw 于2015-04-20加入
开放分组	全部用户
提交状态
分类标签	最小生成树
	分享题解

通过：46，提交：88，通过率：52.27%
cstdio	100	0.064 s	0.33 MiB	C++
Sky_miner	100	0.071 s	0.33 MiB	C++
JSX	100	0.091 s	0.31 MiB	C++
svideo	100	0.110 s	0.29 MiB	C++
ZXCVBNM_1	100	0.131 s	0.30 MiB	C++
Chenyao2333	100	0.164 s	0.33 MiB	C++
fyb	100	0.193 s	0.34 MiB	C++
slyrabbit	100	0.233 s	14.10 MiB	C++
Ra-xp	100	0.240 s	15.74 MiB	C++
槿柒	100	0.263 s	15.73 MiB	C++

本题关联比赛
20150420

关于超牛冠军赛的近10条评论(全部评论)
最大生成树 Hzoi_Go灬Fire 2016-10-15 06:17 9楼
养成开long long的好习惯 Magic_Sheep 2016-09-12 15:05 8楼
一個人的雨 2015-04-26 20:24 7楼
回复 @fyb : n=2000是时间复杂度O(410^7)还是可以承受的毕竟USACO2015 Feb的Silver题目做数据的人还是比较友好的吧 /时间明明都是在排序上吧*/ new ioer 2015-04-20 21:35 6楼
回复 @dsx : 哪的数据，为毛卡不掉kruskal…… fyb 2015-04-20 21:31 5楼
Prim是O(n^2)【不加heap优化。貌似玩脱会减速的样紫 Kruskal大概是O(n^2logn)【所以万年kruskal的不要说话了没T就是好事 new ioer 2015-04-20 21:29 4楼
谁出的数据……你出来……………………………………………………（我请你吃饭……） fyb 2015-04-20 21:23 3楼
一定是我写的姿势不对QAQ莫非得写 prim ? ztx 2015-04-20 19:26 2楼
`if(id[i]^id[mx]>f[i])` 的意思其实是 `if( (id[i]) ^ (id[mx]>f[i]) )` 。。。。。。 Orz AK爷wjx！！！！！Orzzzzzzzzzzzzzzzzzzzzz cstdio 2015-04-20 12:17 1楼

1941. 超牛冠军赛

★★ 输入文件：superbull.in 输出文件：superbull.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

贝茜和她的朋友们在每年的Superbull冠军赛玩hoofball，农民约翰负责组织比赛，要使比赛尽可能精彩。共有N（1≤N≤2000）队参加superbull比赛。每队分配1个不同的整数ID（范围在 1……2^30-1）以区分不同的球队。这个superbull的每一场比赛都是一个淘汰赛，农民约翰选择哪一队从superbull中被淘汰。这个superbull结束时，只剩下一个团队仍然存在。

农民约翰注意到比赛的得分有一个非常不寻常的特性！任何一场比赛，两支球队的综合得分总是以两队ID号按位异或（XOR）的值结束。

例如，如果两队的ID分别是12和20，那这场比赛的得分将是24点，即 01100 XOR 10100 = 11000。

农民约翰相信一场比赛的得分可以得更多的点，该比赛才更精彩。因此，他要选择一个合适的比赛序列，使superbull的总得分最大化。请帮助农民约翰组织比赛。

【输入格式】

第一行包含一个整数n

以下N行包含N组ID。

【输出格式】

输出一个的最大可能整数，superbull比赛中总的得分点数

【样例输入】

【样例输出】

【提示】

样例说明：

取得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。

注：按位异或运算，通常用^符号，它是对两个二进制整数的每一位按位执行逻辑异或运算。异或运算的规则是：只有在两个比较的位不同时其结果是1，否则结果为0

例如：10100（十进制的20）XOR

01100（十进制12）= 11000（十进制的24）

【来源】

在此键入。