【BZOJ2460】【BJOI2011】元素 [线性基]
元素
Time Limit: 20 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
相传,在远古时期,位于西方大陆的 Magic Land 上,人们已经掌握了用魔法矿石炼制法杖的技术。
那时人们就认识到,一个法杖的法力取决于使用的矿石。
一般地,矿石越多则法力越强,但物极必反:有时,人们为了获取更强的法力而使用了很多矿石,却在炼制过程中发现魔法矿石全部消失了,从而无法炼制出法杖,这个现象被称为“魔法抵消”。
特别地,如果在炼制过程中使用超过一块同一种矿石,那么一定会发生“魔法抵消”。
后来,随着人们认知水平的提高,这个现象得到了很好的解释。
经过了大量的实验后,著名法师 Dmitri 发现:如果给现在发现的每一种矿石进行合理的编号(编号为正整数,称为该矿石的元素序号),那么,一个矿石组合会产生“魔法抵消”当且仅当存在一个非空子集,那些矿石的元素序号按位异或起来为零。
并且人们有了测定魔力的有效途径,已经知道了:合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值,并且通过实验推算出每一种矿石的元素序号。
现在,给定你以上的矿石信息,请你来计算一下当时可以炼制出的法杖最多有多大的魔力。
Input
第一行包含一个正整数N,表示矿石的种类数。
接下来 N行,每行两个正整数Numberi 和 Magici,表示这种矿石的元素序号和魔力值。
Output
仅有一行,一个整数:最大的魔力值
Sample Input
1 10
2 20
3 30
Sample Output
由于有“魔法抵消”这一事实,每一种矿石最多使用一块。
如果使用全部三种矿石,由于三者的元素序号异或起来:1 xor 2 xor 3 = 0 ,
则会发生魔法抵消,得不到法杖。
可以发现,最佳方案是选择后两种矿石,法力为 20+30=50。
HINT
对于全部的数据:N ≤ 1000,Numberi ≤ 10^18,Magici ≤ 10^4。
Main idea
给出若干元素带两个属性a,b,求出添加若干个元素使得b最大(可加入的条件是加入的任意元素(不限制个数)XOR起来不为0)。
Solution
考虑贪心,从最大到最小加入肯定最优,发现线性基的性质内含“无法表示出0”,所以可以使用线性基处理。(线性基是可以用内部元素XOR出来答案和原来的相当的结构)。
加入方式:判断i的这一位是否为1,如果为1,判断线性基中这一位是否已经有匹配元,如果没有则将i当做这一位的匹配元,停止判断,Ans+=b[i]。
Code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std; const int ONE=; int n;
int len=;
long long Link[];
int Ans; struct power
{
long long a;
int b;
}a[ONE]; bool cmp(const power &a,const power &b)
{
return a.b>b.b;
} int get()
{
int res,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} int main()
{
n=get(); for(int i=;i<=n;i++)
{
scanf("%lld",&a[i].a);
a[i].b=get();
} sort(a+,a+n+,cmp); for(int i=;i<=n;i++)
{
for(int pos=len;pos>=;pos--)
{
if( ((a[i].a>>(pos-))&) )
{
if(!Link[pos])
{
Link[pos]=a[i].a;
Ans+=a[i].b;
break;
}
else a[i].a^=Link[pos];
}
}
} printf("%d",Ans);
}
最新文章
- [嵌入式开发]Linux性能分析——上下文切换
- idea key
- Java2_J2EE体系架构
- 搜索 录音功能 Android api
- SQL Server 2012 管理新特性:AlwaysOn【转】
- Bulb Switcher
- java.io.IOException: Messenger was closed
- 《Linux内核修炼之道》 之 高效学习Linux内核
- 使用grunt压缩css是能否设置background-size不压缩进去呢?否则ie8不能识别
- [jstl] forEach标签使用
- HTML5学习笔记简明版 目录索引
- Elastic Stack之kibana入门
- JVM(二)—— 类加载机制
- Android 去除应用标题栏(Android Studio)
- CF875F Royal Questions
- 什么是可哈希的(hashable)
- go 内嵌对象类型
- mysqli
- 360 奇酷行车记录仪12967p 安霸a7
- 如何利用JConsole观察分析Java程序的运行并进行排错调优_java
热门文章
- 通过py2exe打包python程序的过程中,解决的一系列问题
- .NET基础知识之八&mdash;&mdash;深拷贝,浅拷贝
- Java的HashMap和HashTable
- js滚动及可视区域的相关的操作
- CentOS 7 安装Nginx并实现域名转发
- 【紫书】(UVa1347)Tour
- python正则-字符串处理,主要用于处理请求参数格式为application/x-www-form-urlencoded的表单数据
- 【转】用ASP.NET Core 2.1 建立规范的 REST API -- 缓存和并发
- 11-Mysql数据库----单表查询
- CSP201512-1: 数位之和