尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
线性基模板+例题
一、基础线性基整数异或最常用模板代码#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;}}
RELATED

相关推荐

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

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

用码道 AI 编程助手开发番茄钟与任务统计工具一行需求,码道帮我写出了带进度环、任务管理和今日/累计统计的番茄钟——25/5/15 计时、localStorage 持久化、浏览器通知,全在一个 HTML 里分类: ai-development 标签: CodeArts, AI编程, 番茄钟, 任务统计,…

📅 2026/11/18 6:12:47
从Intel Edison到RK3588:硬核创客的智能硬件开发实战指南

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

1. 项目概述:一场属于硬核创客的集结号 “智造创意 硬享社区—— Intel & DF创客召集令”,这个标题一出来,老创客们大概会心一笑,新朋友们可能眼睛一亮。这不仅仅是一个活动名字,它更像是一封发给所有动手爱好者的…

📅 2026/10/7 5:23:35
智能办公自动化工具深度解析,棱镜AI工作流

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

在日常办公和内容创作中,越来越多的人开始关注如何通过技术手段提升效率。其中,能够将重复性工作自动化的解决方案尤其受到青睐。这种需求催生了一系列智能化工具的出现,它们正在改变传统的工作方式。智能化工具的核心功能这类工具主要通过流…

📅 2026/10/10 15:57:05
MORE NEWS

更多资讯

📰

平顶山应届生电工证学习资料正规证千万别踩坑,工地太忙根本没时间复习考试

平顶山应届生电工证学习资料正规证千万别踩坑,工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这是很多一线工友,特别是像我这样刚毕业的应届生最真实的写照。我也是去年刚从平顶山某高校毕业,被分配到某建筑工地实习,一开始对电工证一无所知,…

📰

住建部电工证的用途官方回应实操考试心里没底怕挂科

住建部电工证的用途官方回应实操考试心里没底怕挂科 你是不是正准备考住建部电工证,但实操考试心里没底怕挂科?别慌,官方回应已经明确,只要方法得当,通过率还是挺高的。特别是洛阳涧西区劳务班组负责人,这类证书在项目施工、电力安装等工作中至关重要。…

📰

电工证什么需求最多 官方回应最新报考指南

电工证什么需求最多 官方回应最新报考指南 你是不是也和我一样, 不知道去哪报名怕被中介坑 ?最近听说很多人都在打听“ 电工证什么需求最多 ”,但一到报名就晕头转向,各种中介、各种价格,让人摸不着头脑。其实,这个问题, 官方回应…

📰

铜梁区特种工考试怎么准备才不挂科?上岗必备实操经验全分享

铜梁区特种工考试怎么准备才不挂科?上岗必备实操经验全分享 实操考试心里没底怕挂科,尤其是第一次参加铜梁区特种工考试的你,担心自己操作不熟练、流程不熟悉,结果一紧张就出错。别慌,很多人刚接触特种作业证时都这么想,但只要掌握方法,完全可以通过。…

📰

中山考个电工证多少钱才能顺利拿证

中山考个电工证多少钱才能顺利拿证 你是不是正在找电工工作,但因为没证被拒绝?现在好多工地、工厂都要求必须有特种作业证才能上岗,尤其是电工证,是很多岗位的门槛。中山考个电工证,多少钱?怎么考?怎么过?今天咱们就来聊一聊。…

📰

谷饶电工证培训机构在哪考?学历不高怕报不上名?别慌,教你一招搞定

谷饶电工证培训机构在哪考?学历不高怕报不上名?别慌,教你一招搞定 学历不高怕报不上名?别急,谷饶电工证培训机构在哪考?其实很多人都有类似的担忧,但只要你掌握对的方法,照样能顺利拿到电工证,开启更好的职业发展。别让学历成为你进阶的绊脚石,关键…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