Superbull S题解
题目传送门(可点击)
题面
题目描述
\(Bessie\)和她的朋友们正在一年一度的\(Superbull\)锦标赛中打球，而\(Farmer\) \(John\)负责让比赛尽可能激动人心。总共有N支队伍（\(1 \le N \le 2000\)）参加了\(Superbull\)锦标赛。每个团队都有一个\(1...2^{30}−1\)的团队ID。
是一场淘汰赛，即在每场比赛之后，FJ选择淘汰其中一支球队，而被淘汰的球队再也无法参加任何比赛了。当只剩下一支球队时，比赛就结束了。
FJ注意到一个不寻常的事情：在任何游戏中，两个团队的总分是两个团队ID的按位异或（XOR）。例如，如果第\(12\)队和第\(20\)队将参加比赛，则该游戏的得分为\(24\)分，因为\(01100\) XOR \(10100=11000\)。
FJ想要设计一种比赛方案，让所有比赛的得分总和最大。请帮助\(Farmer\) \(John\)组织比赛。
输入格式：第一行包括一个整数N，下面N行每行包括一个队伍的ID。
输出格式：输出一个整数，代表比赛的最大总得分。
输入输出样例
输入 #1
4
3
6
9
10
输出 #1
37
样例解释：
让\(3\)队与\(9\)队进行比赛，并让\(9\)队晋级。然后他让\(6\)队和\(9\)队对决，让\(6\)队获胜。最后，第\(6\)队和第\(10\)队比赛，\(10\)队获胜。
总得分为：\(3\) XOR \(9+6\) XOR \(9+6\) XOR \(10=10+15+12=37\)。
题目描述
有\(n\)个球队，第\(i\)个球队与第\(j\)个球队产生的价值为\(i\)^\(j\)，每两个球队在创造了价值之后其中有一个球队就不能再创造价值了,求价值的最大值
思路
因为这道题目是在最小生成树的题单中，那么自然就需要向图论的方向思考了
可以将这道题目中的球队抽象为一个一个的节点，将两个球队创造的价值看为两个节点之间的边权
那么题目就变成了:
有\(n\)个节点，第\(i\)个节点与第\(j\)个节点的边权为\(i\) XOR \(j\)，每取了两个节点之间的边权，与其中一个节点有关的边都不能取了，求边权最大和
因为在最开始任意两个球队都可以打比赛，所以每个节点之间应该全部连接起来
所以，就可以将样例抽象成为一个图
代码实现其实也挺简单的，因为\(n \le 2000\)，所以直接暴力枚举所有的可能性就可以了
for(int i=1;i<=n;i++) //枚举端点
{
for(int j=i+1;j<=n;j++) //枚举另一个端点
{
a[++m].v=s[i]^s[j]; //储存边权
a[m].x=i; //储存一个端点
a[m].y=j; //储存另一个端点
}
}
继续分析，因为两个节点在取了边权后有一个节点就不能使用了
所以每一个节点一定只有一条或两条边与他相连，并且一定端头中的一个的节点只有一条边与之相连，那么就不可能形成环
举个栗子
在\(3\)队与\(9\)队比赛后就肯定有一个队会被淘汰，在这里就假设是\(3\)队，于是图就变成了这样：
接着\(6\)队又胜过了\(9\)队，接着\(10\)队胜过了\(6\)队，图就变成了这样：
如果这个图想产生环那么就必须让\(3\)与\(10\)这两个两侧的点连接
可是因为最后一个节点不论是战败还是胜利都不可能被大于两个节点连接，所以就不可能有环
因为所有的点一定是一个连通图并且没有环，那么这就是一棵树了
因为题目要求尽可能的让边权最大，所以需要完成的操作就是找出最大生成树
枚举可能性时间复杂度为\(O(\sum_{i=1}^{n} i)\)，下面的循环的时间复杂度就是\(O(\sum_{i=1}^{n}i \times h)\),大概就是 \(O(n^2)\)
AC Code
std版
#include <bits/stdc++.h> //code by 未抑郁的刘大狗
using namespace std;
#define int long long //不开 long long 见 10pts 高分
int n, fa[2020], m, s[2020], cnt, ans;
struct node {
int x, y, v; //分别储存两个节点与边权
} a[2020000];
bool cmp(node a, node b)
{
return a.v > b.v; //因为是最大生成树，所以以边权为关键字，从小到大排序
}
int find_root(int x) //找根
{
if (fa[x] == x) //没有爸爸就是根
return x;
return find_root(fa[x]); //有爸爸就找爸爸
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++) //输入
cin >> s[i];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
a[++m].v = s[i] ^ s[j]; //储存i与j之间的边的边权
a[m].x = i; //储存一个节点
a[m].y = j; //储存另一个节点
}
}
for (int i = 1; i <= 2010; i++) //将爸爸初始化
fa[i] = i;
sort(a + 1, a + 1 + m, cmp); //排序，为贪心做准备
for (int i = 1; i <= m; i++) {
int x = find_root(a[i].x), y = find_root(a[i].y); //找根
if (x != y) { //是不是已经连接
fa[x] = y; //连接
cnt++; //取了cnt个边
ans += a[i].v; //边权和为ans
}
if (cnt == n - 1) //如果已经取完了
break; //退出
}
cout << ans; //输出答案
return 0; //养成好习惯
}
copy版
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,fa[2020],m,s[2020],cnt,ans;
struct node{
int x,y,v;
}a[2020000];
bool cmp(node a,node b){
return a.v>b.v;
}int find_root(int x){
if(fa[x]==x)
return x;
return find_root(fa[x]);
}signed main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
a[++m].v=s[i]^s[j];
a[m].x=i;
a[m].y=j;
}
}for(int i=1;i<=2010;i++)
fa[i]=i;
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++){
int x=find_root(a[i].x),y=find_root(a[i].y);
if(x!=y){
fa[x]=y;
cnt++;
ans+=a[i].v;
}if(cnt==n-1)
break;
}cout<<ans;
return 0;
}