尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
洛谷-B3930 [GESP202312 五级] 烹饪问题 题解
题意描述给定一个数列{ai}\{a_i\}{ai​}求找到一组i,j (i≠j)i,j~(i\neq j)i,j(ij)使aiand⁡aja_i \operatorname{and} a_jai​andaj​最大。约定记号设最优解的ii0ii_0ii0​jj0jj_0jj0​。也就是当ii0,jj0ii_0,jj_0ii0​,jj0​时aiand⁡aja_i \operatorname{and} a_jai​andaj​最大。解题思路设当前寻找最优解的范围是[l,r][l,r][l,r]也就是说目前可以确定l≤i0,j0≤rl\le i_0,j_0\le rl≤i0​,j0​≤r。初始时l1,rnl1,rnl1,rn。先将所有数从小到大排序从高到低检查每一位分讨这一位上的情况逐步缩小最优解所在范围。这位全部相同。答案显然与这一位无关l,rl,rl,r不用改动。这位上有且仅有一个111位于数列末尾。则最优解的这位一定为000将末尾的数这一位改成000并插入排序。当前位为111的数多于111个。则可以确定最优解这一位一定是111。二分出首个这一位为111的位置sss并令l←sl\leftarrow sl←s。最后当[l,r][l,r][l,r]范围缩小到两个数时可以确定i0l,j0ri_0l,j_0ri0​l,j0​r并求出最优解。时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)。Code#includebits/stdc.husingnamespacestd;constexprintN1e65;inta[N];intmain(){cin.tie(0)-sync_with_stdio(0);intn,L,R;cinn;L0,Rn-1;for(inti0;in;i)cina[i];sort(a,an);for(intbit130;bit;bit1){if((a[L]bit)||!(a[R]bit))continue;// 这一位全部相同if((a[R]bit)!(a[R-1]bit)){// 只有1个1intta[R]^bit,i;for(iR-1;iLa[i]t;--i)a[i1]a[i];a[i1]t;}else{// 1的个数多于1intlL,rR,mid;while(lr){midlr1;if(a[mid]bit)rmid;elselmid1;}Ll;}if(R-L1)break;}assert(LR);cout(a[L]a[R]);return0;}Update 2025.6.15修正错误的图片。Update 2025.6.16微调公式。Update 2025.12.6优化语言表达和代码格式。
RELATED

相关推荐

【opencv】Opencv python: seamlessClone泊松融合 (我把Lena变成了彼岸花怪/(ㄒoㄒ)/~~)

【opencv】Opencv python: seamlessClone泊松融合 (我把Lena变成了彼岸花怪/(ㄒoㄒ)/~~)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📅 2026/10/23 5:51:47
【c++】c语言入门到c++使用高手: c语言入门之函数(二)

【c++】c语言入门到c++使用高手: c语言入门之函数(二)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📅 2026/10/23 5:51:47
【c++】c语言入门到c++使用高手: c语言入门之编译预处理(二)

【c++】c语言入门到c++使用高手: c语言入门之编译预处理(二)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📅 2026/10/23 5:51:47
MORE NEWS

更多资讯

📰

第三章:9、工作流编排进阶

概览:支持灵活的条件分支与并行处理可复用子工作流实现流程嵌套通过 Webhook、消息队列等方式与外部系统无缝集成一、条件分支与并行网关1. 条件分支根据工单严重程度,自动路由到不同的处理流程:Configuration public class TicketWorkflowCo…

📰

程序员转型AI,涨薪40%的真相:别裸辞,看懂公司预算流向!

文章讲述了Java后端工程师转型AI后的薪资增长,指出淘汰程序员的不是新技术,而是公司预算流向。大模型岗位需求激增,薪资普遍高于传统岗位,但公司更需要的是懂AI的应用架构师而非简单的CRUD开发者。老工程师的经验在AI转型中成为优…

📰

7个模型外部工程实践,让你的AI Agent从“会聊天”变“能干活”!

本文深入探讨了构建高效AI Agent的关键要素,即模型之外的工程实践。从提示词工程、上下文工程、RAG检索增强生成,到工具调用、Agent记忆、子智能体编排,最后是评测体系,这七大组件共同构成了Agent能力的骨架。文章强调&#xff0c…

📰

Java开发者必看:掌握AI应用开发,收藏这份高薪转型指南!

文章指出,AI相关岗位需求激增,传统Java后端岗位面临收缩,但"JavaAI"复合型人才薪资溢价高达50%。文章分析了JavaAI岗位的核心能力要求,包括LLM接入、Agent工程化和AI驱动的性能优化,并提供了转型路径建议&am…

📰

小白程序员必看:收藏这份 LangChain RAG 实战指南

本文基于 LangChain 官方文档,深入解析 RAG 技术在大模型中的应用。从 RAG 的核心原理到 Deep Agents 的四种实现模式,详细阐述了如何为 LLM 提供外部知识访问能力,并重点解析了“检索-卸载-委托”模式。文章还涵盖了索引阶段、检索-生成阶段…

📰

智学文枢:学生与习题的状态中枢

student_store / question_store:学生与习题的状态中枢一句话摘要:学生是档案主体、习题是分析对象,StudentStore 与 QuestionStore 各自管好"内存缓存 CRUD Signal 广播",一个专注档案与分科配置,一个连图…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

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

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

📞 💬