[luogu] P3812 【模板】线性基

前言

传送门 :

思路

目前 这是求异或最大值的模板, 具体线性基还有什么其他用处待开发

具体步骤 :

1. 从高位向低位扫每一个数 a [ i ] a[i] a[i] , 如果是 0 0 0则继续扫,否则如果当前线性基 p [ i ] p[i] p[i]不存在,那么就让这个数当 p [ i ] = x p[i] = x p[i]=x, 否则异或上当前的线性基
2. 怎么求最大值呢 ? 贪心的做法 , 我们从高到低位扫,如果异或之后比原来的大,那么就让他异或回去

MyCode

const int N  = 110;
ll a[N],p[N];
int n;
ll ans;

void xor_insert(ll x){
	for(int i = 55 ; i>= 0 ; i -- ){
		if(!(x >>i)){
			continue;
		}
		if(!p[i]){
			p[i] = x;
			break;
		}
		
		x ^= p[i];
	}
}
void solve()
{
	cin>>n;
	for(int i=1;i>a[i];
		xor_insert(a[i]);
	}
	
	for(int i = 55;i>=0;i -- ){
		if((ans^p[i]) > ans)
		ans ^= p[i];
	}
	cout