算法学习：线性基

末蓝、 2021-11-17 10:12 330阅读 0赞

**线性基：**

通过将序列中的数字转化为二进制，表现为矩阵形式，于是通过矩阵的相关知识

就能够快速的求取区间内的最大异或和

**模板：洛谷【P3812】**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #define ll long long
     4 using namespace std;
     5 const int MAXN = 62;
     6 ll p[MAXN], a[MAXN];
     7 void insert(ll x)
     8 {
     9     for (int i = 50; i >=0; i--)
    10     {
    11         if (!(x&(1ll<<i)))
    12         {
    13             continue;
    14         }
    15         if (!p[i])
    16         {
    17             p[i] = x;
    18             break;
    19         }
    20         x ^= p[i];
    21     }
    22     return;
    23 }
    24 int main()
    25 {
    26     ll n;
    27     scanf("%lld", &n);
    28     for (int i = 1; i <= n; i++)
    29     {
    30         scanf("%lld", &a[i]);
    31         insert(a[i]);
    32     }
    33     ll ans = 0;
    34     for (int i = 50; i>=0; i--)
    35     {
    36         if ((ans^p[i]) > ans)
    37             ans ^=  p[i];
    38     }
    39     printf("%lld", ans);
    40     return 0;
    41 }

转载于:https://www.cnblogs.com/rentu/p/11234716.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/23aa4bd8170f48aa9a285dd89665dd0a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，330人围观）

还没有评论，来说两句吧...

相关阅读

相关线性基基本操作于模板

资料出处：[https://blog.csdn.net/a\_forever\_dream/article/details/83654397][https_blog.csdn.

谁借莪１个温暖的怀抱￠/ 2023年10月09日 12:54/ 0 赞/ 119 阅读

相关线性代数-基变换

[B站视频-线性代数的本质][B_-] 一般情况下，基向量为i-hat=【1,0】，j-hat=【0,1】使用不同基向量会怎样？如何在不同坐标系之间对向量进行转化？

左手的ㄟ右手/ 2023年06月13日 06:20/ 0 赞/ 128 阅读

相关线性基总结（题目合集）

线性基的三大性质：线性基能相互异或得到原集合的所有相互异或得到的值。线性基是满足性质1的最小的集合。线性基没有异或和为0的子集。模板：

待我称王封你为后i/ 2023年06月04日 02:59/ 0 赞/ 79 阅读

相关线性基

原本想整理下前段时间做的牛客网的赛题，其中有个题目是线性基解决，于是就误入了线形基的坑...看了b站上“时光蒸汽喵”大佬的讲解，很是舒适，今天来整理下几个常见的类型。学习过

小鱼儿/ 2022年03月17日 11:52/ 0 赞/ 300 阅读

相关【模板】线性基

include<bits/stdc++.h> using namespace std; define LL long long LL p[70]

灰太狼/ 2021年11月29日 18:38/ 0 赞/ 407 阅读

相关 HDU 3949 XOR——————线性基

[XOR][] Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

以你之姓@/ 2021年11月23日 04:28/ 0 赞/ 366 阅读

相关算法学习：线性基

线性基：通过将序列中的数字转化为二进制，表现为矩阵形式，于是通过矩阵的相关知识就能够快速的求取区间内的最大异或和模板：洛谷【P3812】 ![Cont

末蓝、/ 2021年11月17日 10:12/ 0 赞/ 331 阅读

相关【2017西安】 XOR (线性基+思维）

Consider an array AA with n elements . Each of its element is A\[i\]A\[i\] (1 \\le i \\l

亦凉/ 2021年11月09日 11:42/ 0 赞/ 409 阅读

相关线性基训练与总结

线性基我们先考虑基的一些定义和性质。唯一表示线性无关极小生成集 acm中的线性基一般是基于异或运算下的。根据第一条，我们可以解决一系

今天药忘吃喽~/ 2021年09月30日 06:10/ 0 赞/ 381 阅读

相关 SGU - 275 线性基初步

题意:求给出的数任意异或的最大值目前对线性基的理解过于肤浅,有空总结一下 include<iostream> include<algorithm>

缺乏、安全感/ 2021年09月29日 14:46/ 0 赞/ 373 阅读