算法学习：线性基

末蓝、 2021-11-17 10:12 257阅读 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 条评论，257人围观）

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

相关阅读

相关线性代数-基变换

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

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

相关复习机器学习算法：线性回归

Logistic回归用来分类，线性回归用来回归。线性回归是把让样本的属性前面加系数，相加。代价函数是误差平方和形式。所以，在最小化代价函数的时候，可以直接求导，令

末蓝、/ 2022年08月05日 15:22/ 0 赞/ 195 阅读

相关机器学习算法-------线性回归法

算法概述线性回归其实是一种比较基础的回归算法，他假设特征与最后的结果之间存在某种线性关系，他通过最小化损失函数（平方误差），来获取最优的系数值和截距值，主要通过最小二乘

浅浅的花香味﹌/ 2022年05月25日 11:20/ 0 赞/ 291 阅读

相关线性基

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

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

相关【模板】线性基

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

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

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

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

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

相关算法学习：线性基

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

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

相关【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 赞/ 308 阅读

相关线性基训练与总结

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

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

相关 SGU - 275 线性基初步

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

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