ps网站制作教程,外贸网站模板设计,企业网站代运营,长沙做网站一般要多少钱ACM模板 文章目录构造线性基线性基模板操作线性基相关题目学习线性基可考虑以下大佬博客 知乎Pecco博客 博客园Kaori博客 menci博客 肖然博客 从线性代数谈线性基#xff08;有点硬核#xff09; 构造线性基
普通插入#xff1a; 不能保证除了主元上其他线性基元素该位置为…ACM模板 文章目录构造线性基线性基模板操作线性基相关题目学习线性基可考虑以下大佬博客 知乎Pecco博客 博客园Kaori博客 menci博客 肖然博客 从线性代数谈线性基有点硬核 构造线性基
普通插入 不能保证除了主元上其他线性基元素该位置为1
typedef unsigned long long ull;
ull p[64];
void insert(ull x)
{for(int i63;i0;i--){if(!(xi1)) continue;if(!p[i]) {p[i]x;break;}x^p[i];}
}进阶插入 若p[i]!0即主元i存在则线性基中只有p[i]的第i位是1且此时p[i]的最高位就是第i位 bool insert(ll x)
{for(int i62;i0;i--){if(!(xi1)) continue;if(p[i]){x^p[i];continue;}for(int ji-1;j0;j--)if(xj1) x^p[j];for(int j62;ji;j--)if(p[j]i1) p[j]^x;p[i]x;return 1;}return 0;
}线性基模板操作 1.在一系列数中选若干数做异或求最大值。 反向遍历p[]数组按高位贪心因为对于每个p[i]来说当且仅当目前的res的第i位为0时选这个数可以使res增大。而此时选它一定比不选它更优
普通插入代码
ull getmax()
{ull res0;for(int i63;i0;i--)if((res^p[i])res) res^p[i];return res;
}进阶插入直接把所有p[i]异或即是最大值。 2.在一系列数中选若干数做异或求最小值。 直接求线性基然后选最小的一个即可。显然它与线性基中任意其他数异或后都不会更小。 注意特判0
普通插入代码
ull getmin()
{if(cnt0) return 0;for(int i0;i63;i)if(p[i]) return p[i];
}进阶插入找到最小主元即可 3.查询某数是否能被表示出来 按照插入的思路进行检查即可。
bool belong(ull x)
{for(int i63;i0;i--){if(!(xi1)) continue;if(!p[i]) return false;x^p[i];}return true;
}4.查询第k小值 使用进阶插入解决此问题把k进行二进制分解把1对应位置的主元xor起来。 注意第0小是0
ll now[64];
int cnt0;
for(int i0;i62;i)if(p[i]) now[cnt]p[i];
ll query(ll k)
{if(flag) k--;if(!k) return 0;if(k(1ullcnt)) return -1;ll res0;for(int i0;icnt;i)if(ki1) res^now[i];return res;
}线性基相关题目
【模板】线性基 普通插入即可解决
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N70;
ull p[N];
int n;
void insert(ull x)
{for(int i63;i0;i--){if(!(xi1)) continue;if(!p[i]) {p[i]x;break;}x^p[i];}
}
int main()
{cinn;for(int i1;in;i) {ull x;cinx;insert(x);}ull res0;for(int i63;i0;i--)if((res^p[i])res) res^p[i];//不难发现只有(resi1)0是才会满足if语句coutres\n;return 0;
}异或运算 第k异或小使用进阶插入即可解决。
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N10010;
ll p[70];
int n,q;
bool flag;
ll now[70];
int cnt;
bool insert(ll x)
{for(int i62;i0;i--){if(!(xi1)) continue;if(p[i]){x^p[i];continue;}for(int ji-1;j0;j--)if(xj1) x^p[j];for(int j62;ji;j--)if(p[j]i1) p[j]^x;p[i]x;return 1;}return 0;
}
ll query(ll k)
{if(flag) k--;if(!k) return 0;if(k(1ullcnt)) return -1;ll res0;for(int i0;icnt;i)if(ki1) res^now[i];return res;
}
int main()
{int T;cinT;for(int ca1;caT;ca){printf(Case #%d:\n,ca);memset(p,0,sizeof p);flag0;cnt0;cinn;for(int i1;in;i){ll x;cinx;if(!insert(x)) flag1;}cinq;for(int i0;i62;i)if(p[i]) now[cnt]p[i];while(q--){ll k;cink;coutquery(k)\n;}}return 0;
}[BJWC2011]元素 按照magic逆序然后线性基插入
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
typedef unsigned long long ull;
const int N1010;
ull p[N];
struct node
{ll id,w;bool operator(const node o) const {return wo.w;}
}q[N];
int n;
bool insert(ull x)
{for(int i63;i0;i--){if(!(xi1)) continue;if(!p[i]) return p[i]x,1;x^p[i];}return 0;
}
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i) cinq[i].idq[i].w;sort(q1,q1n);ll res0;for(int i1;in;i){if(insert(q[i].id)) resq[i].w;}coutres\n;}return 0;}Good subset 线性基线段树题解 搜索题解 2020/09/30 要加油哦~
