线性基

题目传送门

简单的线性基应用。

把所有矿石按照法力大小sort一下，然后根据元素序号搞线性基就好了。

代码：

#include<cstdio> #include<cstring> #include<algorithm> #define N 1005 using namespace std; typedef long long LL; struct nd{ LL x,id; }a[N]; int n,ans; LL p[65]; bool cmp(nd a,nd b){ return a.x>b.x; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld%lld",&a[i].id,&a[i].x); sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++){ for (int j=64;~j;j--) if ((a[i].id>>j)&1) if (!p[j]) { p[j]=a[i].id; break; } else a[i].id^=p[j]; if (a[i].id) ans+=a[i].x; } return printf("%d\n",ans),0; }