题意:给定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 ;
}

最新文章

  1. T-sql语句查询执行顺序
  2. MySQL支持的数据类型(3)( 字符串)
  3. [Android Pro] Android 官方推荐 : DialogFragment 创建对话框
  4. 删除重复的字符(给一个字符串,删除连续重复的字符,要求时间复杂度为O(1)……)
  5. tmux简单使用指南
  6. eclispe输入@注解时提示所有注解的设置
  7. C#中通过调用Dll函数时,执行一段时间后,就会报内存可能被破坏的错的解决办法
  8. 字符编码终极笔记:ASCII、Unicode、UTF-8、UTF-16、UCS、BOM、Endian
  9. linux grep命令详解(转)
  10. 【luogu P1186】玛丽卡
  11. 【转】Java方向如何准备技术面试答案(汇总版)
  12. 2. Java面向对象之泛型-构造方法中使用
  13. 音乐出身的妹纸,零基础学习JAVA靠谱么
  14. python爬虫-上期所持仓排名数据爬取
  15. Python TVTK 标量数据可视化与矢量数据可视化,空间轮廓线可视化
  16. 【THUWC2017】随机二分图(动态规划)
  17. [POI2005]DWU-Double-row
  18. WebAPI接口安全校验
  19. npm cnpm +nodejs
  20. 全志A33 linux led驱动编程(附实测参考代码)

热门文章

  1. java日常统计
  2. EFI系统分区如何删除
  3. linux 正则表达式 目录
  4. Dubbo原理学习
  5. 关于golang的label
  6. 循环结构 :for
  7. Codeforces 1262E Arson In Berland Forest(二维前缀和+二维差分+二分)
  8. idea配置less自动编译
  9. Python链表倒置的两种方法
  10. Ubantu上安装Redis