首页 > 代码库 > bzoj2460题解

bzoj2460题解

【题意分析】

  给你一个可重复数集,要求从中选取一个关于异或空间线性无关的子集,使子集的权值和最大。

【解题思路】

  定义:一个有序对(S,I)称为拟阵当且仅当该有序对满足以下性质:

1.有穷性:S是一个有限集。

2.遗传性:I是S的一类具有遗传性质的非空子集族。具体地说,∀B∈I,若A⊂B,则A∈I。

3.交换性:I满足交换性。具体地说,∀A,B∈I不妨设|A|<|B|,必定存在某一元素x∈B-A,使A∪{x}∈I。

 

  衍生概念:

独立子集:给定拟阵M=(S,I),A称为S的独立子集当且仅当A∈I。

可扩展元素:给定拟阵M=(S,I)与独立子集A∈I,若存在x∈S但x∉A,使得A∪{x}∈I,则称x为A的可扩展元素。

 

  我们可以构造关于可重数集S的一个有序对M=(S,I),S所有的线性基的集合为I,M满足拟阵的性质的证明如下:

1.有穷性:显然存在有限线性基的情况下S是有限的。

2.遗传性:显然一个线性基的任意独立子集都关于异或空间线性无关。(根据线性基定义可得)

3.交换性:

  求证:∀A,B∈I不妨设|A|<|B|,必定存在某一元素x∈B-A,使A∪{x}∈I。

  证明:

    我们假设∀A,B∈I不妨设|A|<|B|,∀x∈B-A,都有A∪{x}∉I。

    于是有B与A的差集包含于A的异或空间,又显然B与A的交集包含于A的异或空间,则B包含于A的异或空间。

    所以整个B的异或空间包含于A的异或空间,又A,B均线性无关,则有|A|>|B|,与前提|A|<|B|矛盾。命题得证。

 

  引理:带权拟阵的贪心算法正确性证明(懒得写了QAQ,戳这里)

  这样我们证明了权值和最大的线性基可以用贪心算法构造,所以按权值排序后贪心加入即可。复杂度O(n(log2n+log2∑numberi))。

【参考代码】

技术分享
 1 #include <algorithm> 2 #include <cstdio> 3 #include <functional> 4 #include <utility> 5 #define REP(i,low,high) for(register int i=(low);i<=(high);++i) 6 #define PER(i,high,low) for(register int i=(high);i>=(low);--i) 7 #define __function__(type) __attribute__((optimize("-O2"))) inline type 8 #define __procedure__ __attribute__((optimize("-O2"))) inline void 9 using namespace std;10 typedef pair<int,long long> PIL;11  12 static int n; long long base[64]; PIL a[1010];13  14 __function__(bool) push(const long long&n)15 {16     long long x=n; PER(i,63,0) if((x>>i)&1)17     {18         if(!base[i]) return base[i]=x,1; x^=base[i];19     }20     return 0;21 }22  23 int main()24 {25     scanf("%d",&n);26     REP(i,1,n) scanf("%lld%d",&a[i].second,&a[i].first);27     int ans=0; sort(a+1,a+n+1,greater<PIL>());28     REP(i,1,n) ans+=push(a[i].second)*a[i].first;29     return printf("%d\n",ans),0;30 }
View Code

 

bzoj2460题解