首页 > 其他分享 >线性基学习笔记

线性基学习笔记

时间:2023-07-21 22:22:51浏览次数:45  
标签:int 笔记 学习 插入 异或 基的 线性 贪心

线性基的定义

在一个高维空间中一组极大的线性无关的向量组成为一组线性基,更严谨的定义参考线性代数相关内容。

但是在 OI 中我们常用的是异或线性基,它维护了给定若干个数能够通过异或计算出的所有的数,具体来说可以实现以下几个功能:

  • 求 min/max 异或和
  • 求 k 大异或和
  • 求异或和数量

线性基的构建

分为高斯消元法和贪心法,这里介绍贪心法。
考虑插入一个数 \(x\),从高位到低位遍历一个线性基,如果当前位线性基内没有值,那么把 \(x\) 作为当前位的代表值,否则让 \(x\) 异或上这一位,继续插入。
考虑这样做的正确性,从低位到高位插入,如果当前位没有值,那么 \(x\) 必不可能被表示,反之则 \(x\) 的这一位可有可无,如果一直到最后 \(x\) 都没有被插入,则我们认为本次插入失败。

需要注意的是,我们构建出来的只是一个能实现线性基功能的东西而不是严格的线性基,

code:

bool insert(int x){
	for(int i = 60; i >= 0; --i){
		if(!(x & (1ll << i))) continue;
		if(p[i]) x ^= p[i];
		else {p[i] = x; return 1;}
	}
	return 0;
}

求最大/最小异或和

继续考虑贪心,我们从高位到

求 k 大异或和

标签:int,笔记,学习,插入,异或,基的,线性,贪心
From: https://www.cnblogs.com/Lkkaknoi/p/17572504.html

相关文章

  • Django学习笔记:第二章django的安装和创建应用
    1.安装Django终端运行pipinstalldjango查看django是否安装成功python-mdjango--version1.1安装虚拟环境在控制台运行pipinstallvirtualenv1.1.2创建虚拟环境在特定文件夹内打开终端运行virtualenv-pD:\program_condition\python\python.exeenv_djvir......
  • 概率期望学习笔记总结
    一.OSU!题目背景原《产品排序》参见P2577题目描述osu是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子:一共有\(n\)次操作,每次操作只有成功与失败之分,成功对应\(1\),失败对应\(0\),\(n\)次操作对应为\(1\)个长度为\(n\)的01串。在......
  • 「学习笔记」AC 自动机
    AC自动机是 以Trie的结构为基础,结合 KMP的思想 建立的自动机,用于解决多模式匹配等任务。Trie的构建这里需要仔细解释一下Trie的结点的含义,Trie中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态,Trie的边就是状态的转移。形式化地......
  • 小样本学习-RN
    论文阅读《LearningtoCompareRelationNetworkforFew-ShotLearning》相关链接1.RelationNetwork官方代码解析2.github代码地址3.基础知识视频4.论文解析讲解视频......
  • 7.21语言结构学习
    语言结构学习第一题,答案;第二题,答案写,第一题,答案多少;第二题,答案多少......
  • 树上启发式合并学习笔记
    树上启发式合并\((dsu\on\tree)\)适用条件:可以在一个子树内统计的问题,并且不带修改。暴力复杂度一般为\(O(n^2)\)。例题:CF600ELomsatgelral解法考虑一个问题,给你一棵树,每个节点有一个颜色,如果一种颜色在以\(x\)为根的子树内出现次数最多,则称\(col_i\)占主要色。......
  • javaweb从入门到架构学习路线图?
    javaweb从入门到架构学习路线图?1.学习Java基础知识和面向对象编程的概念。2.了解计算机网络基础知识,包括HTTP协议、TCP/IP协议等。3.掌握HTML、CSS和JavaScript等前端技术,了解前后端交互原理和基本的前端开发技巧。4.学习基于Java的Web开发技术,包括Servlet、JSP等。5.深入学......
  • 学习日志
    7.21今天继昨天的递归进一步复习,写了一道搜索与回溯的题Letter#include<bits/stdc++.h>usingnamespacestd;intn,m,maxt=0;charc[25][25];map<char,bool>p;boolf[25][25];constshortdx[]={0,0,-1,1};constshortdy[]={-1,1,0,0};voiddfs(intx,inty,intt)......
  • Docker学习路线9:运行容器
    要启动一个新的容器,我们使用dockerrun命令,后跟镜像名称。基本语法如下:dockerrun[选项]镜像[COMMAND][ARG...]例如,要运行官方的Nginx镜像,我们可以使用:dockerrun-d-p8080:80nginx这会启动一个新的容器,并将主机的端口8080映射到容器的端口80。列出容器要......
  • java分布式从入门到架构学习路线?
    java分布式从入门到架构学习路线?初级阶段:1.Java基础知识:掌握Java语言的基本语法、面向对象编程的概念、集合框架和异常处理等基础知识。2.网络编程:了解Java网络编程的基本概念,学习Socket编程和网络通信协议,掌握TCP/IP和HTTP协议的基本原理。3.分布式系统概念:理解分布式系统......