题目描述

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)

解答

给定一个集合s内的n个数，

进行一种操作：

从集合内选出两个数进行异或（xor），异或的值计入贡献，并且将两个数中的一个数从集合中删去。

重复N−1次此操作，直到集合内只剩下最后一个数。

求最大贡献值。

数据范围：(1<=N<=2000)

首先我们不妨猜想一下贪心思路

选前N−1大的异或和作为答案

很可惜，这是错误的，因为没有考虑不可行情况

什么是不可行情况？

我们假设集合里有{a,b,c,d} ，a xor b ，b xor c ，a xor c 是前N−1 大值

我们并不能选这三个组数作为答案

因为如果我们选a,b 删a 

那么a,c 是不可能选到的

反之亦然

也就是说如果删除的某些二元组构成了环，那么这个方法不可行

N 个点没有环又有N−1 条边，显而易见是生成树，为了保证答案最大，只需要连边跑最大生成树即可

我们可以将每个数编号1→N ，结点两两连一条 边权为【两数异或值】的边

然后对得到的图跑一遍Kruskal 或者Prim 即可。

最后请注意，数据范围较大，需要开long long  

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAXN 2023 using namespace std; struct qwq { int u,v,w;
}e[4000023]; int w[MAXN]; int tot=0; int f[MAXN]; int find(int x) { if (f[x]==x) return x; return f[x]=find(f[x]);
} bool cmp(const qwq x,const qwq y) { return x.w>y.w;
} int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++)
    { scanf("%d",&w[i]);
    } for (int i=1;i<=n;i++)
    {
        f[i]=i;
    } int xx,yy; for (int i=1;i<n;i++)
    { for (int j=i+1;j<=n;j++)
        {
            e[++tot]=(qwq){ i,j,(w[i] xor w[j]) };
        }
    } long long ans=0;
    sort(e+1,e+tot+1,cmp); for (int i=1;i<=tot;i++)
    {
        xx=find(e[i].u); yy=find(e[i].v); if (xx!=yy)
        {
            ans+=e[i].w;
            f[xx]=yy;
        }
    } printf("%lld",ans); return 0;
}

来源：千柒/Kan_kiz