牛客假日团队赛1---Superbull

题目链接

链接：https://ac.nowcoder.com/acm/contest/918/G
来源：牛客网

题目描述
Bessie and her friends are playing hoofball in the annual Superbull championship, and Farmer John is in charge of making the tournament as exciting as possible. A total of N (1 <= N <= 2000) teams are playing in the Superbull. Each team is assigned a distinct integer team ID in the range 1…2^30-1 to distinguish it from the other teams. The Superbull is an elimination tournament – after every game, Farmer John chooses which team to eliminate from the Superbull, and the eliminated team can no longer play in any more games. The Superbull ends when only one team remains.

Farmer John notices a very unusual property about the scores in matches! In any game, the combined score of the two teams always ends up being the bitwise exclusive OR (XOR) of the two team IDs. For example, if teams 12 and 20 were to play, then 24 points would be scored in that game, since 01100 XOR 10100 = 11000.

Farmer John believes that the more points are scored in a game, the more exciting the game is. Because of this, he wants to choose a series of games to be played such that the total number of points scored in the Superbull is maximized. Please help Farmer John organize the matches.

输入描述:
The first line contains the single integer N. The following N lines contain the N team IDs.
输出描述:
Output the maximum possible number of points that can be scored in the Superbull.
示例1
输入
复制
4
3
6
9
10
输出
复制
37
说明
OUTPUT DETAILS: One way to achieve 37 is as follows: FJ matches teams 3 and 9, and decides that 9 wins, so teams 6, 9, and 10 are left in the tournament. He then matches teams 6 and 9, and lets team 6 win. Teams 6 and 10 are then left in the tournament. Finally, teams 6 and 10 face off, and team 10 wins. The total number of points scored is (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37.
备注:
NOTE: The bitwise exclusive OR operation, commonly denoted by the ^ symbol, is a bitwise operation that performs the logical exclusive OR operation on each position in two binary integers. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but is 0 if both bits are 0 or both are 1. For example: 10100 (decimal 20) XOR 01100 (decimal 12) = 11000 (decimal 24)

这道题我开始也是毫无思路的(就是太菜了)，然后也想过爆搜，但是大概算了一下，复杂度太高，然后也就放弃了。

其实这道题是一道 MST 的变形，最大生成树。

为什么呢？

1. 题目要求的是求最大的值。
2. 一共N只队伍，每次比赛淘汰一只队伍，也就是要比赛N-1次。
3. 每只队伍都要参与到比赛里面去

具体要怎么做呢？

我们最开始把N只队伍两两之间的异或和预处理出来，相当于预处理处，每一场比赛。每一场比赛就可以看成是一条连接这两只队伍的边。然后既然每只队伍都需要用到，所以我们对刚刚预处理出来的每场比赛进行最大生成树的建立。

时间复杂度：N * N * log(N) == 7e6 完全可以接受
空间复杂度：2010 * 2010 * 12/1024 == 47344K 也是可以接受的

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010;
ll n,cnt,a[N],f[N],res,tot;
struct node//最大生成树
{
    int u,v;
    ll w;
}t[N*N];
int cmp(node a,node b)
{
    return a.w>b.w;
}
ll find(ll x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
void kruskal()
{
    sort(t+1,t+tot+1,cmp);
    for(int i=1;i<=tot&&cnt<n-1;i++)
    {
        int fa=find(t[i].u);
        int fb=find(t[i].v);
        if(fa!=fb)
        {
            res+=t[i].w;
            cnt++;
            f[fa]=fb;
        }
    }
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)    for(int j=i+1;j<=n;j++)  t[++tot].u=i,t[tot].v=j,t[tot].w=a[i]^a[j];
    for(int i=1;i<=n;i++)    f[i]=i;
    kruskal();
    cout<<res<<endl;
    return 0;
}