线性基 & 洛谷 P3812 【模板】线性基
2021/10/26 23:10:12
本文主要是介绍线性基 & 洛谷 P3812 【模板】线性基,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
线性基
推荐Menci博客的前半部分:https://oi.men.ci/linear-basis-notes/
非常学术的讲解了线性基。
然后对于如何构造线性基,我一般使用以下方法:
对于每一个加进来的数,从高位向低位扫,若某一位是1,则看线性基的a[i]是否有值,若有,则这个数^=a[i],否则a[i]=这个数,插入完毕。
功能
- 查询最大异或和:从高位开始枚举,若异或上a[i]的ans更大,则异或上。
- 查询最小异或和:线性基里的最小的数
- 查询异或值的数量:2的线性基长度次幂(线性基长度即为线性基内元素个数)
AC代码
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; long long ans,a[55],n; void work(long long x){ for(int i=50;i>=0;i--){ if((1ll<<i)&x){ if(a[i]) x^=a[i]; else{ a[i]=x; return; } } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ long long x; cin>>x; work(x); } for(int i=50;i>=0;i--){ if((ans^a[i])>ans) ans=ans^a[i]; } cout<<ans; return 0; }
这篇关于线性基 & 洛谷 P3812 【模板】线性基的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求