(题目链接)

题意

　　n个二元组(a,b)，求一个∑b最大，且所有子集XOR<>0的集合

Solution

　　线性基的经典应用。具体证明好像要用到拟阵，不会，好像是很高深的东西。

代码

// bzoj2460#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #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;}