线性基是线性空间在概念上的拓展。线性空间指的是 向量在加法和数乘上是运算封闭的。
线性空间 是由向量生成的。而整个线性空间的最大线性无关子集叫做整个线性空间的基。
定理 线性空间的基 的数量是一定的。证明一下吧 这个是必要的，设a1,a2,a3...ak是整个线性空间的基底。若存在 af使得af加入此线性空间后an,am将会被去掉。那么必然有 对于任意的bn*an+bm*am==af*bf 这是必然的如果af要取代他们必然要和他们产生的效果相同。
观察 bn*an+bm*am这个东西组成的线性空间 因为他们是属于一个线性空间的基底的 故在线性空间的表示上必然是一个平面 而af*bf是一条线 如果他们两个在任意情况下都是一条线的话 显然他们是线性相关的故假设不成立所以af是不可能取代an am取代更多的可以用上述向量的张成空间来解释。证毕。
放上一道题更容易理解证明其他的东西。
LINK： JLOI装备购买
本题让我们求 对于一些多维向量 求出其最小代价的基底。考虑做法：题目中想买更多的装备显然是不存在的 因为由上述定理可知一个线性空间的基底大小是固定的。
求线性空间的一组基底 考虑高斯消元。求最小的代价 考虑贪心的选取最小的代价的向量来加入我们的基底中。
此题是我写的方式有点问题么 精度为1e8 60ponits 1e6 90points 1e4 AC。
我的 GAUSS 的其他题解中写的不太一样... 我觉得我这样也是正确的。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define EPS 1e-4 using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=510; int n,m,cnt,ans; int flag[MAXN],vis[MAXN]; struct wy { db a[MAXN]; int v; int friend operator <(wy x,wy y) { return x.v<y.v; } }t[MAXN]; inline void GAUSS() { for(int j=1;j<=m;++j)//枚举第i个系数 { for(int i=1;i<=n;++i) { if(vis[i])continue; if(fabs(t[i].a[j])>EPS) { if(!flag[j]) { flag[j]=i;vis[i]=1; ++cnt;ans+=t[i].v; continue; } else { db w=t[i].a[j]/t[flag[j]].a[j]; t[i].a[j]=0; for(int k=j+1;k<=m;++k) t[i].a[k]-=t[flag[j]].a[k]*w; } } } } } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) t[i].a[j]=read(); for(int i=1;i<=n;++i)t[i].v=read(); sort(t+1,t+1+n); GAUSS(); printf("%d %d ",cnt,ans); return 0; }
关于本题 贪心的正确性 是否存在一个向量的加入顶掉两个及两个以上的向量 显然如果可以 那么这两个向量也是线性相关的（上述定理） 故两个也会排斥不存在这种情况。
所以 从小到大的加入 是正确的 因为 向量之间只有不存在一个优秀的组合 一个更小的向量加入其中会拆散这个组合 反而会变得更加的优秀。
现在研究一下 线性基 也叫作 异或空间的一组基底 当然 异或空间是对异或运算的封闭空间。对于一组基底来说 显然的是p1*a1^p2*a2^p3*a3...可以组成这个集合中的任何数字 当然这个p是0,1的随机函数。
注意 我们这线性基是体现在一维层面的也是很容易证明一个数字不能取代两个数字的 a1^a2^a3...^ak注意此时 p数组被我们去掉了为0的都丢掉了 因为我们此时是一个 方程Y a1^a2^a3...^ak==af;
设 af==an^am; 注意此时af a1 a2 都不等于0 0是无法加入我们的线性基当中的 因为考虑当p函数都取0的时候 0是可以把这些东西都给表示出来的。
pf*af==pn*an^pm*am; 当pn取0的时候显然有 af=an 当 pm取0的时候显然有 af=am; 那么此时很显然了 如果an==am an和am是线性相关组 否则不存在一个数同时等于两个不同的数字 故一个af最多只能代替一个数字。
上述情况都是 和a1 a2 a3...ak这些数字是由脱节的 比较显然的是 如果af能够取代的话 那么带来的影响和 an*pn am*pm 这个等式的效果相同 所以有上述等式 。（其中p是0 1 之间的函数。
考虑如何构建 一个序列的线性基。我们 选出任意一些数字使得 这些数字异或出来可以 张成整个线性空间 。
考虑线性基的替换关系 是否存在一个非线性基的元素直接替换线性基元素。由 p1*a1^p2*a2^p3^a3...pn^an==af（1）这种情况来说 必然有 p1^a1*p2^a2*p3^a3...pn*an^pf*af==pm^am;（异或满足交换律）
此时是否可以看成 af完全替代am成为线性基的一员呢，am被踢了...(我也是经常被踢的 还是皮一点好.../cy
这能说明什么呢？我所知道的是 当（1）式中pm为0的时候显然替换不了，如果不为0呢考虑原式 如果pm为0的时候我们pf也为0 在这种程度上代替了 am 考虑pm不为0的时候 当我们要拼出一个数字ak的时候一个比较显然的想法是 如果是原来的线性基是可以异或出来的但对于现在的 去掉am加入af 是否可行了，不妨来构造一波。a1^a2^a3...a^n^af==ak; ...此时pf不为0 因为我们在论证这种情况 考虑去掉其 加入 am怎么凑出ak 。显然有凑出am的式子和ak的式子取交交集定义为A集 凑出am的式子叫做B集。
我们把am加上 把A集关于B集的补集也加上这样连带ak原本的式子 也就是原本的式子+A集关于B的集的补集==ak 好啊 对于一般的式子我们证明出来了在pm不为0的时候af成功替换掉了af 那么对于所有的这种情况我们定义af都可取代线性基中的元素。
但是还是考虑到一个元素不可能同时取代线性基中的两个元素 所以 线性基中的元素个数还是不变的...
关于构造线性基的代码 我们可以将其抽象成解异或方程组的样子。注意异或空间也是有维度的每个二进制位单独算一个维度 这和线性空间不尽相同。
const int MAXN=100010; int a[MAXN]; int f[60],cnt; inline void structure(int x) { for(int i=60;i>=0;--i) { if(x&(1<<i)) { if(!f[i]) { ++cnt;f[i]=x; break; } else x^=f[i]; } } }
当然 看似很简单 我却琢磨了很久很久很久... 考虑为什么最后形成的线性基可以把所有数字都拼出 那是因为线性基中每个元素在插入的时候都解了一遍方程组...
看看能否将其变成0 这样的话就说明线性基不需要其 如果变不成0 那么他本身就要被加入到线性基当中。
引理：一个线性基中的元素个数不可能大于这个线性基的最大维度。(我是不会告诉你我写出的定理都是我自己想出来的...正确性还是很不错的 请继续看下去...一个蒟蒻的自学历程.
证明它很容易吧 因为如果大于了这个线性基的最大维度了 也就是说利用鸽巢原理必然有一个维度有多于1个数字的情况 考虑如何把其中之一踢出来...
按照刚才插入线性基的方式 就显然可以得出 一定可以将其异或成0 因为从大到小的考虑异或其当前这维的另一个数字设当前这维为k那么k及k位之前的都为0 往后一直不断异或下去 得到的之前得到的数字位一定全部为0 因为我们构造线性基的时候就创造了 对于基底的任意的一个维度W的数字 其前W之前的维度全部为0 那么到最后的0这个维度呢必然只有它一个元素为1这样按照这样不断异或前面的位数上的数字不断为0的一直进行下去 到达最后一位一定是0或1 那么是1再异或一下就为0了。这是非常一般的情况...我们成功证明了上述定理。写到这里做一个线性基刚入门的初学者也不禁热血沸腾了感觉发现了世界的奥秘...可能有人说线性基中存的数字不是原始的序列中的数字也可以拿来直接使用么，这我也想到了 是这样的线性基在插入的时候是不断异或其他的数字最终插入的考虑线性基的数字就是由整个序列构成的 更一般的对于af我们说他被线性基中的线性方程构出但是指出构出其的不是原序列上的数字怎么才能解释呢？
注意到了这里 就不单单是学习知识点了我认为问题的提出比自己去学习网上的定理更加的有效...解释：我们把组成af的线性方程写出来 考虑线性基的数字也是有原序列构成的我们把线性基中的数字用原序列中的数字来表示一定可以表示，这个时候发现了什么 这个方程由af和原序列中的数字构成 但是重复的数字很多 我们可以利用异或的自反性来化简这个等式。我们惊叹于等式变成了一个原序列组成的数字==af 且左式中没有重复的数字出现。
综上我们证明出来了线性基可以拼成整个序列中的元素了...很棒不是么...(弱鸡的快乐...
基本的性质也都说过了 证明也有了我们可以利用其来解题了~！
LINK：模板线性基
发现和上面的性质 无关 如何选取最大的数字呢？我有一个想法 对于一个满的线性基来说 能构成最大的数字是确定的 因为 我们可以通过不断的异或把线性基中的每个元素让其当前这维变为1.这样最大值就是线性基各个维度都取1的最大值了。
可事实却是可能有一些维度是不满的如何选取最大？我们考虑构造出来这个数字 将其设为x 且x=a1^a2^a3...an.
线性基 可以构成这个x如何让其最大 考虑贪心首先如果从较小位开始选择的话后面较大的数位可能也具有较小位那么此时我们必然选大的东西那么再次异或形成的数字就是 比原本的数字还要小我们不如不选这个较小的可以变得更大。
所以我们贪心的选的话从高位开始选因为高位时高于低位的 我们这样选择高位和低位不发生冲突...所以是最大的。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define ll long long using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } ll n,ans; ll f[52],cnt; inline void structure(ll x) { for(ll i=51;i>=0;--i) { if(x&(1ll<<i)) { if(!f[i]) { ++cnt;f[i]=x; break; } else x^=f[i]; } } } signed main() { freopen("1.in","r",stdin); n=read(); for(ll i=1;i<=n;++i)structure(read()); for(ll i=51;i>=0;--i) if((ans^f[i])>ans)ans=ans^f[i]; printf("%lld ",ans); return 0; }
关于位运算符要注意 加括号优先级太低了 谁知道哪个地方没注意就爆零了呢....
考虑如何求出最小值 注意观察我们线性基的状态 ...专业一点的术语来说叫做一个高斯消元构造出来的一个极小线性基 注意是极小线性基 而并非是最小线性基呢...因为存在 可以直接人为构造出最小线性基出来...很简单自己可以想一下。
好吧这个极小线性基好像也是支持求最小值的因为是存在一个命题为一个序列的最小值一定在这个线性基当中。考虑反证法 如果不在 那么比如有一个二进制位相同的数字顶替了它但是其他二进制位还不为0的那种 此时插入那么当取二进制位位0 其他的又不为0了故还能插入到线性基当中...所以假设不成立. 既然我们这个线性基存在序列中的最小值我们思考一下如何创造出来更小的值...显然是这个最小值再异或上其他值或者是序列中的某个数进行异或的到的答案更小。
我们不妨论述一下这两种情况 前者由于当前线性基中的最小值异或前面任何数字都是要比其本身大的 异或序列中的数字也没用...所以它本身就可以作为答案的后选项之一。再论述另外一种情况：一个数字经过重重异或到达了当前我们线性基这一位了，我们惊奇的发现只要这个数字再次异或这个最小的数字就能成为更小的，我们再次惊奇的于这样我们的线性基还可以再次扩大，我们瞬间平息了 构造出来的线性基是不可能有这种情况的。
综上 这个最小值就是我们线性基中的最小值...证明很简单 就害怕你不相信 如同我一般 明明是自己证明的 还一直怀疑正确性...下一道题。
LINK：TJOI 2008 彩灯 去年元月时 花市灯如昼 ...
这道题就没有那么显然能快速的到答案了 每个开关能能控一部分的彩灯...如何数出所有的方案呢。
一个暴力的想法是 对于每一个开关 那么必然有某个开关到底是点还是不点 我们爆搜这个 然后状压灯的状态直接开数组进行一波乱搞...发现能得到30分。
考虑一下正解 我们先状压一下开关所控制的灯 一些二进制数。构造出来线性基 这样我们可以抛弃一些没有必要的开关了 因为他们能被其他开关所表示出来。考虑如何利用这个线性基来数数...
我可以不太负责的说 我看完题后就想到答案应该是2^线性基大小...显然?尽管看起来不太可靠但是带入几波数据发现就是这个答案 考场上用刚才的暴力和这个来对拍。。。这样 我们保底30分最高100分。(毕竟考场上能不正明就不证明...
现在来 仔细分析一下这个答案为什么会正确。我是如何快速得到答案的 通过对线性基的理解来看 对于线性基的每个开关我们是否使用只和我们是否想要打开当前我们控制的这个位置上的灯 如果还控制其他位置上的灯 那么这个是无用的我们所有灯的变化都是和其本身有关一个灯的亮灭所以对于附属的灯其实他们的亮灭是对方案数无关的 因为不存在两个个方案使得在原本的灯不变的情况下一个附属灯灭 一个附属灯也可以亮起来，如果存在 那么必然可以延伸控制出当前附属灯的开关 于此同时我们想要的状态也可以表达出来的话说明此灯不再是附属灯而是线性基中的一个 故原假设不成立。证毕。当然可以不用这么繁杂...但是上述过程显然是一个严谨的证明过程。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define ll long long using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const ll MAXN=52,mod=2008; ll n,m; ll a[MAXN]; ll f[MAXN],cnt; char ch; inline void structure(ll x) { for(ll i=51;i>=0;--i) { if(x&(1ll<<i)) { if(!f[i]) { ++cnt;f[i]=x; break; } else x^=f[i]; } } } signed main() { //freopen("1.in","r",stdin); n=read();m=read(); for(ll i=1;i<=m;++i) for(ll j=1;j<=n;++j) { ch=getc(); while(ch!='O'&&ch!='X')ch=getc(); if(ch=='O')a[i]|=(1ll<<j); } for(ll i=1;i<=m;++i)structure(a[i]); printf("%lld ",(1ll<<cnt)%mod); return 0; }
写这些蓝题 没意思 不妨来一道紫题...真正的省选题才是好题呢。
LINK：Lucky number 我从来都没有感觉幸运过...磨难面前也从来没有被幸免过...拼将一人头颅血 须把乾坤力挽回。SCOI2016 幸运数字
简化 树上每个点都有一个权值 求树上的一条路径的任意数字异或和最大。->线性基路径上的线性基...
考虑如何解题 初始想法暴力的对于没一条路径都构出线性基然后 再贪心的选取...复杂度Qnlogs+Qlogs s为数的最大值(其实nQ的复杂度早挂了 考虑如何快速构建出来路径上的线性基。
一个比较显然的想法是 树链剖分把树上问题转移到序列上 如果我们用线段树来维护序列上的线性基会造成什么样的效果呢？考虑线性基是否具有区间可加性。
不妨思考一个问题 两个线性基可以合并么 这个是我一直没有提出的问题...这还用说肯定可以 怎么合并在一起是一个问题，请教过源神之后（惹怒了他..他在学习化学... 其实这个弱智的问题 答案是暴力合并。
显然一个线性基大小不超过logn 通常这里我们指60，插入线性基的复杂度是60。那么暴力的复杂度也不过才 60*60没有log的得做法 这个logn)^2的做法够可以了...
还考虑树剖么 +线段树复杂度貌似很高 然后线性基暴力合并 logn*logn*logn*logn 最后还有Q次询问接受不了 倍增更快点好像 log*logn*logn 其实时间还是达到了1e10不过 加点常数优化 肯定跑不到...而且时限也很大...
最后再次考虑树剖 我们不用线段树维护 直接开数组维护某两点之间如果跳链的线性基 这样 复杂度跟倍增差不多了但是空间似乎比倍增小 但是比较难写不推荐这个...
作为省选题 这道题不算很难但是对细节和代码难度要求较高...对线性基的理解 也得更深。
一次AC了 码力依旧啊 (蕴含着一丝骄傲 一丝快乐 一丝期待 一丝...总而言之 言而总之 非常快乐..
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define ll long long using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=20010; int n,Q,len,T; ll g[MAXN],w[MAXN][16][61],ans[61]; int f[MAXN][16],d[MAXN],Log[MAXN]; int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1]; inline void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void insert(ll *a,ll x) { for(int i=60;i>=0;--i) { if(x&(1ll<<i)) { if(!a[i]) { a[i]=x; return; } else x^=a[i]; } if(!x)return; } } inline void dfs(int x,int father) { d[x]=d[father]+1;f[x][0]=father; insert(w[x][0],g[x]); insert(w[x][0],g[father]); for(int i=1;i<=T;++i) { f[x][i]=f[f[x][i-1]][i-1]; for(int j=0;j<=60;++j)w[x][i][j]=w[x][i-1][j]; for(int j=0;j<=60;++j)if(w[f[x][i-1]][i-1][j])insert(w[x][i],w[f[x][i-1]][i-1][j]); } for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn==father)continue; dfs(tn,x); } } inline void LCA(int x,int y) { if(d[x]<d[y])swap(x,y); insert(ans,g[x]); insert(ans,g[y]); for(int i=Log[d[x]];i>=0;--i) if(d[f[x][i]]>=d[y]) { for(int j=60;j>=0;--j)if(w[x][i][j])insert(ans,w[x][i][j]); x=f[x][i]; } if(x==y)return; for(int i=Log[d[x]];i>=0;--i) { if(f[x][i]!=f[y][i]) { for(int j=60;j>=0;--j) { if(w[x][i][j])insert(ans,w[x][i][j]); if(w[y][i][j])insert(ans,w[y][i][j]); } x=f[x][i];y=f[y][i]; } } insert(ans,g[f[x][0]]); return; } inline ll ask() { ll cnt=0; for(int i=60;i>=0;--i) if((cnt^ans[i])>cnt) cnt^=ans[i]; return cnt; } int main() { //freopen("1.in","r",stdin); n=read();Q=read(); for(int i=1;i<=n;++i) { g[i]=read(); if(i!=1)Log[i]=Log[i>>1]+1; } T=Log[n]; for(int i=1;i<n;++i) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0); for(int i=1;i<=Q;++i) { int x,y; memset(ans,0,sizeof(ans)); x=read();y=read(); LCA(x,y); printf("%lld ",ask()); } return 0; }
看一下题解 做题 做题前尽量不要看题解 做完题一定要看题解。 正解似乎是点分治 我构想了一下应该是可以做的 复杂度大概可能是一个nlog^2的吧我也不太会题解说的很不清晰...
下一道题：
LINK：最大XOR和路径
这题就很妙 我没有任何的思路/cy 正解是这样的 显然对于一个环来说我们想跑多少遍跑多少遍 这和前面我们的线性基的本质是一样的 每个数字随便用 。考虑如何获取 答案 必然是一条路径 可能加环也可能不加环...
我们环都 放到线性基里了 但是他们都是可以用么 答案是显然的 考虑这个环如果被使用了我们要从一个点奔向这个环然后 肯定还是得跑回去的 那么 这条路径由于异或两次 相当于没有 所以说线性基中的环可以随便使用...
考虑是哪一条路径会被我们选中呢？那个万众瞩目的 幸运儿 ,,,是随机的呢... 因为...当前我们选出的路径和那个最优的路径必然会形成环因为都是从起点出发终点结束 经过异或这个环我们就得到那个环了。
综上算法是把环放到线性基里然后进行 随便选一条路 然后去线性基立寻找max即可。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define ll long long using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=100010; int n,m,len; ll f[62],e[MAXN<<1],d[MAXN]; int vis[MAXN]; int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1]; inline void add(int x,int y,ll z) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; e[len]=z; } inline void insert(ll x) { for(int i=60;i>=0;--i) { if(x&(1ll<<i)) { if(!f[i]) { f[i]=x; return; } else x=x^f[i]; } if(!x)return; } } inline void dfs(int x) { vis[x]=1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(!vis[tn]) { d[tn]=d[x]^e[i]; dfs(tn); } else insert(d[x]^d[tn]^e[i]); } } inline ll ask(ll x) { for(int i=60;i>=0;--i) if((x^f[i])>x)x=x^f[i]; return x; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;++i) { int x,y;ll z; x=read();y=read();z=read(); add(x,y,z);add(y,x,z); } dfs(1); printf("%lld ",ask(d[n])); return 0; }
LINK：最小异或和路径
这道题 就比较容易了 其实还是上一题的思路 唯一的不同点是最小的异或和路径 之前我们讨论过如何求出整个序列中的最小值 这里要求的是给定数字的最小值 怎么做？不可能再是线性基中的最小元素了，如何让ans更小考虑 贪心的处理二进制下的每一位 还是从大到小因为高位数字还是会影响低位的选取 所以 应该从大的到小的。代码常数较小目前不用开o2都是最优解/cy
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define ll long long using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=100010; int n,m,len; int f[32],e[MAXN<<1],d[MAXN]; int vis[MAXN]; int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1]; inline void add(int x,int y,int z) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; e[len]=z; } inline void insert(int x) { for(int i=30;i>=0;--i) { if(x&(1<<i)) { if(!f[i]) { f[i]=x; return; } else x=x^f[i]; } if(!x)return; } } inline void dfs(int x) { vis[x]=1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(!vis[tn]) { d[tn]=d[x]^e[i]; dfs(tn); } else insert(d[x]^d[tn]^e[i]); } } inline int ask(int x) { for(int i=30;i>=0;--i) if((x^f[i])<x)x=x^f[i]; return x; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;++i) { int x,y,z; x=read();y=read();z=read(); add(x,y,z);add(y,x,z); } dfs(1); printf("%d ",ask(d[n])); return 0; }
LINK：元素element
光刷题没意思 说点我自身的事情 元素 让我想起了 银龙王啊...白银龙枪(每天晚上基本上都会幻想自己是金龙王和银龙王的中二少年...
这道题让大致意思就是说找到一个集合使其异或不为0且权值最大那么就是 那这个集合怎么找？这显然是一个线性基的集合 能异或出来任何的数字 且异或和一定不为0 如果为0那就不是线性基了... 当然除非发生上述情况 p函数全部取0的时候...
这个跟新NIM游戏一样 由大到小贪心的加到线性基了 关于贪心的证明 第一二道题就证明过了.这里不再赘述。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cstdlib> #include<cctype> #include<utility> #include<queue> #include<stack> #include<deque> #include<vector> #include<set> #include<map> #include<bitset> #define db double #define ll long long #define id(x) t[x].id #define v(x) t[x].v using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=1000; int n,flag,ans; ll f[62]; struct wy { ll id; int v; int friend operator <(wy a,wy b){return a.v>b.v;} }t[MAXN]; inline void insert(ll x) { for(int i=60;i>=0;--i) { if(x&(1ll<<i)) { if(!f[i]) { f[i]=x;flag=1; return; } else x=x^f[i]; } if(!x)return; } } int main() { //freopen("1.in","r",stdin); n=read(); for(int i=1;i<=n;++i) { ll x,y; x=read();y=read(); t[i]=(wy){x,y}; } sort(t+1,t+1+n); for(int i=1;i<=n;++i) { flag=0; insert(id(i)); if(flag)ans+=v(i); } printf("%d ",ans); return 0; }
LINK：第k小异或和 XOR
通过此题 我对线性基的理解 更深了一层...
求一个异或空间的第k小超级有意思... 如何做这个操作呢？首先说明一个东西 对于基底中的每一个数字我们称其为主元 构造出第k小 不妨思考一下最小的数字 是主元中最小的那个次小的呢？主元上面的那个么 未必 可能主元再异或上面的数字可能更小。
所以 为了求出最小的 线性基而不是极小线性基我们还需要进行一次高斯消元 求出最小线性基 步骤呢？从最小的开始么 不对吧 从最大的开始因为最小的当主元意味着最大的可能当不了主元这样的话最后求出的线性基还是一个比较大的。
这样我们 求出最小线性基 然后再构造出来第k小 显然第二小是倒数第二个主元 第三小呢 显然是第一个异或第二个主元...就这样就没了...其实 我们将其二进制拆分就好了 。注意 0的情况就好了线性基中我们往往会忽略0这个东西。
//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<ctime> #include<algorithm> #include<cctype> #include<utility> #include<queue> #include<map> #include<set> #include<bitset> #include<deque> #include<vector> #include<cstdio> #include<cstdlib> #include<iomanip> #include<stack> #include<string> #include<cstring> #define INF 1000000000 #define ll long long #define db double #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define mp(x,y) make_pair((x),(y)) using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f<0?-x:x; } const ll MAXN=50010; ll n,k,T,Q; ll f[62],flag,cnt; inline void insert(ll x) { for(ll i=60;i>=0;--i) { if(x&(1ll<<i)) { if(!f[i]) { f[i]=x; ++cnt; return; } else x^=f[i]; } } flag=1; } inline void GAUSS() { for(ll i=0;i<=60;++i) { if(!f[i])continue; for(ll j=i+1;j<=60;++j) if(f[j]&(1ll<<i))f[j]=f[j]^f[i]; } } inline ll ask(ll k) { ll ans=0; for(ll i=0;i<=60;++i) { if(!f[i])continue; if(k&1)ans=ans^f[i]; k=k>>1; } return ans; } int main() { //freopen("1.in","r",stdin); T=read(); for(ll w=1;w<=T;++w) { printf("Case #%d: ",w); flag=cnt=0;n=read(); memset(f,0,sizeof(f)); for(ll i=1;i<=n;++i)insert(read()); GAUSS(); Q=read(); for(ll i=1;i<=Q;++i) { int x=read(); if(flag)--x; if(x>(1ll<<cnt)-1)puts("-1"); else printf("%lld ",ask(x)); } } return 0; }
题目不是很好懂但是仔细看 还是可以看懂的 将一个集合的所有子集的异或和进行排序 然后询问x在这个序列中第一次出现的位置。
这个很有意思了 我听闻可以求一个数列的第k大异或和 这个是相反的给定x让求第k大。...好像还不太一样 这个是多重集.这样的话就比较难受了 是多重集的...
如果不是的话我们显然可以求出...考虑如何统计那些相同数字的答案。我们不妨转换一下问题 给定x 我们能求出来什么 在线性基中我们必然能求出来这个数字是第几小的 不过这是不重集的，我们要求的也就相应转化了设刚才是第k小的 我们输出的答案应该是k-1小的数字个数+1这就其排名 考虑0出现了多少次显然的 总数字个数为n 线性基大小为cnt 答案为1+2^n-cnt 第二小的数字个数呢？这就转换成更一般的形式了 我们知道它的大小为倒数第一个主元好像显然还是1+2^n-cnt...哇好像是正确的 无意中就推出来了因为是这样的 考虑第二小的数字还是我们刚才构造的最小线性基中的第二个主元 还有呢 我们已知线性基之外的元素为n-cnt 这些元素我们完全可以视为0因为可以利用线性基给异或成0 然后再异或第二个主元而外面的东西可以随便选啊 答案就是2^n-cnt乌拉...感觉发现了世界的奥秘。
那么本题的做法就有了 先求其是第k小的然后 (2^n-cnt+1)*(k-1+1)。。。快速幂一下就好了 然后 值得注意的是0也算 注意细节就好了。
写代码的时候又开始神志不清了...所以wa了很多次...处理这个相互转换的时候还是很好想的吧...
//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<ctime> #include<algorithm> #include<cctype> #include<utility> #include<queue> #include<map> #include<set> #include<bitset> #include<deque> #include<vector> #include<cstdio> #include<cstdlib> #include<iomanip> #include<stack> #include<string> #include<cstring> #define INF 1000000000 #define ll long long #define db double #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define mp(x,y) make_pair((x),(y)) #define mod 10086 using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f<0?-x:x; } const ll MAXN=50010; ll n,k,T,Q; ll f[62],cnt,pos[62]; inline void insert(ll x) { for(ll i=60;i>=0;--i) { if(x&(1ll<<i)) { if(!f[i]) { f[i]=x; ++cnt; return; } else x^=f[i]; } } } inline void GAUSS() { for(ll i=0;i<=60;++i) { if(!f[i])continue; for(ll j=i+1;j<=60;++j) if(f[j]&(1ll<<i))f[j]=f[j]^f[i]; } } inline ll rank(ll x) { ll r=0; for(ll i=0;i<=60;++i) { if(i>=1)pos[i]=pos[i-1]; if(f[i])++pos[i]; } for(ll i=60;i>=0;--i) { if(!f[i])continue; if(x&(1ll<<i)) { x=x^f[i]; r=r|1<<(pos[i]-1); } } return r; } inline ll fast_pow(ll b,ll p) { ll ans=1; while(p) { if(p&1)ans=ans*b%mod; p=p>>1; b=b*b%mod; } return ans; } signed main() { //freopen("1.in","r",stdin); n=read(); for(ll i=1;i<=n;++i)insert(read()); GAUSS(); Q=read(); if(!Q){puts("1");return 0;} k=rank(Q); //printf("%d ",k); printf("%lld ",(((fast_pow(2,n-cnt))%mod)*k%mod+1)%mod); return 0; }
最后 一道题 从学博弈论到入门线性基 我可真是个...(学博弈学着学着学到了线性基/cy
LINK：八纵八横 纵横家 往往都是很nb的一类人...虽然跟此题无关.rt
这题 很水 但是要求学的东西 很多...至少我知道是什么知识点但是没写过...看来这次我不得不写了，看完题目显然就是一张图求从1开始到1的一条路径上的异或和最大 做过上面拿到WC的题目我们都知道 这肯定是环。。。
发现初值也是环 我们把环放到线性基里 然后寻找最大值就好了... 发现有修改有删除有添加操作..我们都知道线性基是不可能支持删除或者修改操作的...
全国人民都知道 在这个关键的时刻我们应该来一点奇技淫巧... 直接线段树分治就好了 (谁都能想到好不好...
但是我不会线段树分治 直接 学一发好了 这题真无聊。。。
感觉懂了一丝丝 以前好像写过这玩意不过回溯好像不太会...这里再次点名线段树分治的原理吧.
狭义：只计算左边对右边的贡献。(CDQ...
广义：只计算外部对内部的贡献。(线段树...
说起来很好说 写起来就比较难写了用到了平常很少写的bitset 函数bitset的做法也是第一次写 最关键的是没判断Q是否大于1 RE半天...
//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<ctime> #include<algorithm> #include<cctype> #include<utility> #include<queue> #include<map> #include<set> #include<bitset> #include<deque> #include<vector> #include<cstdio> #include<cstdlib> #include<iomanip> #include<stack> #include<string> #include<cstring> #define INF 1000000000 #define ll long long #define db double #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define mp(x,y) make_pair((x),(y)) #define zz p<<1 #define yy p<<1|1 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f<0?-x:x; } const int MAXN=510,maxn=1010; int n,m,Q,len,cnt; char a[maxn],ca[10]; struct data { int x,y; bitset<maxn>s; }w[maxn]; int last[maxn]; int lin[MAXN],nex[MAXN<<1],ver[MAXN<<1],vis[MAXN]; bitset<maxn>e[MAXN<<1],dis[MAXN],f[maxn]; vector<data>t[maxn<<2]; inline void add(int x,int y,bitset<maxn>s) { ver[++len]=y;nex[len]=lin[x];lin[x]=len;e[len]=s; ver[++len]=x;nex[len]=lin[y];lin[y]=len;e[len]=s; } inline bitset<maxn>get_in() { bitset<maxn>s;s.reset(); scanf("%s",a); int l=strlen(a)-1; for(int i=0;l>=0;++i,--l)if(a[i]=='1')s.set(l); return s; } inline int insert(bitset<maxn> s) { for(int i=999;i>=0;--i) { if(!s[i])continue; if(f[i][i])s=s^f[i]; else {f[i]=s;return i;} } return -1; } inline void dfs(int x,int father) { vis[x]=1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn==father)continue; if(vis[tn])insert(dis[x]^dis[tn]^e[i]); else dis[tn]=dis[x]^e[i],dfs(tn,x); } } inline bitset<maxn>ask() { bitset<maxn>s;s.reset(); for(int i=999;i>=0;--i) { if(!f[i][i])continue; if(s[i])continue; s=s^f[i]; } return s; } inline void output(bitset<maxn>s) { int flag=0; for(int i=999;i>=0;--i) { if(s[i])flag=1; if(flag)printf("%d",s[i]==1?1:0); } puts("");return; } inline void change(int p,int l,int r,int L,int R,data x) { if(L<=l&&R>=r){t[p].push_back(x);return;} int mid=(l+r)>>1; if(L<=mid)change(zz,l,mid,L,R,x); if(R>mid)change(yy,mid+1,r,L,R,x); return; } inline void solve(int p,int l,int r) { vector<int>g; for(int i=0;i<t[p].size();++i) { int mark=insert(dis[t[p][i].x]^dis[t[p][i].y]^t[p][i].s); if(mark!=-1)g.push_back(mark); } if(l==r)output(ask()); else { int mid=(l+r)>>1; solve(zz,l,mid); solve(yy,mid+1,r); } for(int i=0;i<g.size();++i)f[g[i]].reset(); } int main() { //freopen("1.in","r",stdin); n=read();m=read();Q=read(); for(int i=1;i<=m;++i) { int x,y; x=read();y=read(); add(x,y,get_in()); } dfs(1,0); output(ask()); for(int i=1;i<=Q;++i) { int x,y; scanf("%s",ca+1); if(ca[1]=='A') { x=read();y=read(); w[++cnt]=(data){x,y,get_in()}; last[cnt]=i; } if(ca[2]=='h') { x=read(); change(1,1,Q,last[x],i-1,w[x]); w[x].s=get_in();last[x]=i; } if(ca[3]=='n') { x=read(); change(1,1,Q,last[x],i-1,w[x]); last[x]=-1; } } for(int i=1;i<=cnt;++i)if(last[i]!=-1)change(1,1,Q,last[i],Q,w[i]); if(Q)solve(1,1,Q); return 0; }
至此 本题的核心就是利用线段树分治来撤销操作而并非 暴力删除线性基 复杂度很稳吧Qlogn*logn+Qlogn....一堆的不分析了。。把操作分成logn层是关键...
至此 初学线性基我总结完了很常见的线性基题目可以继续我的博弈之路了，作为一个赌徒,什么都挡不了我。也挡不住我...