海淀信息奥赛游记

求此题题解

之前的题目做出来了（也因为比较“水”所以删了） 补充一下题目： 蓝题也许不水了吧（但愿是这样）

【GeOI-M1】赛时答疑帖

不是怎么都只做出来第一题啊？ 奖金 4.60 RMB！ 【GEOI-M1】赛时答疑帖 比赛基本内容 这里是 2026 GeOI Math Round 赛时答疑帖，你可以在此处提出问题或报名比赛，比赛时间为 2026/1/16 12:00 至 2026/1/31 00:00，剩余时间为赛后补题，不计入获奖名单。 这里是 比赛链接，邀请码为 HXmj。 这里是 作弊名单，第一周每日更新，剩余时间三日更新一次。 答疑情况 * T2 没有错误数据 赛时公告栏 截止于 2026/1/17 19:50，比赛报名人数 303030，有分人数 888，AK 人数 000。 信息 * [2026/1/16 13:06] 验题完成 * [2026/1/18 00:21] 恭喜 @𝓐𝓘𝓮𝓻 首杀 A 题！ 欢迎加入 GEOI！ * ACGO link * 洛谷 link * 加入要求（请先通读，然后申请加入并私信给出符合条件）

我的作文为什么才得了30分？！谁能帮Me

求评论和指点 老师到底是咋想的啊！！！ 《找回纯真》 著：墨白渊 记忆在时光的长河中流过，其中就有我找不回的星光。 一年级前，我还是那个爱穿彩色衣服、笑容透亮的孩子。可我现在却活成了曾经那个另厌恶的模样。波斯菊我没能留住，圣洁的土地上也开出了鲜红的黑玫瑰。 新学期开始前的周末，最好的朋友小墨为了庆祝，硬拉着我去了游乐场，说要陪我玩新出的项目。我本不想出门，却拗不过他的热情。毕竟，我与世界之间，隔着一层厚厚的玻璃。我能看见所有的热闹，但所有的声音都是闷响，所有的温度都无法传导。而他确实那束例外的光。谁料过马路时，一辆汽车失控冲来，小墨为了护我。。。温热的鲜血飞溅在我的脸上，我的大脑一片空白，耳朵一阵轰鸣，我多么希望这是一场梦，梦醒了，小墨就又会出现在我面前。 我开始封闭自己，把彩色衣服全锁进柜子，只穿黑白灰。我学着变得“黑心”，低价收商品再高价倒卖，成了大家口中的“奸商”；见同学犯错就肆意嘲弄，看着他人窘迫的模样，心里反倒多了一丝病态的安全感；我信奉基督教，却用虚伪的微笑掩饰恶意。——哪怕。。。知道这不行。 转机在一个周末的游乐场出现。我陪着亲戚去旧地，心情自然十分糟糕，无意间看见两个小孩：瘦小的男孩摔倒了，另一个小孩立刻跑过去，小心翼翼扶起他，还把自己的棉花糖分给他，眼里满是纯粹的善意。这一幕像钥匙，打开了尘封的回忆——从前我和小墨，也是这样的。 我站在原地，黑白衣服仿佛透着寒意。可是，失去的太多，黑山羊的河流把他们都带走了，已经找不回来了。嘴角一丝苦笑，转身，向着远方走去。 实际上——早就不指望救赎了——深渊底部的黑暗，比任何星光都更适合我。 上帝啊。。。

互动｜期末玄学许愿指南

