当前位置: 代码迷 >> 综合 >> bzoj2460(xor线性基)
  详细解决方案

bzoj2460(xor线性基)

热度:39   发布时间:2024-01-04 12:43:32.0

 

拟阵证明,线性基性质,线性基中任意子集异或和不为0,所以从大到小加入就好

 

/************************************************************** 
Problem: 2460 
User: zhhx 
Language: C++ 
Result: Accepted 
Time:24 ms 
Memory:832 kb 
****************************************************************/
#include<cstdio> 
#include<cmath> 
#include<cstring> 
#include<algorithm> 
#include<cstdlib> 
using namespace std; 
typedef long long ll; 
int n; 
struct aa 
{ 
ll num;int val; 
}a[1005]; 
bool cmp(aa a,aa b) {return a.val>b.val;} 
ll b[65]; 
int main() 
{ 
scanf("%d",&n); 
for (int i=1;i<=n;i++) scanf("%lld%d",&a[i].num,&a[i].val); 
sort(a+1,a+n+1,cmp); 
int ans=0; 
for (int i=1;i<=n;i++) 
{   ll p=a[i].num; 
for (int j=63;j>=0;j--) if (p&(1ll<<j))  
{   if (b[j]) p^=b[j]; 
else {b[j]=p;ans+=a[i].val;break;} 
} 
} 
printf("%d",ans); 
return 0; 
}