首页 > 代码库 > 【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—元素