🎒 期末倒计时！你的玄学能量储备好了吗？ 在刷题、背诵、焦虑、抓狂的边缘反复横跳…… 别怕！期末许愿池2.0 限时返场！ 用宇宙的能量，换考场的奇迹—— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌟 许愿通道正式开启 请严格按以下格式，留下你的神圣考前愿望： 🎯 我希望： __________ 💀 我愿意为此放弃： __________ 🔮 如果灵验，我将回来还愿并： __________ 🌟 优质示范： > 🎯 我希望： 数学期末考能稳定发挥，大题不崩 > 💀 我愿意为此放弃： 一周的峡谷夜游，专心刷题 > 🔮 如果灵验，我将回来还愿并： 在社区分享我的错题笔记+给AC君点爆100个赞 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 许愿者专属福利 所有按格式完整许愿的用户，均可参与能量池抽奖！ AC君将随机抽取 5位 天选锦鲤与点赞最高TOP1，送出AC狗拼图冰箱贴随机1片。 > ⏰ 活动时间：即日起 - 1月31日 23:59 > 🎉 开奖日期：2月2日（考完正好来还愿✨） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 许愿池使用说明 1. ✅ 愿望越具体、越真诚，宇宙接收信号越强！ 2. ✅ 放弃的代价要真实可执行（比如“放弃一周游戏”比“放弃呼吸”更靠谱） 3. ❌ 禁止许愿他人挂科（反向能量会反弹！） 4. 💫 互相点赞、评论加油的愿望，实现概率+99% ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌌 来自宇宙的回复 > “你刷的每一道题，背的每一个知识点， > 都会在考场上变成让你稳住的底气。 > 许愿不是魔法，而是给自己一个仪式感的承诺—— > 期末考试月，我们一起把它变成奇迹发生的土壤。” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👇 评论区已开放许愿通道，你的愿望，宇宙正在收听！ 转发给并肩作战的搭子，一起接收好运能量！ 🔮 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

《关于我想写一篇关于ACGO的史记》

现在急缺23，25年的史料，哪个DALAO能提供一点啊球球了[哭] 666上榜了 1/18 666一晚上没看成榜6了 1/19 冲4了嘎嘎嘎嘎 1/20 555掉5了 1/21 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最近闲得慌想写一篇关于acgo这个网站从上线到现在发生的大事件的合集，编成一部“史书”，各位dalao能帮我提供一些大事件吗，越大越好的那种 目前已知： 22.03.16 ACGO平台登记著作权 22.07.21 ACGO题单和竞赛系统登记著作权 22.09.29 A+B problem出现第一个AC； 22.11.10 ACGO正式发布，很多人发帖庆祝； 22.12.16 ACGO第一篇题解（目前能查得到的）出现了链接描述； 23.03.12 AC系列赛第一场（ACGO排位赛 #1）正式开始； 23.07中旬 法兰西&花似雪事件； 23.07下旬-08初 徐某事件； 24.03月下旬-04月下旬 一只姜论关于czw抄题解事件及czw《抄袭天才》文章事件； 24.03.30 学校校赛第一场（“码王杯”黑龙江工程学院第十届程序设计竞赛）正式开始； 24.04.20 大量用户曝光法兰西抄题解； 24.04月左右 精华帖子的盛世出现（俗称“百 家 争 鸣”）； 24.07月左右 czw重出江湖，大量dalao对他进行 赞美； 25.03.29 陶蠢事件上榜； 25.08.15 反动书事件； 25.09.15 左右的芙宁娜&滚C事件（虽然这是个误会）； 25.10月左右的和平宣言事件； 25.10.29 一只姜发布“高联省一拿下”的短暂回站帖； 25.12.26 ID4592666被一大群人抄袭昵称，且被冤枉禁言（这是真冤）； 26.01.14 ACGO第一届嘻哈赛开始报名，26.01.15 开始竞赛 小广告1 小广告2 小广告3 注：此贴仅为以后正式写时的草稿，仅供参考！

海淀信息奥赛游记

