线性基(求抑或最值)

线性基：对一组数建立线性基得到：一组数a1,a2、、、an,其中ax：存最高位的1在第x位的元素值。

线性基作用：线性基的子集的抑或和的 值域与原数抑或和的值域相同。

性质1：线性基的任意子集的抑或和都不为0

构造线性基：

对原数组的每一个数p,从高位到低位扫描，找到第一位为1的，若该位上的线性基ai不存在，则ai=p,否则p=p^ai,继续扫描下一位。

像如果原数是2,3，则插入线性基中的是1,2 

ll b[63], nb[63], tot=0,flag=false; //b为线性基  nb用来求第K小异或值,基线性基中数 tot为nb元素个数,flag为true表示线性基外有数void insert(ll  x){ //插入for(int i = 62; i >= 0; i--) {if(x & (1ll << i)) {if(!b[i]){b[i] = x;return;}x ^= b[i];}}flag = true;
}

查询xor最大、小值：

ll Max(ll x) 
{  //求最大值ll res = x;for(int i = 62; i >= 0; i--) res = max(res, res ^ b[i]);return res;
}ll Min(ll x) 
{  //求最小值ll res = x;for(int i = 0; i <= 62; i++) if(b[i])res ^= b[i];return res;
}

验证一个数x能否被xor出

bool fin(ll x) 
{ //验证存在性if(x == 0 && b[0])return 1;for(int i = 62; i >= 1; i--) {int j = i - 1;if(x & (1 << j)) {x ^= b[i];if(!x)return 1;}}return 0;
}

求抑或第k大

把k二进制拆分，如果k的第i位上是1，ans^=b[i]

ll b[63], nb[63], tot=0,flag=false; //b为线性基  nb用来求第K小异或值,基线性基中数 tot为nb元素个数,flag为true表示线性基外有数void insert(ll  x){ //插入for(int i = 62; i >= 0; i--) {if(x & (1ll << i)) {if(!b[i]){b[i] = x;return;}x ^= b[i];}}flag = true;
}ll Rebuild() {  //第K大for(int i = 62; i >= 0; i--) {if(b[i] == 0)continue;for(int j = i - 1; j >= 0; j--) {if(b[j] == 0)continue;if(b[i] & (1ll << j))b[i] ^= b[j];}}for(int i = 0; i <= 62; i++) {if(b[i])nb[tot++] = b[i];}
}ll Kth_Max(ll k) {if(flag)k--; ll res = 0;if(k == 0)return 0;if(k >= (1ll << tot))return -1;for(int i = 62; i >= 0; i--) {if(k & (1ll << i))res ^= nb[i];}return res;
}

实例

A - 元素

theme：给定n个魔石的编号和魔力值，如果一堆魔石中有子串的抑或和为0，则这堆魔石没有魔力。问最多能达到多少魔力值？

solution：按魔力值排序，依次插入线性基，如果该元素可以插入，说明该数某一为1的位有价值，则该魔石被选。

#include
#define far(i,s,n) for(int i=s;ib.magic;}
}a[2000];void Insert(ll  x,int &flag){ //插入for(int i = 62; i >= 0; i--){if(x & (1ll << i)){if(!b[i]){flag = 1;b[i] = x;return;}x ^= b[i];}}
}int main()
{int n;cin>>n;far(i,0,n)scanf("%lld%lld",&a[i].num,&a[i].magic);sort(a,a+n);ll ans=0;far(i,0,n){int flag=0;Insert(a[i].num,flag);if(flag)ans+=a[i].magic;}cout<

#include
#define far(i,s,n) for(int i=s;i= 0; i--){if(x & (1ll << i)){if(!b[i]){b[i] = x;return;}x ^= b[i];}}flag = true;
}ll Rebuild() {  //第K大for(int i = 62; i >= 0; i--){if(b[i] == 0)continue;for(int j = i - 1; j >= 0; j--){if(b[j] == 0)continue;if(b[i] & (1ll << j))b[i] ^= b[j];}}for(int i = 0; i <= 62; i++){if(b[i])nb[tot++] = b[i];}
}ll Kth_Max(ll k) {if(flag)k--;ll res = 0;if(k == 0)return 0;if(k >= (1ll << tot))return -1;for(int i = 62; i >= 0; i--){if(k & (1ll << i))res ^= nb[i];}return res;
}int main()
{int t;cin>>t;for(int Case=1;Case<=t;++Case){printf("Case #%d:\n",Case);memset(b,0,sizeof(b));memset(nb,0,sizeof(nb));tot=0,flag=false;int n;scanf("%d",&n);far(i,0,n){ll x;scanf("%lld",&x);Insert(x);}Rebuild();int q;scanf("%d",&q);far(i,0,q){ll k;scanf("%lld",&k);ll ans=Kth_Max(k);printf("%lld\n",ans);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！