题目名称	1941. [USACO Feb15 Gold] Superbull
输入输出	`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

关于 Superbull 的近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. [USACO Feb15 Gold] Superbull

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

【题目描述】

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

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

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

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

【输入格式】

第一行包含一个整数 $n$;

以下 $N$ 行包含 $N$ 组 $ID$。

【输出格式】

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

【样例输入】

【样例输出】

【样例说明】

$3\ XOR\ 9\ =\ 10$（淘汰 $3$）

$6\ XOR\ 9\ =\ 15$（淘汰 $9$）

$6\ XOR\ 10\ =\ 12$（淘汰 $6$）

总得分：$10\ +\ 15\ +\ 12\ =\ 37$

注：按位异或运算，通常用 ^ 符号，它是对两个二进制整数的每一位按位执行逻辑异或运算。

异或运算的规则是：只有两位不同时其结果是 $1$，否则结果为 $0$。

例如：

$10100$（十进制 $20$）$XOR$

$01100$（十进制 $12$）结果为：

$11000$（十进制 $24$）

【来源】

USACO