woc榜十了，感谢各位大佬观看，点赞的全家健康，长命百岁，比赛次次都AK 点个赞吧 求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了 年龄：11岁，六年级 身份：GESP五级79分的蒟蒻，男 角色介绍：牢孙（男，同班同学），牢白（女，隔壁班的） 考试全名：海淀区中小学生信息学奥林匹克竞赛 这样适合装b 先给大家展示一下考试 时间有点久，网上找的图，请见谅 目标：我不到啊，上次我第一赛段就趋势了 第一赛段 考前：看真题，信心满满，必须拿下好吧 考试时：被AI技术的题喂饱了 考完：在小绿书上查答案，估分80左右 出成绩：72?????，同班同学（不知名姓孙的物种）才64，压力！ （分数线62） 第二赛段 考前：复习2024年真题，感觉误闯天家了，啥也看不懂啊。疯狂补习排列组合ing 考试时：被排列组合喂饱了，还好复习了。 遇到会做的选择题： 不会做的： 考完：依旧小绿书，发现自己没救乐，基本错了一半啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 出分53 等待分数线处刑ing 牢孙微信告诉我他考了43，心情瞬间舒畅了 分数线出了，分数线43！ 不过我好像高兴不起来是为什么 致敬传奇压线王牢孙 彩蛋：由于牢白被嘲笑了，于是牢孙被牢白线下真实了 主包在旁边吃瓜看戏加油呐喊，也是很爽。主包非常有用 这句话运用了删除线的手法，体现了主包诚实的品质 赛后采访牢孙：男厕是个好东西 第三赛段 考前：ok啊也是来到我最擅长的上机编程了，必须1=的好吧（幻想自己1=ing） 考试时：6道题，满分600！看到前两道题，感觉稳了，输入输出是人都会啊。 看到T3~T6的我： T3~T6直接输出样例都提交了 考完：T1，T2应该AC了……吧，牢孙和牢白自认为做出了3道，主包被狠狠地嘲笑了 漫 ~ 长 ~ 的 ~ 等 ~ 待 ~ 出 ~ 分 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 %%%疯了 我230，T1 T2AC T4 T5各骗15分，爽！ 牢孙190，他是怎么做到的？ 请看VCR： 牢孙T1：颗秒题 牢孙T2：做的太快颗秒自己（就得了80） 牢孙T3：不会 牢孙T4：苦思冥想ing 我会了！（结果因为没加max(1,ans)被紫菜了）10分 牢孙T5，T6：不会 等等，聪明的你可能会问，不会输出样例吗？ 没错，牢孙不会 牢白分数至今也是未解之谜，问她就说我知道也不告诉你（像个类人） 等待分数线中……

这怎么来的蓝

rt。 链接描述啥阴啊洛谷你告诉我这是蓝？ 天之蓝还是海之蓝

码上开聊VOL14 | 童瑞骐

