[USACO15FEB]Superbull 超级牛
题意概况
题目描述
\(Bessie\)和她的朋友们正在一年一度的\(Superbull\)锦标赛中打球,而\(Farmer John\)负责让比赛尽可能激动人心。
总共有 \(N\) 支队伍 \(1 \le N \le 2000\) 参加了\(Superbull\)锦标赛。每个团队都有一个 \(1 \dots 2^{30}-1\)的团队ID。
\(Superbull\)是一场淘汰赛 - 在每场比赛之后,\(FJ\)选择淘汰其中一支球队,而被淘汰的球队再也无法参加任何比赛了。当只剩下一支球队时,比赛就结束了。
\(FJ\)注意到一个不寻常的事情:在任何游戏中,两个团队的总分是两个团队ID的按位异或(XOR)。
例如,如果第 \(12\) 队和第 \(20\) 队将参加比赛,则该游戏的得分为 \(24\) 分,因为\({01100} \quad xor \quad {10100} = {11000}\)
FJ想要设计一种比赛方案,让所有比赛的得分总和最大。请帮助\(Farmer John\)组织比赛。
输入输出格式
输入格式:第一行包括一个整数 \(N\) ,下面 \(N\) 行每行包括一个队伍的ID。
输出格式:输出一个整数,代表比赛的最大总得分。
样例解释
让 \(3\) 队与 \(9\) 队进行比赛,并让 \(9\) 队晋级。
然后他让 \(6\) 队和 \(9\) 队对决,让\(6\)队获胜。
最后,第 \(6\) 队和第 \(10\) 队比赛,\(10\)队获胜。
总得分为:\(3 \quad xor \quad 9+6 \quad xor \quad 9+6 \quad xor \quad 10=10+15+12=37。\)
样例输入
4
3
6
9
10
样例输出
37
数据范围
\(1 \le N \le 2000\)
解题报告
题意理解
给定\(n\)个人,比\(n-1\)场比赛
对于一场比赛的精彩度是两个比赛队伍的编号异或
要求所有的比赛的精彩度之和最大.
算法解析
首先,这道题目难在建图上面.
我们可以分析一下,这道题目的比赛模式.
这就是一场竞赛的四场比赛的形式.
我们发现
- 一共比了\(n-1\)场比赛,有\(n\)个人,呈现,树形结构
- 对于一场比赛,谁赢谁输并没有什么影响.
- 我们要求这些边权最大,且只能有\(n-1\)条边
- 一条边的边权,是两点编号的异或.
综上所述,我们可以使用最小生成树的变形,最大生成树来求解本题.
代码解析
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N],n,m,cnt,fa[N];
struct node
{
int x,y,w;
} g[N*N];
int cmp(node a,node b)//最大排序
{
return a.w>b.w;
}
inline int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void kruskal()
{
for(int i=1; i<=n; i++)//建立图
for(int j=1; j<=n; j++)
if (i!=j)
g[++cnt]= {i,j,a[i]^a[j]};//边权为异或
sort(g+1,g+1+cnt,cmp);//kruskal排序
int cc=0;
long long ans=0ll;//记得开long long
for(int i=1; i<=cnt; i++)
{
int x=find(g[i].x),y=find(g[i].y);
if (x==y)//已经联合
continue;
fa[x]=y;
ans+=g[i].w;
if (cc==n-1)//n-1条边凑齐了
break;
}
printf("%lld\n",ans);
}
inline void init()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),fa[i]=i;
kruskal();
}
signed main()
{
init();
return 0;
}
最新文章
- 无需编译、快速生成 Vue 风格的文档网站
- ORACLE中的支持正则表达式的函数
- c# 后台弹出对话框 和前台弹出新页面
- Atitit.基于dsl的methodinvoker
- 浅谈ES6中的Proxy
- HDU 5834 [树形dp]
- 使用.net 的Chart控件绘制曲线图
- HDU 2493 Timer 数学(二分+积分)
- css 基础(一)
- CSS 之 光进入光
- Team City的安装1
- sql sever分组查询和连接查询
- Codeforces April Fools Contest 2017
- 记一次线上coredump事故
- InnoSetup 以命令行自动编译打包
- php 当前日期加一天和指定日期加一天
- sql语句中 “where 1=1” 的用处
- Linux centos修改防火墙为iptables
- C 函数——Day04
- Python报错IOError: [Errno 22] invalid mode ('r') or filename
热门文章
- CodeForces 1251A --- Broken Keyboard
- Leetcode之并查集专题-765. 情侣牵手(Couples Holding Hands)
- DC-1靶机
- shell学习笔记3-后台执行命令
- 【FFMPEG】【ARM-Linux开发】fmpeg安装第三方编码器(encoder)库,ffmpeg编码h264(完)
- 最新 智联java校招面经 (含整理过的面试题大全)
- fatal error C1189: #error : Building MFC application with /MD[d] (CRT dll version) requires MFC sha
- 利用Python进行数据分析_Numpy_基础_1
- python3 虚拟环境的创建
- golang数据基本数据类型和string类型的转换