线性基【p4570】 [BJWC2011]元素
2024-10-20 20:48:27
题目描述-->p4570 [BJWC2011]元素
题目大意
给定一些矿石的编号与价值,我们想要得到最大的价值和,并且选定物品的编号异或之和不为0.
分析
线性基就不多bb了,来这里->p3812 [模板]线性基
贪心
我们从小到大,选择价值大的矿石,满足异或之和不为零的条件,我们就可以加上它的贡献.
因此我们需要用到sort对价值从小到大排序.
线性基.
这题线性基有什么用?说实话开始我也没想到
我们很容易想到.
如果某个矿石能被使用,那它的编号的二进制下某一位一定是已经出现过的矿石编号中不存在的.(这句话还是仔细研读,应该不难理解,qwq.
这句话简单来讲.对于某一个编号x,我们检验其与之前已选编号时候异或起来为0.
(因为线性基进行插入元素的操作时,我们会对这个元素的大小进行削减是这么说吧.)
因此不难证明用线性基维护是正确的.
因此我们对已经选入的矿石的编号维护线性基.(那这题就裸了.
如果满足条件(异或之和不为0),我们就可以选择它,加上它的价值.
------------------代码-------------------
#include<bits/stdc++.h>
#define int long long
#define IL inline
#define RI register int
using namespace std;
int n,ans,p[64];
struct cod{int idx,w;}rock[1008];
IL bool ccp(const cod&a,const cod&b){return a.w>b.w;}
IL bool ins(int x)
{
for(RI i=63;i>=0;i--)
{
if(x&(1LL<<i))
{
if(p[i])
x^=p[i];//削减操作
else
{
p[i]=x;//如果之前选择的编号的当前一位不存在,而我的存在.
return true;//即能选择当前编号.
}
}
}
return false;
}
main()
{
ios::sync_with_stdio(false);
cin>>n;
for(RI i=1;i<=n;i++)
cin>>rock[i].idx>>rock[i].w;
stable_sort(rock+1,rock+n+1,ccp);
for(RI i=1;i<=n;i++)
if(ins(rock[i].idx))
ans+=rock[i].w;
cout<<ans;
}
最新文章
- windows命令——explorer
- NET实现微信公共平台上传下载多媒体文件(转)
- Huffman
- mysql数据库sql常用命令
- Hibernate 配置详解(7)
- Android中使用Handler以及CountDownTimer实现包含倒计时的闪屏页面
- C# 时间格式总结
- Java多线程高并发学习笔记——阻塞队列
- web离线应用--applicationCache
- 解决mariadb grant ERROR 1045 (28000): Access denied for user
- java 中的JDK封装的数据结构和算法解析(集合类)----链表 List 之 Vector (向量)
- 多个DbContext修改同一张表测试
- java 各种数据类型判断为空
- ubuntu14.04安装MATLAB R2017b步骤详解
- Angular2入门:TypeScript的类型 - 对象解构
- 『编程题全队』Scrum 冲刺博客
- JS结合a标签的使用
- MVC项目实践,在三层架构下实现SportsStore-11,使用Knockout实现增删改查
- javascript区域打印代码
- null,“”,empty的区别
热门文章
- javascript 数组的常用方法总结
- 【转载】Unity3D研究院之IOS触摸屏手势控制镜头旋转与缩放
- 一些优秀的SLAM博主
- CentOS下Apache虚拟主机配置
- UVa 1326 - Jurassic Remains(枚举子集+中途相遇法)
- C++ 11 智能指针 lamda 以及一个 围棋程序
- urlopen error [SSL: CERTIFICATE_VERIFY_FAILED] certificate verify failed解决办法
- Nginx主要模块常用指令说明
- [HNOI2015][bzoj4011] 落叶枫音 [拓扑DP]
- Snakes and Ladders LightOJ - 1151( 概率dp+高斯消元)