线性基模板+例题-北京尧图网络

一、基础线性基整数异或最常用模板代码#includebits/stdc.husingnamespacestd;在这里插入代码片typedeflonglongll;constintMAX_BIT60;// long long开60int开30ll p[MAX_BIT5];// 插入数字x到线性基voidinsert(ll x){for(intiMAX_BIT;i0;i--){if((xi)1){if(!p[i]){p[i]x;break;}x^p[i];}}// x最后变为0说明x可由现有基异或表示}// 查询集合能异或出的最大值llget_max(){ll res0;for(intiMAX_BIT;i0;i--)if((res^p[i])res)res^p[i];returnres;}// 查询集合能异或出的最小值llget_min(){for(inti0;iMAX_BIT;i)if(p[i])returnp[i];return0;}// 判断x能否由线性基中的数异或得到boolcheck(ll x){for(intiMAX_BIT;i0;i--)if((xi)1){if(!p[i])returnfalse;x^p[i];}returntrue;}// 清空线性基voidclear(){memset(p,0,sizeof(p));}二、带合并操作多组合并线性基// 将b线性基合并进avoidmerge(ll a[],ll b[]){for(intiMAX_BIT;i0;i--)if(b[i])insert(b[i]);}三、求第 k 小异或值进阶模板ll p[MAX_BIT5],d[MAX_BIT5];intcnt;// 线性基有效基底数量voidinsert(ll x){for(intiMAX_BIT;i0;i--){if((xi)1){if(!p[i]){p[i]x;break;}x^p[i];}}}// 重构基底用于求第k小voidrebuild(){cnt0;memset(d,0,sizeof(d));for(inti0;iMAX_BIT;i){for(intj0;ji;j)if((p[i]j)1)p[i]^p[j];if(p[i])d[cnt]p[i];}}// 查询第k小异或值llkth(ll k){ll res0;if(k(1LLcnt))return-1;// 不存在for(inti0;icnt;i)if((ki)1)res^d[i];returnres;}四、使用说明1. 数据范围区分数字范围是int(2^{31})MAX_BIT 30数字范围是long long(2^{63})MAX_BIT 60竞赛绝大多数情况2. 基础操作示例intmain(){clear();ll n,x;cinn;for(inti1;in;i){cinx;insert(x);}coutget_max()endl;// 最大异或return0;}五、线性基核心性质做题必背原数组任意数字异或结果都能等价用线性基异或表示线性基内部任意子集异或结果互不相同线性基不支持删除只能重建删除场景用线段树 / 分块套线性基数组存在 0 的条件插入时数字被消为 0说明该数能被其他数异或凑出。六、经典适用题型给定数组选若干数异或求最大值判断某个数能否由数组子集异或得到求所有子集异或结果中第 k 小区间异或、树上路径异或线段树 / 倍增线性基。例题牛客多校第二场 BB-Bitwise Maximization_2026牛客暑期多校训练营2中文题面题意给定一个非负整数列表要把每一个数必须分到两个多重集合 A、B 中的其中一个不能不选。定义一个集合的按位异或值集合内所有数做异或运算的结果空集异或值为 0。最终得分 A的异或值 B的异或值你需要求这个得分的最大可能值。做题思路题目要求最大化 X(S⊕X)其中 S 是所有元素的总异或和观察二进制的某一位如果 S 在这一位是1那么不管 X 在这一位是0还是1这一位对总和的贡献始终是一个1因为 X 和 S⊕X必然一个是0一个是1。如果 S 在这一位是0那么 X 和 S⊕XS⊕X 在这一位是相同的。为了让总和最大我们希望 X 在这一位是1这样总和的这一位上就会贡献两个1即 112。原代码直接对 ai建立线性基并最大化 ans这会导致线性基可能为了让 S 为1的某些位变成1而牺牲了让 S 为0的位变成1的机会。这是因为线性基在求max时不区分这些位的重要性但对我们的答案来说SS 为0的位对答案的增加有决定性作用而 SS 为1的位对答案根本没有影响。代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintM5e510;inta[M];//列表signedmain(){ios::sync_with_stdio(0);cin.tie(0);intT;cinT;while(T--){intv[65];//线性基memset(v,0,sizeof(v));intn;cinn;intm0,sum0;for(inti0;in;i){cina[i];mmax(m,a[i]);sum^a[i];}intw0;//最大位数while(m){w;m/2;}for(inti0;in;i){a[i]a[i]~sum;for(intjw-1;j0;j--){if(a[i]j1){if(v[j]!0){a[i]a[i]^v[j];}else{v[j]a[i];break;}}}}intans0;for(intiw-1;i0;i--){//coutv[i]:v[i] ;ansmax(ans,ans^v[i]);//coutans:ansendl;}coutans(sum^ans)endl;}}

线性基模板+例题

相关推荐

用码道 AI 编程助手开发番茄钟与任务统计工具

从Intel Edison到RK3588：硬核创客的智能硬件开发实战指南

智能办公自动化工具深度解析，棱镜AI工作流

更多资讯

CNN垃圾邮件分类实战：从.eml解析到Grad-CAM可解释性

IDEA源根报错排查指南：Source Root原理与修复实操

IDEA源根报错全面排查与修复指南

C# WinForm TCP多路转发器：单端口分发至多目标

工厂短视频不要当网红：以信任前置打造能接单的企业号

紧固件自动化生产怎么落地？从成本账到产线改造的完整指南

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？