【未完】#并非创作计划# 线性基学习笔记
2026-04-06 12:42:42
发布于：广东
29阅读
0回复
0点赞
嗯。就是主包没过昨晚 ABC G，然后想大学习线性基。
P3812
Difficulty：4.2 / Template
题意解析：给定一个长度为 的数组 。求 的子序列异或和最大值。
。
直接做是 或 的，显然过不了。
直觉告诉我们真正要用到的 其实是很少的，其它的都能被这些异或表示。
假设当前 能表示 个数，此时考虑 。
- 如果 能被前面的数表示，那它就没用了，依然只能表示 个数。
- 如果 不能被前面的数表示，那前面能表示的所有数显然都能异或上 变成一个新的数，此时能表示 个数。
所以真正用到的数的数量不超过 个。
现在考虑如何构造出这些。
见这个。没了。主要是特别巧妙不知道咋讲。
namespace cjdst{
ll base[64];
void solve(){
int n;
std::cin >> n;
while(n--){
ll val;
std::cin >> val;
for(int i = 63; i >= 0; i--){
if(val >> i & 1){
if(base[i]) val ^= base[i];
else{
base[i] = val;
break;
}
}
}
}
ll ans = 0;
for(int i = 63; i >= 0; i--){
if((~ans >> i & 1) && base[i]){
ans ^= base[i];
}
}
std::cout << ans << '\n';
}
}
时间复杂度：。
有帮助，赞一个