【BZOJ2460】元素(拟阵)
2024-09-28 05:08:48
题意:给定n个物品,每个物品有属性x和价值y,要求从中选出一些使得价值和最大并且其中没有属性xor和为0的非空子集
n<=1000,x<=1e18,y<=1e4
思路:没有xor和为0的非空子集本来就是线性基的定义
拟阵,直接按价值排序之后贪心插入并维护线性基
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<ll,ll>P;
#define N 100010
#define M 1000000
#define INF 1e9
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1
#define fors(i) for(auto i:e[x]) if(i!=p) const int MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int dx[]={-,,,};
int dy[]={,,-,}; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} ll readll()
{
ll v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} struct node
{
ll x;
int y;
}a[N]; bool cmp(node a,node b)
{
return a.y>b.y;
} struct base
{
ll d[],p[];
int cnt; base()
{
mem(d,);
mem(p,);
cnt=;
} bool insert(ll x)
{
//if(x==0) return 0;
per(i,,)
if(x>>i&)
{
if(!d[i])
{
d[i]=x;
break;
}
x^=d[i];
}
return x>;
}
}T; int main()
{
int n=read();
rep(i,,n) scanf("%lld%d",&a[i].x,&a[i].y);
sort(a+,a+n+,cmp);
base T;
int ans=;
rep(i,,n) if(T.insert(a[i].x)) ans+=a[i].y;
printf("%d\n",ans);
return ;
}
最新文章
- T-sql语句查询执行顺序
- MySQL支持的数据类型(3)( 字符串)
- [Android Pro] Android 官方推荐 : DialogFragment 创建对话框
- 删除重复的字符(给一个字符串,删除连续重复的字符,要求时间复杂度为O(1)……)
- tmux简单使用指南
- eclispe输入@注解时提示所有注解的设置
- C#中通过调用Dll函数时,执行一段时间后,就会报内存可能被破坏的错的解决办法
- 字符编码终极笔记:ASCII、Unicode、UTF-8、UTF-16、UCS、BOM、Endian
- linux grep命令详解(转)
- 【luogu P1186】玛丽卡
- 【转】Java方向如何准备技术面试答案(汇总版)
- 2. Java面向对象之泛型-构造方法中使用
- 音乐出身的妹纸,零基础学习JAVA靠谱么
- python爬虫-上期所持仓排名数据爬取
- Python TVTK 标量数据可视化与矢量数据可视化,空间轮廓线可视化
- 【THUWC2017】随机二分图(动态规划)
- [POI2005]DWU-Double-row
- WebAPI接口安全校验
- npm cnpm +nodejs
- 全志A33 linux led驱动编程(附实测参考代码)