码上开聊VOL14 | 童瑞骐：从ACGO榜一到CSP-S巅峰 关键词：CSP-S 一等、社区榜一、出题志愿者、ACGO核心玩家 > 个人档案 * 姓名：童瑞骐 * 社区昵称：cjdstttttt * 年级：九年级 * 坐标：广东深圳 * 江湖地位：ACGO社区长期“榜一”级核心大神、出题审核志愿者 * 硬核荣誉：2024年CSP-J一等奖，2025年CSP-S一等奖和NOIP(体验赛)一等奖 * 社区数据：一年提交超800次，解题数领先99.95%的用户，发帖破千，粉丝上千 * 社区好友：@Gragher，@dream92143，@MuktorFM，@复仇者_澜（不处不加团队） * 主页直通车：点击围观超级大帅童 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 正式开聊 Q1：社区里你的昵称“CJDSTTTTTT”，有什么特别的含义？ 帅童： 其实并没有特殊含义（（（，这个是按我 ACGO 一开始的 ID ”超级大帅童“ 改的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q2：你之前很长一段时间社区榜一，保持这种“统治级”的数据，背后是靠惊人的自律，还是纯粹的热爱驱动？ 帅童： 都有吧，我觉得更偏重于热爱。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q3：最早是怎么“入坑”编程的？是学校里接触的，还是自己偶然发现的？还记得第一次写出能运行的程序是啥感觉吗？ 帅童： 应该是偶然发现的。在我六岁的时候，妈妈觉得我没有什么爱好，就给我报了机器人兴趣班，但我手太笨拼不了那些，机构老师感觉我适合打代码，所以就入坑编程了。当天我调试了几次代码后发现能运行了，非常兴奋。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q4：从“学着玩”到“认真打比赛”，这个转变是怎么发生的？ 帅童： 大概就在去年，打ACGO 排位赛 #9 的时候，当时我熬了一晚上终于 AK 了。虽然现在看来题没有多难，但是这确实是我转向疯狂刷题的地方。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q5：为了达到现在的水平，你觉得自己投入最多的是什么？在这个过程中有没有想放弃的时候，又是怎么坚持下来的？ 帅童： 我投入最多的就是时间和精力。但我整个过程还算比较顺利的，也比较开心，没有放弃的想法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q6：从排位榜一大佬，变成为公开赛设计考题、审核比赛的“幕后大佬”，你觉得哪个角色更有挑战，也更有趣？ 帅童： 我觉得还是在当公开赛负责人时更有趣，因为能让其他 ACGO 同学做上我出的题特别有成就感（虽然现在看来质量也不是很高）。 附：帅童贡献的题目 * A49458.统计……？ * A49459.迷宫 * A49457.圆环游戏 * A49456.一个简单的迷宫 …… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q7：今年CSP-S拿下一等奖，这个结果在你意料之中吗？你觉得是哪些因素让你稳稳拿下？ 帅童： 也没多稳吧，当时估分的时候发现好像挂了 757575 分，吓死了，但最后出题人还是在 T3 送了我 303030，让我压线过一等。 我觉得今年的 CSP-S 能拿一等主要是心态还算不错，在发现不会写 T1 后没有特别崩溃，秒开 T2 并光速想到了接近正解的解法，后面一优化就 808080 分了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q8：作为过来人，你觉得对于冲刺CSP-J/S这种比赛，线下上课系统学，和在ACGO上刷题实战，这两件事怎么配合效果最好？ 帅童： 我认为应该理论和实践相结合，上课与刷题实战一个也不能少。如果还有时间的话也可以尝试看看博客。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q9：有没有哪个瞬间，突然感觉课上学的一个算法，在ACGO的某道题上“通了”，然后解题功力大涨？ 帅童： 划分区间。这个是老师给的线段树题目的作业。做完这题我感觉对线段树优化 DP 更熟练了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q10：你发帖量也巨大，这种大量的输出和讨论，真的对你的编程思维有帮助，还是纯粹为了快乐？ 帅童： 一开始我发的都是一些灌水、无意义的帖子，但后来我会将我学到的知识、做过的题的题解发到讨论区，时不时复习一下，顺便给 ACGO 用户科普一下。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q11：时间管理是大难题！你怎么平衡学校、机构课程和ACGO上“根本停不下来”的刷题/比赛？给大家支个招吧！ 帅童： 这个对我也很困难，只能自己想办法挤时间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q12：遇到真的“卡死”的难题，你的终极求助链条是啥？先自己死磕？翻题解？还是直接“摇”老师？ 帅童： 首先会想 30min，如果完全没思路或者思路假了就看一下题解，否则会自己想下去。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q13：作为已经登上S组顶峰的大佬，你打算怎么在ACGO上调整训练模式，去征服下一座山？ 帅童： 现在要全面转战蓝紫黑题了，争取在省选的时候把两天的 T1 都做出来。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q14：说一条你认为最重要的、对竞赛选手的“逆耳忠言”。 帅童： 信竞之路会越来越难走，到了后面几乎只能花时间“死磕”了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q15：在ACGO里，你觉得自己最大的收获是什么？ 帅童： 学到了很多知识，提高了代码能力，而且还认识了一堆大佬（上面的社区好友全都是）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Q16：明年在学业和竞赛上有什么规划？打算如何实现？ 帅童： 编程和学业都要花时间做好，在补whk的同时也要努力刷题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > ⚡ 快问快答 * ACGO上最让你沉迷的功能是？ 讨论区。水讨论太好玩了（（（ * 最让你有挑战欲望的编程语言是？ 肯定是C++。 * 除了编程，最近在“肝”什么？ 在恶补语文、数学。 * 你的学习BGM风格是？ “随缘但坚持”，前面忘了后面忘了（（（ * 用一句话形容你的性格？ 有点糖（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 🎙️ 访谈结语 帅童的成长轨迹，是一条从偶然“入坑”到称霸社区，再到赛场夺魁的清晰路径。他的经历印证了热爱与坚持的力量：ACGO社区不仅是他的“练功房”，更是激发他从参与者成长为贡献者的舞台。面对未来更艰险的省选之路，他已准备好向蓝紫黑题发起新一轮冲锋。这份源于热爱的专注，或许正是他一路“稳”下去的最大底气。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击回顾往期访谈 >>

