题意

给定n个物品,每个物品有一个编号和价值,问如何取使得拿到的物品价值总和最大,并且取得物品的编号的子集异或和不能为0。

思路

这是个贪心,我们先按照价值从大到小排序,然后贪心地取,如果当前要取的物品的编号和之前取的存在异或为0的情况,我们就丢弃这个物品,否则加入。判断异或为0可以用线性基来做。
具体证明参考

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4) #include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c); const ll oo = 1ll<<;
const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;} /*-----------------------showtime----------------------*/
const int maxn = ;
struct node{
ll id;
int val;
}a[maxn];
bool cmp(node a,node b){
return a.val > b.val;
}
ll p[];
bool check(ll x){
for(int i=; i>=; i--) {
if((x & (1ll << i) ) > )
{
if(p[i] >-) x ^= p[i];
else {
p[i] = x;
return true;
}
}
}
return false;
} int main(){
memset(p, -, sizeof(p));
int n; scanf("%d", &n);
for(int i=; i<=n; i++) {
scanf("%lld%d", &a[i].id, &a[i].val);
}
sort(a+, a++n,cmp);
int sum = ;
for(int i=; i<=n; i++) {
if(check(a[i].id)) sum += a[i].val;
}
printf("%d\n", sum); return ;
}

最新文章

  1. wk_01
  2. jQuery简单实现iframe的高度根据页面内容自适应的方法
  3. Html5 学习系列(五)Canvas绘图API快速入门(2)
  4. 升级了win10后开启wifi热点出现iphone&amp;macbook连接断线的问题(win7也一样)
  5. C++Primer 第十九章
  6. Notepad++ Emmet安装方法教程
  7. magic_quotes_runtime 与 magic_quotes_gpc
  8. 51nod1125 交换机器的最小代价
  9. 创建ID3D11Device可能会遇到的问题,不能使用具体的IDXGIAdapter
  10. 让用户打开你app的位置功能
  11. BZOJ 1927: [Sdoi2010]星际竞速 费用流
  12. java中抽象类与接口的区别
  13. bzoj 4031: [HEOI2015]小Z的房间 轮廓线dp
  14. Python中几种数据结构的整理,列表、字典、元组、集合
  15. github修改自己的昵称
  16. Csharp 高级编程 C7.1.2
  17. jQuery 遍历 – 祖先
  18. RxJava(七) 使用debounce操作符 优化app搜索功能
  19. Linux创建用户与权限赋值
  20. 解决悬浮的&lt;header&gt;、&lt;footer&gt;遮挡内容的处理技巧

热门文章

  1. some (1)
  2. 【MySQL】Unknown column &#39;column_name&#39; in &#39;field list&#39;
  3. React Hooks 深入系列 —— 设计模式
  4. win10家庭版打开组策略
  5. Java性能权威指南读书笔记--之一
  6. ABP实现EF执行SQL(增删改查)解决方案
  7. java代码之美(13)--- Predicate详解
  8. Java源码之ConcurrentHashMap
  9. 天天都用消息队列,却不知道为啥要用MQ,这就有点尴尬了
  10. hadoop2.7之作业提交详解(下)