首页 > 代码库 > 【bzoj2460】 BeiJing2011—元素
【bzoj2460】 BeiJing2011—元素
www.lydsy.com/JudgeOnline/problem.php?id=2460 (题目链接)
题意:n个二元组(a,b),求一个∑b最大,且所有子集XOR<>0的集合
Solution
线性基的经典应用。具体证明好像要用到拟阵,不会,好像是很高深的东西。
代码:
// bzoj2460#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=1010;struct data {LL num;int x;}a[maxn];LL bin[65];int n,b[65];bool cmp(data a,data b) { return a.x>b.x;}int main() { bin[0]=1;for (int i=1;i<=60;i++) bin[i]=bin[i-1]<<1; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld%d",&a[i].num,&a[i].x); sort(a+1,a+1+n,cmp); int ans=0; for (int i=1;i<=n;i++) { for (int j=60;j>=0;j--) if (a[i].num&bin[j]) { if (!b[j]) {b[j]=i;break;} else a[i].num^=a[b[j]].num; } if (a[i].num) ans+=a[i].x; } printf("%d\n",ans); return 0;}
【bzoj2460】 BeiJing2011—元素
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。