ZigZagK的博客
[贪心+线性基]BZOJ2460(BeiJing2011)【元素】题解
2018年3月7日 19:35
BZOJ
查看标签

题目概述

有 $n$ 种无数个的物品,每种物品带有ZZK的蒟蒻值 $weak_i$ 和JZ的神犇值 $strong_i$ ,你现在可以选任意个物品,将得到所有物品神犇值之和的JZ神犇值。但是ZZK实在是太弱了,如果你选的物品中能够挑出一个非空真子集使得蒟蒻值异或和为 $0$ ,就会抵消所有JZ的神犇值!求你能得到最大的神犇值。

解题报告

选的物品中没有非空子集异或和为 $0$ 说明这是一组基,所以我们可以贪心,先把物品按照神犇值从大到小排序,然后能插入就插入就行了。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long long LL;
const int maxn=1000,Log=60;

int n,ans;LL M[Log+5];pair<int,LL> a[maxn+5];

inline bool cmp(pair<int,LL> a,pair<int,LL> b) {return a>b;}
inline bool Insert(LL x){
    for (int j=Log;~j;j--)
        if (x>>j&1) if (M[j]) x^=M[j]; else {M[j]=x;return true;}
    return false;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<=n;i++) scanf("%lld%d",&a[i].sc,&a[i].fr);
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++) if (Insert(a[i].sc)) ans+=a[i].fr;
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!