sup-extra 线性基及部分例题
1.先来讲讲什么是线性基吧
线性基是专门用来处理异或相关问题的一个数的集合，把原先的数的集合中挑出一部分数，利用这些挑出来的数进行相互的异或运算就能得到原先的数。不过实际上这些数能够组合出的数字会比原集合的数字相等或更多，基于这个方面的原因，只有当不考虑集合本来的数而只考虑异或结果的时候会用到线性基。
2.原理
那么具体的原理是怎么个原理呢？考虑一下二进制数的性质，当一个数组中存储n个高位均不相同的数字的时候，能够通过异或得到多少个数呢？答案很明显是2n，因为显然一个有k位的数只能影响从小到大k位，所以从高位往低位遍历的时候，针对一个数选与不选肯定会得到两个不同的结果，所以最大为64位的数的集合，我们构造线性基的时候只需要选出64个不同的数字就好。
当然光是讲一下构造的原理并不能实际解决问题。针对具体的问题就结合题目来看吧。
3.例题及代码
求异或最大值 bzoj 2460
题意：给你n个石头的编号和权值，让你求出在石头编号异或值最大的情况下能得到的权值。很明显就是要求编号的异或最大值。
代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
struct mine{
LL num;
LL val;
}ori[maxn];
bool comp(mine a,mine b){
return a.val>b.val;
}
LL lis[70];
bool havezero;
void init(){
memset(lis,0,sizeof(lis));
havezero=false;
}
bool build(LL x){
for(int i=62;i>=0;--i){
if(x&(1ll<<i)){
if(lis[i])
x^=lis[i];
else {lis[i]=x;return true;}
}
}
havezero=true;
return false;
}
int main(void)
{
int n;
while(~scanf("%d",&n)){
init();
for(int i=0;i<n;++i){
scanf("%lld%lld",&ori[i].num,&ori[i].val);
}
sort(ori,ori+n,comp);
LL res=0;
for(int i=0;i<n;++i){
res+=ori[i].val;
if(build(ori[i].num)==false){
res-=ori[i].val;
}
}
printf("%lld\n",res);
}
return 0;
}
求异或第k小 hdu 3949
版题就不谈思路了，第k小求的时候要首先重新处理线性基，使得每位数字都是最小的，这样能够提供的贡献就是2m，然后就可以得到第k小了。
代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
const LL INFL=0x3f3f3f3f3f3f3f3f;
int t,n,q,coun;
LL lis[70],sml[70];
bool havezero;
void init(){
memset(lis,0,sizeof(lis));
havezero=false;
}
bool build(LL x){
for(int i=62;i>=0;--i){
if(x&(1ll<<i)){
if(lis[i]) x^=lis[i];
else {
lis[i]=x;
return true;
}
}
}
havezero=true;
return false;
}
bool rebuild(){
coun=0;
for(int i=62;i>=1;--i){//i=0的时候必定为1，不用往下异或了
if(lis[i]){
for(int j=i-1;j>=0;--j){
if(lis[i]&(1ll<<j)){//保证有减小
lis[i]^=lis[j];
}
}
}
}//由于线性基性质+每次只改变后面j位,所以扫一遍就够了
for(int i=0;i<=62;++i){
if(lis[i])
sml[coun++]=lis[i];
}
}
LL ksmall(int k){
if(havezero) --k;
LL res=0;
if(k>=(1ll<<coun)) return -1;
for(int i=coun;i>=0;--i){
if(k&(1ll<<i))
res^=sml[i];
}
return res;
}
int main(void)
{
scanf("%d",&t);
for(int mark=1;mark<=t;++mark){
scanf("%d",&n);
LL mid;
init();
for(int i=0;i<n;++i){
scanf("%lld",&mid);
build(mid);
}
rebuild();
scanf("%d",&q);
printf("Case #%d:\n",mark);
for(int i=0;i<q;++i){
scanf("%lld",&mid);
printf("%lld\n",ksmall(mid));
}
}
return 0;
}
xor bzoj 2115
题意：要你找出一条从1到n的路径，使得路径上的权值异或和最大。
则实际上就是任求一条1到n的路径然后再去得到每个环所能提供的权值，因为走到环里转一圈再回到1点的时候得到的权值就是环的异或和。同时如果有多条到n的路径，则他们之间也能构成环，在跟起始选择的一条进行各种异或后肯定能得到最长的。
代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
struct edge{
int to,num;
LL val;
edge(int t,LL v,int n):to(t),val(v),num(n){}
edge(){}
};
vector<edge> tree[maxn];
int n,m,tot;
LL dis[maxn],circle[maxn*3];
bool vis[maxn];
void addedge(int u,int v,LL val,int num){
tree[u].push_back(edge(v,val,num));
tree[v].push_back(edge(u,val,num));
}
void dfs(int u,int fa){
vis[u]=true;
for(int i=0;i<tree[u].size();++i){
int v=tree[u][i].to,num=tree[u][i].num;
LL val=tree[u][i].val;
if(num!=fa){
if(!vis[v]){
dis[v]=dis[u]^val;
dfs(v,num);
}
else{
circle[++tot]=dis[u]^dis[v]^val;
}
}
}
}
LL xmxyji[64];
bool xmxyji_insert(LL k){
for(int i=63;i>=0;--i){
if(k&(1ll<<i)){
if(!xmxyji[i]){
xmxyji[i]=k;
return true;
}
else{
k^=xmxyji[i];
}
}
}
return false;
}
LL getres(){
LL res=dis[n];
for(int i=63;i>=0;--i){
if((res^xmxyji[i])>res)
res^=xmxyji[i];
}
return res;
}
int main(void)
{
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;++i){
tree[i].clear();
}
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
int a,b;
LL c;
tot=0;
for(int i=1;i<=m;++i){
scanf("%d%d%lld",&a,&b,&c);
addedge(a,b,c,i);
}
dfs(1,0);
memset(xmxyji,0, sizeof(xmxyji));
for(int i=1;i<=tot;++i)
xmxyji_insert(circle[i]);
LL res=getres();
printf("%lld\n",res);
}
return 0;
}
XOR UVALive-8512
这个题要求区间异或最值，实际上对于每个插入的数字，我们都做一个线性基，并且记录每个数字是第几位的。当有更靠前的数字插入进来时优先替换旧的，这样在求l r区间上的结果时就可以直接遍历r的线性基，把其中位置在l-1及之后的点都抛弃掉。这样就能直接得到结果了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
LL xmxyji[maxn][64];
int posi[maxn][64];
LL k_seperate[64],tot,n,q,k;
void build(int num,LL val){
for(int i=0;i<tot;++i){
if(val&k_seperate[i]){
val-=k_seperate[i];
}
}
for(int i=0;i<64;++i){
xmxyji[num][i]=xmxyji[num-1][i];
posi[num][i]=posi[num-1][i];
}
int nown=num;
for(int i=63;i>=0;--i){
if(val&(1<<i))
if(xmxyji[num][i]){
if(posi[num][i]<nown){
swap(xmxyji[num][i],val);
swap(posi[num][i],nown);
}
val^=xmxyji[num][i];
}
else{
xmxyji[num][i]=val;
posi[num][i]=nown;
return;
}
}
}
LL query(int l,int r){
LL res=0;
for(int i=63;i>=0;--i){
if(posi[r][i]>=l){
if((xmxyji[r][i]^res)>res){
res^=xmxyji[r][i];
}
}
}
return res|k;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld",&n,&q,&k);
tot=0;
LL tmp=k;
while(tmp){
k_seperate[tot++]=tmp&(-tmp);
tmp-=tmp&(-tmp);
}
memset(xmxyji,0,sizeof(xmxyji));
memset(posi,0,sizeof(posi));
for(int i=1;i<=n;++i){
scanf("%lld",&tmp);
build(i,tmp);
}
for(int i=0;i<q;++i){
int a,b;
scanf("%d%d",&a,&b);
printf("%lld\n",query(a,b));
}
}
return 0;
}