题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2460
题意：每块矿石有魔力和元素两个属性，选择总魔力和尽可能大的矿石，满足元素集合所有的异或和均不为 0
显然可以维护一个线性基判断一个矿石能不能选，然而怎么满足和最大呢？排序后贪心的想法是很容易得到的.... 然而正确性呢？大爷说需要拟阵相关姿势，先待学后来补吧 T.T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 10010 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct magic { ll num; int mag; }a[N]; bool cmp(magic a,magic b) {return a.mag>b.mag;} ll p[64],ans; bool flag; int n; void ins(ll x) { for(int i=63;i>=0;i--) if(x>>i&1) { if(!p[i]){p[i]=x;break;} else x^=p[i]; } if(x)flag=1; } int main() { n=read(); for(int i=1;i<=n;i++) a[i].num=read(),a[i].mag=read(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { flag=0; ins(a[i].num); if(flag)ans+=a[i].mag; } printf("%lld",ans); } |
Comments | NOTHING