# 官方题解 | 欢乐赛#64题解

官方题解 | 欢乐赛#64题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔的土豆脑袋 入门 T2 皓仔和奶茶 入门 T3 皓仔的水果筛选 入门 T4 皓仔的指令执行 入门 T5 皓仔的累乘 普及- T6 皓仔的美丽子矩阵 普及- T1 皓仔的土豆脑袋 题目大意 直接输出一行语句 Potatoes are amazing!。 题解思路 直接使用 cout 进行输出即可。 参考代码 T2 皓仔和奶茶 题目大意 皓仔买了 aaa 包红茶和 bbb 盒牛奶来自己煮奶茶喝。 已知煮一锅奶茶需要 222 包红茶以及 333 盒牛奶， 请问皓仔手头的原料可以煮多少锅奶茶。 题解思路 可以煮的奶茶数量同时取决于红茶数量和牛奶数量。 aaa 包红茶可以煮 a/2a / 2a/2 锅奶茶， bbb 盒牛奶可以煮 b/3b / 3b/3 锅奶茶，因此最终实际上可以煮的奶茶数量应当是二者之间的最小值 min(a/2,b/3)min(a / 2, b / 3)min(a/2,b/3)。 参考代码 T3 皓仔的水果筛选 题目大意 nnn 个苹果的重量分别为 a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1 ,a2 ,⋯,an ， 现在皓仔将第一个苹果的质量 a1a_1a1 设定为本次出售的苹果重量基准值，重量和 a1a_1a1 差距不超过 555 的苹果都可以一起打包出售， 问皓仔这次可以出售多少个苹果？ 题解思路 题目要求苹果质量和第一个苹果的差距不超过 555, 那么可以使用绝对值表示差距: abs(a[i] - a[1]) <= 5。 或者根据数字的大小范围来判断： a[i] >= a[1] - 5 && a[i] <= a[1] + 5 遍历整个数组，每次发现符合条件的数字，则答案加一，最后输出答案即可。 参考代码 T4 皓仔的指令执行 题目大意 对于一个数字 xxx, 执行 nnn 次指令，在每次执行之后对 202601012026010120260101 取模。 对于每一条指令，令 sumsumsum 为指令内所有字符的 ASCIIASCIIASCII 码的总和， 如果 sumsumsum 是一个奇数， 那么令 x=x2x = x^2x=x2， 否则 x=2×xx = 2 \times xx=2×x。 题解思路 循环 nnn 次输入所有的指令，本题中对于每一条指令，我们遍历字符串内部的所有字符，计算得到总和之后，根据数字是奇数还是偶数来执行对应的指令： 如果 sumsumsum 是一个奇数， 那么令 x=x2x = x^2x=x2， 否则 x=2×xx = 2 \times xx=2×x，每一次操作之后将数字对 202601012026010120260101 取模。 参考代码 T5 皓仔的累乘 题目大意 皓仔计算从 111 累乘到 nnn 的结果，但他会避开他不喜欢的数字：凡是数位中包含数字 aaa 或 能被 aaa 整除的所有数，一律跳过不进行累乘。 题解思路 循环嵌套练手题，外层循环首先从 111 到 nnn 进行枚举，在内层需要进行数位分解，判断数字的数位是否含有 aaa。 如果当前数字既不是 aaa 的倍数，也不含有数字 aaa, 那么将其进行累乘，注意每一次需要将答案对 1e9+71e9 +71e9+7 取模。 参考代码 T6 皓仔的美丽子矩阵 题目大意 皓仔把一个子矩阵称为美丽子矩阵，当且仅当这个子矩阵的行数和列数都大于 111, 并且该子矩阵的四个角（左上、右上、左下、右下）格子的颜色完全相同。 现在请你帮助皓仔统计：在整张画布中，一共有多少个美丽子矩阵？ 题解思路 本题是一个子矩阵枚举的模板练习，当我们想要枚举子矩阵时候只需要做两件事情：枚举左上角的点，再枚举子矩阵右下角的点。 首先编写两重循环 i→[1,n],j→[1,m]i \rightarrow [1, n], j \rightarrow [1, m]i→[1,n],j→[1,m]枚举左上角的点 (i,j)(i,j)(i,j)。 注意右下角的点 (t,k)(t, k)(t,k)，坐标需要大于等于左上角的点，因此枚举起点为 (i,j)(i, j)(i,j)， 则枚举范围为 t→[i,n],k→[j,m]t \rightarrow [i, n], k \rightarrow [j, m]t→[i,n],k→[j,m]。 对于每一个子矩阵，判断四个角颜色是否一致，是的话答案加一。最后输出答案。 参考代码

