线性基 小鱼儿 2022-03-17 11:52 158阅读 0赞 原本想整理下前段时间做的牛客网的赛题,其中有个题目是线性基解决,于是就误入了线形基的坑...看了b站上“时光蒸汽喵”大佬的讲解,很是舒适,今天来整理下几个常见的类型。 学习过程中参考的博客,[线性基学习笔记][Link 1] [关于线性基的学习与理解][Link 2]。 # 题型一:求第k小的异或结果 # [hdu3949 XOR][] #include<iostream> #include<queue> #include<cstdio> #include<cmath> #include<cstring> #include<string> using namespace std; const int maxn = 1e4+10; const int maxbit=63; const int INF=0x3f3f3f3f; typedef long long ll; ll A[maxn],P[maxbit],L[maxbit]; int main() { int T; scanf("%d", &T); int kase = 0; while(T--){ printf("Case #%d:\n", ++kase); int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lld", &A[i]); } memset(P, 0, sizeof(P)); for(int i = 1; i <= n; i++) { for(int j = maxbit-1; j >= 0; j--) { if((A[i]>>j) & 1){ if(P[j] == 0) { P[j] = A[i]; break; } else { A[i] ^= P[j]; } } } } for(int i = maxbit-1; i >= 0; --i) { for(int j = i+1; j < maxbit; ++j) { if((P[j]>>i) & 1) P[j] ^= P[i]; } } int r = 0; for(int i = 0; i < maxbit; ++i) { if(P[i]) L[r++] = P[i]; } int q; scanf("%d", &q); while(q--){ ll k; scanf("%lld", &k); if(n != r) //第一小的数为0 k--; //因为下面第一小的都是从非0数开始组合的 if(k >= 1LL<<r) // printf("-1\n"); //总共可以组合出 2^r-1个数 else { ll ans = 0; for(int j = 0; j<maxbit; j++) { if((k>>j) & 1) ans ^= L[j]; } printf("%lld\n",ans); } } } return 0; } # 题型二:求权值最大的那个线性基 # [P4570 \[BJWC2011\]元素][P4570 _BJWC2011] **题意**:给你物品的编号和价值,让你求出最大价值,并且选定物品编号的异或和不为0。 **分析**:由异或和不为0可知,需要用线性基来维护物品编号。至于最大价值,显然按物品价值从大到小加入构建线性基即可。 #include<iostream> #include<queue> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn = 1e3+10; const int maxbit=64; const int INF=0x3f3f3f3f; typedef long long ll; struct Thing { ll val; ll id; bool operator < (const Thing A) const{ return val > A.val; } }; Thing A[maxn]; ll P[maxbit]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lld%lld", &A[i].id, &A[i].val); } sort(A+1, A+1+n); ll ans = 0; for(int i = 1; i <= n; i++) { for(int j = maxbit-1; j >= 0; j--) { if((A[i].id>>j) & 1){ if(P[j] == 0) { P[j] = A[i].id; break; } else { A[i].id ^= P[j]; } } } if(A[i].id) ans += A[i].val; } printf("%lld\n",ans); return 0; } 线性基题目:[P3211 \[HNOI2011\]XOR和路径][P3211 _HNOI2011_XOR] [P4151 \[WC2011\]最大XOR和路径][P4151 _WC2011_XOR] [Link 1]: https://blog.sengxian.com/algorithms/linear-basis [Link 2]: https://www.cnblogs.com/ljh2000-jump/p/5869991.html [hdu3949 XOR]: http://acm.hdu.edu.cn/showproblem.php?pid=3949 [P4570 _BJWC2011]: https://www.luogu.org/problemnew/show/P4570 [P3211 _HNOI2011_XOR]: https://www.luogu.org/problemnew/show/P3211 [P4151 _WC2011_XOR]: https://www.luogu.org/problemnew/show/P4151
还没有评论,来说两句吧...