郑州专业网站制作服务报价,wordpress 跳转首页,前端开发岗位,网站开发 高职课本什么是线性基#xff1f;
先来回顾一下向量空间中的基。这个基代表着空间的一个极大线性无关子集#xff0c;组中向量线性无关#xff0c;且空间中的任意一个向量都可以唯一地由基中的向量来表示
那么回到线性基#xff0c;它其实就类似于是一个向量空间的基
我们考虑一…什么是线性基
先来回顾一下向量空间中的基。这个基代表着空间的一个极大线性无关子集组中向量线性无关且空间中的任意一个向量都可以唯一地由基中的向量来表示
那么回到线性基它其实就类似于是一个向量空间的基
我们考虑一个问题给定一个数组a要求一个最小的数组d使得a中的任意一个数可以由d中的若干个数字来通过异或得到且d中任意多个数字的异或结果不为0
注意到异或操作其实就是在模2意义下的加法操作我们如果将每一个数字按二进制位分解就可以看成一个n维向量我们假定数字2^n
所以当前要求的东西如下
给定一个向量组a,求一组向量d向量个数为m使得存在唯一的一组解k满足加法在模2意义下且不存在一组解s使得.
这里
事实上这样一个线性基不一定是原数组的子集但是略去这一点的话它跟空间中的基的概念就有诸多相像的地方了。
这里列出对应的性质 1.数组中的任意一个数可以唯一地由线性基中的若干元素异或得到 2.线性基中任意多个元素的异或值不为0 3.线性基元素的异或集合等于原数组元素的异或集合 那么我们考虑一下如何求出这样一个集合并满足上述性质
好吧其实我也不知道前人是怎么搞出来这个东西的但是可以意会一下
异或中一个极好的思考角度就是从二进制位入手。想要得到一个数字说白了就是要让对应位为1或0.那么如果我们的线性基中每一个数字都有一位满足其它数字在这一位上都是0那么或许就可以操控了。所以线性基其实就是按位分成n个数字每一位对应一个数字或许没有
这里先给出求线性基的代码再慢慢讲解很简单的别走
void add(ll x)
{for(int i63;i0;--i){if(x(1lli)){if(d[i]) x^d[i];else {d[i]x;break;} } }
}
这是一个将元素尝试添加进线性基的代码。我们的操作就是让线性基中每一个元素的最高位拥有唯一的1就没了。这里如果一个数组的某一个1位已经存在对应的线性基元素了我们直接将其取异或知道它的最高位1是唯一的。如果没有这样的位也就是最后x0就无法加入线性基
为什么这样是合理的我们一个性质一个性质来看
不妨先看性质2 线性基中任意多个元素的异或值不为0 我们假设d[a]^d[b]^d[c]0并假设三者加入线性基的次序是a,b,c 显然d[a]^d[b]d[c]所以在c尝试加入线性基的时候就会加入失败。 得证 再看性质1 数组中的任意一个数可以唯一地由线性基中的若干元素异或得到 先考虑可行性 假设数字A成功加入线性基的第i个位置 那么A^d[a]^d[b]^...^d[c]d[i],反过来Ad[a]^d[b]^...^d[c]^d[i]. 如果A没有加入线性基 那就是因为线性基中存在一些数字的异或和A 得证 再考虑唯一性 如果存在两种方案使得d[a1]^d[a2]^..d[ai]d[b1]^d[b2]^..d[bj]A,那么取d[a1]^d[a2]^..d[ai]^d[b1]^d[b2]^..d[bj]0,与性质2矛盾 得证 性质3 线性基元素的异或集合等于原数组元素的异或集合 线性基中的元素都是原数组元素互相异或得来的所以该性质显然 所以说这样构造是合理的其实就是按位贪心。 然后我们考虑一下用处
求数组异或最大值
ans0;
for(int i60;i0;--i)
{ansmax(ans,ans^d[i]);
}
其实还是按位贪心如果高位能取到1的话就取因为决策具有单调性。 求数组异或最小值
如果有元素不能插入线性基那么最小值显然就是0否则就是线性基里最小的元素因为最小的元素无论异或谁都会变大 求数组异或的第k小
我们考虑将线性基重新构造使得每一个数字的每一位1都是唯一的
如果ijaj的第i位是1就将aj异或上ai。
这样我们只需要将k按二进制拆分对于1的位就异或上对应的元素即可
例题
板子
求数组异或最大值
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
const ll N1e510;
ll n,k;
ll mas[N];
ll d[70];
void add(ll x)
{for(int i60;i0;--i){if(x(1lli)){if(d[i]) x^d[i]; else{d[i]x;break;}}}
}
void solve()
{cinn;for(int i1;in;i) cinmas[i];for(int i1;in;i) add(mas[i]);ll ans0;for(int i60;i0;--i){ansmax(ans,ans^d[i]);}coutansendl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//ll t;cint;while(t--)solve();return 0;
}
彩灯
大意 求数组的异或结果的种类数
思路 我们考虑性质2显然线性基中不同元素的异或结果一定不同所以答案就是2^(线性基大小)
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
const ll N1e510;
ll n,m;
string s;
ll d[70];
vectorll vt;
void add(ll x)
{for(int i60;i0;--i){if(x(1lli)){if(d[i]) x^d[i];else{d[i]x;break;}}}
}
void solve()
{cinnm;for(int i1;im;i){cins;ll cnt0;for(int j0;jn;j){cnt*2ll;if(s[j]O) cnt;}//coutcntendl;vt.push_back(cnt);}for(auto i:vt) add(i);ll num0;for(int i0;i60;i) if(d[i]0) num;ll ans1;for(int i1;inum;i){ansans*2%2008;}coutansendl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
元素
大意
每一个元素有一个id和val选择一个子集任意多个id的异或结果不为0且val最大
思路
线性基中任意元素的异或结果不为0所以其实就是要求一个val最大的线性基。那么我们只要按val倒序贪心即可
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
const ll N1e510;
ll n,m;
struct ty
{ll num,val;
}mas[N],d[70];
bool cmp(ty a,ty b)
{return a.valb.val;
}
void add(ty a)
{for(int i60;i0;--i){if(a.num(1lli)){if(d[i].num){a.num^d[i].num;// a.vald[i].val;}else {d[i]a;break;}}}
}
void solve()
{cinn;for(int i1;in;i){cinmas[i].nummas[i].val;}sort(mas1,mas1n,cmp);for(int i1;in;i) add(mas[i]);ll sum0;
// coutsdf endl;
// for(int i0;i60;i) if(d[i].num) coutd[i].num d[i].valendl;
// coutendl;for(int i0;i60;i) sumd[i].val;coutsumendl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
新Nim游戏
大意 懒
思路 Nim的一个结论就是元素异或和为0时先手必败否则先手必胜
所以当前先手的策略就是使得后手无论怎么拿都不可能使元素异或和0。也就是我们要取尽可能少的数使得局面成为一个线性基。因为总能构造出一个线性基多了就拿掉呗所以先手必胜
那么升序插入线性基即可
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
const ll N1e510;
ll n,m;
ll mas[N];
ll d[70];
ll sum0;
void add(ll x)
{ll prex;for(int i60;i0;--i){if(x(1lli)){if(d[i]) x^d[i];else{d[i]x;break;}}}if(x0) sumpre;
}
void solve()
{cinn;for(int i1;in;i) cinmas[i];sort(mas1,mas1n,greaterll());for(int i1;in;i) add(mas[i]);coutsumendl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
最大XOR路径
大意:
给一个 n 个点 m 条边权值为di的无向有权图可能有重边和子环。可以多次经过一条边求1→n 的路径的最大边权异或和。
思路
显然一条边被走两次之后贡献就是0那么我们什么时候会这样做当第二次经过时可以到达其它地方时
其实这里有一类边集是很特殊的环。我们可以异或来得到整个环的值再从起点出去就类似于是一个额外贡献。
这启示我们我们可以将图分为一个一个环和一条链。我们的主线是链我们沿着链走中间碰到有环可以走的话我们可以走也可以不走。那么就相当于求环的值的集合的一个线性基然后求链的值与该线性基元素的异或的最大值即可。
这里还有两个问题
1.从环回去要走重边所以环的值要扣掉重边对应的部分
2.如何选择我们的主链
事实上如果有两条主链的话就有了一个环 我们取价值为a的路可能不如b优但是环的价值是a^b,那么在最后的操作中a^(a^b)就得到了b。所以我们其实可以任意选择一开始的主链。另外选择不同的主链最后可能会得到不同的一个一个的环。如何保证不同链能得到相同的环不能保证环套环的情况可能会导致不同的遍历顺序得到不同的环但是简单环的异或操作可以得到所有的简单环。具体可以看一下这里
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
const ll N1e510;
ll n,m;
struct ty
{ll t,l,next;
}edge[N1];
ll cn0;
ll head[N];
ll res[N];
ll vis[N];
ll d[70];
void add(ll x)
{for(int i63;i0;--i){if(x(1lli)){if(d[i]) x^d[i];else {d[i]x;break;} } }
}
ll ma(ll x)
{ll ansx;for(int i63;i0;--i){ansmax(ans,ans^d[i]);}return ans;
}
void add(ll a,ll b,ll c)
{edge[cn].tb;edge[cn].lc;edge[cn].nexthead[a];head[a]cn;
}
void dfs(ll id,ll now)
{vis[id]1;res[id]now;for(int ihead[id];i!-1;iedge[i].next){ll yedge[i].t;if(!vis[y]) dfs(y,now^edge[i].l);else add(now^edge[i].l^res[y]);}
}
void solve()
{memset(head,-1,sizeof head);cinnm;for(int i1;im;i){ll a,b,c;cinabc;add(a,b,c);add(b,a,c);}dfs(1,0);
// for(int i64;i0;--i) if(d[i]) coutd[i] ;
// coutendl;coutma(res[n])endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
Shortest Path Problem?
大意 跟上一题一样只是变成求路径异或最小值了
那么只是换个板子的事情
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
const ll N1e510;
ll n,m;
struct ty
{ll t,l,next;
}edge[N1];
ll cn0;
ll head[N];
ll res[N];
ll vis[N];
ll d[70];
void add(ll x)
{for(int i63;i0;--i){if(x(1lli)){if(d[i]) x^d[i];else {d[i]x;break;} } }
}
ll mi(ll x)
{ll ansx;for(int i63;i0;--i){ansmin(ans,ans^d[i]);}return ans;
}
void add(ll a,ll b,ll c)
{edge[cn].tb;edge[cn].lc;edge[cn].nexthead[a];head[a]cn;
}
void dfs(ll id,ll now)
{vis[id]1;res[id]now;for(int ihead[id];i!-1;iedge[i].next){ll yedge[i].t;if(!vis[y]) dfs(y,now^edge[i].l);else add(now^edge[i].l^res[y]);}
}
void solve()
{//164就炸了 memset(head,-1,sizeof head);cinnm;for(int i1;im;i){ll a,b,c;cinabc;add(a,b,c);add(b,a,c);}dfs(1,0);
// for(int i64;i0;--i) if(d[i]) coutd[i] ;
// coutendl;coutmi(res[n])endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
装备购买
大意 求一组向量的极大无关组其中每一个向量还有一个价值val要求极大无关组的val总和最小
思路 其实就是实数意义下的一个线性基。那么我们用高斯消元像求线性基一样如果当前最高位向量最左边元素没有对应的线性基就加入并更新后面对应的元素即可
至于val总和最小跟之前一样贪心即可
其实就是一个消元求解方程组的过程。
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
#define ldb long double
const ldb eps1e-7;
const ll N510;
ll n,m;
struct ty
{ldb val[N];ldb cost;friend inline bool operator (const ty a,const ty b){return a.costb.cost;}
}mas[N];
ll d[N];
ll cnt0;
ldb ans0;
void solve()
{cinnm;for(int i1;in;i){for(int j1;jm;j) cinmas[i].val[j];}for(int i1;in;i) cinmas[i].cost;sort(mas1,mas1n);for(int i1;in;i){for(int j1;jm;j){if(abs(mas[i].val[j])eps) continue;if(!d[j]){d[j]i;//确定对应的基ansmas[i].cost;cnt;break;}ldb apmas[i].val[j]/mas[d[j]].val[j];for(int kj;km;k){mas[i].val[k]-ap*mas[d[j]].val[k];}}}coutcnt (ll)ansendl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
未完待续~