堆学习笔记

叠甲： > 本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。 堆及堆的性质 > 堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。 > > 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．STL 中的 priority_queue 其实就是一个大根堆。 > > （小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。 -- OI wiki ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 堆使用数组进行储存。对于第 iii 个节点，其父节点下标为 i2\frac{i}{2}2i ，左右孩子节点下标分别为 2×i2 \times i2×i 与 2×i+12\times i+12×i+1 。 （小根）堆元素的插入与取出 1. 在堆尾加入该元素，并把这个节点设为当前节点。 2. 比较当前节点与父节点的大小： 2.1 如果当前节点小于父节点，交换他们的值，并把父节点设为当前节点，重复步骤 2。 2.2 若当前节点大于父节点，或该节点已经为根节点，停止。 小根堆插入代码实现： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 取出堆的根结点的值 2. 把堆的最后一个结点（len）放到根的位置上，把根覆盖掉。把堆的长度减一。 3. 把根结点置为当前父结点 。 4. 如果当前父节点无儿子（parent>len/2parent >len/2parent>len/2），则结束；否则，把当前父节点的两（或一）个儿子中值最小的那个设置为当前的子结点。 5. 比较当前父节点与当前子节点的值，如果当前父节点的值小于或等于当前子节点的值，则结束；否则，交换这两个结点的值，把当前父节点指向当前子节点，继续执行步骤 4。 小根堆取出当前节点并删除当前节点代码实现（这里分为 top 和 pop ） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 手写堆模版： 小根堆： 大根堆： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 真题演练： 题目 题目大意： 给你 NNN 个数，要求输出他们从小到大排列的结果。 思路： 这里我们使用堆排序。 很简单，首先构建一个堆，将这 NNN 个数放入堆。之后取出所有元素并输出即可。注意这里使用小根堆。 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 超市 题目大意： 超市里有 NNN 件商品，每件商品都有利润 pip_ipi 和过期时间 did_idi ，每天只能卖一件商品，过期商品不能再卖。 求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。 其中 N≤2×105N\leq 2\times 10^5N≤2×105。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本题有两种做法，一种是采用贪心的策略，但是可能会爆。所以我们用堆。 先预处理所有商品，构建一个结构体并按照过期时间进行排序。 建立一个小根堆（这里采用 STL 容器的方式）。由于一天只能卖一个商品，所以堆的大小就是卖商品的天数。如果当前的商品过期天数与当前卖商品的天数相等，我们就看堆顶的那件商品（因为是小根堆，所以这件商品的收益肯定最小）的收益，如果比这件商品小，我们就替换掉。否则直接添加至堆中即可（因为已经排过序了）。 CODE