张家口网站建设费用南通网站建设开发

张家口网站建设费用,南通网站建设开发,网站诊断与检测,专业海外网站推广本篇将详细介绍基础的线性基模板 #xff08;文章非常详细#xff0c;把笔者学时的每一个问题都详细解答了#xff0c;如果感觉内容过于繁杂可以选择跳着看#xff09; 一#xff1a;线性基及有关概念 线性相关#xff1a;通俗讲#xff0c;一个量a和b线性相关#…本篇将详细介绍基础的线性基模板文章非常详细把笔者学时的每一个问题都详细解答了如果感觉内容过于繁杂可以选择跳着看一线性基及有关概念线性相关通俗讲一个量a和b线性相关则b一定可以表示为λ a线性无关即a和b非线性相关线性基维护一个极长线性无关基底假设我们要通过一些数彼此异或来表示[1,n]范围内的所有数我们维护的这些数就叫做线性基它的大小是严格log级别的。这里的线性相关:假设线性基是p一个数组数是x若x和p线性相关则x可以被p中某些元素彼此异或表示。比如现在线性基里的元素有1,2那么3一定不在线性基里因为31^2,3和线性基p线性相关所以不在里面二维护线性基即将一个元素插入线性基的插入操作。我们维护线性基时通常不把它看做一个数组而是把它内的所有数二进制分解一下看成一个矩阵比如线性基里的元素有1,2,5,我们直接把它看成一个矩阵二进制拆位我们如何表示一个线性基设线性基是p,假如x在线性基内设x的最高位1所在位数是i,那么p[i]x也就是把每个数存在最高位1所在位置而线性基中不可能出现两个数最高位1在同一位首先我们是这么构造的其次也有证明使用反证法设x和y是线性基的元素最高位1在第k位设zx^y,由于x,y最高位是k,所以zmin(x,y)假设z是p中某些元素pi彼此异或得到的结果那么这些pi和x,y线性相关这与线性基的定义彼此矛盾故假设不成立接着是插入操作我们把一个元素插入线性基中我们希望这个数能为线性基贡献一个新的基底但这个数不能和线性基p线性相关所以我们插入的数可能和原本的这个数不相同具体插入操作如下插入x,设当前遍历x的第i位1若x的第i位为0直接看下一位2若x的第i位是1那么1]:线性基p的第i位有值那么x^p[i]因为此时x和pi最高位1在同一位2]:线性基p的第i位没有值那么p[i]x,结束插入说明x找到了更低的最高位直接插入即可然后是查询最大值我们从高到低遍历线性基p,,假设当前答案是res如果res的第i位是1直接跳过因为pi的第i位也是1而异或完会使值变得更小因为损失了第i位就算后面的所有位都是1也不能弥补这一位变成0的损失如果res的第i位是0异或上pi同理因为得到这一位及时后面的位都损失了也是不亏的【模板】线性基代码如下#includebits/stdc.h using namespace std; #define int long long #define _for(i,a,b) for(int i a ; i b ; i ) #define for_(i,a,b) for(int i a ; i b ; i --) int n; const int maxn 5e2 10; int p[maxn]; int a[maxn]; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin n; _for(i , 1 , n) cin a[i]; _for(i , 1 , n){ int x a[i]; for_(j , 60 , 0){//插入线性基 if((x j) 1){//x第j位是1 if(p[j]) x ^ p[j];//p第j位有值 else {//p[j]没值 p[j] x;//插入 break; } } } } int x 0;//最大值 for_(i , 60 , 0) x max(x,x ^ p[i]); //其实是简略写法和文章中所说的没有区别 cout x; return 0; }本篇篇幅较小主要是方便新手入门下一篇是详细的线性基基础应用