求此题题解

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

互动｜期末玄学许愿指南

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

关于ACGO的一些小建议

叠甲：仅代表个人想法，勿喷 广告 关于ACGO的一些小建议： 处罚的力度 * 首先处罚的力度就很值得一说。处罚的力度大了，风气自然就好了。 至于如何处罚，值得一谈。 首先 ACGO 是一个 OJ 平台，作为一个 OJ 平台，那么学术诚信固然重要，现在感觉官方把“学术诚信”至关重要的这一点丢弃，作为次要的，把大精力丢弃到去管一些非常琐碎的小事。浪费资源。 其次不理解ACGO为什么会对“禁言”这个处罚情有独钟。个人认为学术诚信和禁言半毛钱关系没有。早就建议过官方加上“棕名”“扣分”“清空通过题目”这些处罚。不知道官方到底是为什么一直没有加。是技术原因还是什么，难猜。个人认为加上“棕名”“扣分”“通过0”这些处罚更好的能改变学术诚信。 再就是关于“封禁”这个或许是最严重的惩罚。建议 ACGO 采取洛谷一样对“封禁”的方式。建议给予一个封禁的期限（考虑到糖丸较多觉得定在 1~3 个月左右差不多），不要封禁就永久封，对社区的风气毫无帮助。建议的是增加给予“封禁”这个处罚的频率，减少“封禁”这个处罚的严重程度。当然对于屡教不改的可以给一点特殊关照。 觉得官方应该着重注意下以下几个点，而不是琐碎的小事： * 慢慢地把竞赛作弊者的比例降下来，考虑到糖丸较多，降到“10%”已经很好了，岁虽然远没有达到LGR的“2%”。对于这个建议官方除以“每作弊三次封禁 1 个月”这样的处罚，更有利于社区发展。大小号参赛封禁大小号各 1 个月 * 整治抄题解，提交记录行为。对于这个，主要让用户去菊爆。主要看两道题目的提交时间只差以及用户习惯的码风。一旦发现再30天内抄10次题解或提交记录的，与比赛作弊同罪。再者就是加上例如拿到40pts以上再让用户看提交记录是不是大大减少了这些事发生的频率 讨论区质量 关于社区的讨论区有一些机制很令人费解。 For example“热榜”这个机制很不理解。例如发这个帖子当时的热榜状况： 真正的学术贴可能只有 1 个甚至可以说是没有。不知道官方整改整改在哪里了。把学术贴全整改没了。 说真的不理解为什么让热帖上榜而不是学术贴。 个人认为应该让官方置顶帖优先上榜，有空位的让最新发布的学术贴上榜。 这个机制会稍微好些。再就是加强在学术贴内灌水的禁言力度。 还有些涉政的到没有造成什么特别大的实质性影响，这看官方自己了 @AC君

想看就看

这是我在ACGO上第一次过生日，当然只是公历生日。临近期末我希望我，大家期末都能考到自己想要的分数。 蛋糕🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂。一人一个够分吗… ——2026年1月12日 天上飞的慕温

CXXP#1赛前预告帖

广告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 加入 CXXP 公开赛出题组要求见此处，有意愿且符合要求的私信忘川秋库 * 待定，等一个金主来 比赛介绍 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 这里是 C++Pippi#1 （简称 CXXP#1 ）比赛。 * 本场比赛时间为 202620262026 年 222 月 161616 日 8:008:008:00 ∼\sim∼ 202620262026 年 222 月 181818 日 12:0012:0012:00，共 222 天 444 小时 ，由于时间不短，不建议打满。 * 本场竞赛题目很简单，大约在红~绿，欢迎各位来玩，题目详细信息见题目信息。 * 本次竞赛采用 ACGO 赛制，实时可见排名。 * 本场比赛不计入 ACGO 等级分，请放心参与。 * 鸣谢各位参赛者参赛，各位工作人员出比赛，审核员审核，xmw 提供 ACGO ，尚弟提供世界。 * 赛后补题 出题组信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次比赛出题组成员： * 题目主要负责人：亚洲卷王 * 出题人：亚洲卷王，忘川秋库，🥥 * 验题人：PPX|AndyCGM/，yaonainai，复仇者_澜（中途退出），AC是最好的，Cocacola * 数据人：复仇者_零（中途加入） * 审题人：Xylophone（中途加入），༺ཉStars_Seekerད༻（中途加入） 除 AC是最好的外，其余人均达到了 奖项认证/铂金段位 条件。AC是最好的已向管理组报备。 出题组非必要不要在赛时提交代码。 以下用户因为见过题目或提前为下次竞赛提前加入出题组而不得参赛： * priority（不加团队）（下次竞赛出题者） * 滚蛋吧c++（中途加入又中途退出） 题目信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次竞赛所有题目时间限制均为 1000ms1000ms1000ms ，空间限制均为 128MB128MB128MB ，每题中的每个测试点均等分，每题满分 100100100 分 题目序号 题目idea来源 实际出题人 测试点数量 难度 题型 T1 忘川秋库 忘川秋库 101010 入门 传统 T2 🥥 🥥 505050 普及- 传统 T3 忘川秋库 亚洲卷王 & 忘川秋库 505050 普及/提高- 传统 T4 亚洲卷王 亚洲卷王 202020 普及+/提高 传统 相关链接 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 竞赛综合帖 * 赛前预告帖 * 赛时答疑帖 * 题解与总结 广告再出现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 加入 CXXP 公开赛出题组要求见此处，有意愿且符合要求的私信忘川秋库 * 待定，等一个金主来 奖品信息 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 快速 AK 变换 * 在开赛 30min30min30min 内，首个 AKer\texttt{AKer}AKer 送出 222 个盲盒 + 随机 222 块拼图 + 111 个吧唧（如无在 30min30min30min AKer\texttt{AKer}AKer 则取消此奖励） * 由于题目不难，排行榜前 333 且 AK\texttt{AK}AK 的送出 111 个盲盒 + 随机 222 块拼图 + 111 个吧唧（如榜前三不是 AKer\texttt{AKer}AKer 则取消此奖励） 一血 * 每题首杀获得 111 个盲盒 + 111 个吧唧 不幸中的不幸 * 所有题目均有 80 pts80~pts80 pts 以上且没有 111 题通过获得随机 111 块冰箱贴 万幸中的万幸 赛后执行此代码，被抽中的对应排名获得随机 111 块冰箱贴，若作弊则取消该奖项。 题解奖 * 让有奖项认证的出题人看到的符合要求的题解之创作者，可以获得奖品（待定）。 作弊者的新年礼物 * 作弊者会受到至少 333 天的禁言作为奖励。 所有奖项允许叠加，作弊顺延，如果报名人数超过 100010001000 且有提交人数超过 600600600 会补上一些有价值的奖品或是奖金。 注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 如果发现比赛有原题或其他影响公平性的因素，请私聊管理员和出题人，而不要以任何方式公开，违者视影响可能会得到取消成绩或禁言的惩罚。 * 因为是新年期间的竞赛，赛时的答疑可能不及时，但一般情况下看到了就会进行答疑。 * 不给予直播讲解，提供文字题解与赛后补题。 关于作弊 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 审核方式 CXXP 赛事的作弊审核与传统的方式不相同，我们会将每个选手的 444 道题的代码随机选择 1∼41\sim 41∼4 份代码进行抽查，即每个选手的代码都会被审核者看到。 主要的作弊方式有： * AI 辅助答题（A） * 大小号答题（B） * 代码辱骂（C） * 调戏反作弊机制（D） * 赛时讨论做法（E） * 赛时灌水（F） * 索要、套取他人代码或思路（G） * 负责人觉得就是作弊了（S） 申诉机制 若初审被认定作弊，可以申诉，但申诉人必须满足以下条件之一： 1. 提交参赛全程的全屏录制视频，视频内容须清晰展示整场比赛完整操作过程，且画面可辨识参赛者身份及操作界面。视频可以在 BiliBili 等视频网站上传、也可以提交百度网盘等网盘链接； 2. 由 CCF 认证不小于 888 级的用户代为提交申诉，须充足理由； 3. 自身的 CCF 认证不小于 666 级，须充足理由； 4. 明显不是作弊行为的：出题人提交选手代码、或者代码中直接复制题面等情形。 任何用户仅可进行一次申诉，申诉一旦失败则在 ACGO 公示选手代码进行众裁。申诉成功撤销记录。 公示机制 一旦被认定作弊一次，即公开名单、取消奖品且不可再在 CXXP 系列赛事中获得奖品，哪怕写检讨也仍然禁赛。

撤销 进入主站 权限

封禁用户\color{brown}封禁用户封禁用户 （PS：棕色） * 撤销 进入主站 权限 @忘川秋库因为黑沉石鱼惊旋被封禁一年。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 封禁用户\color{brown}封禁用户封禁用户 （PS：棕色） @忘川秋库因学术不端而棕名惩罚十四天。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 出错啦 该账户因为违反洛谷社区规则（https://help.luogu.com.cn/rules/community/）被封禁。如需咨询或者申请解封，请发送符合要求的材料至电子邮箱 shensu283@luogu.com.cn，管理员可能在 30 日内处理，也有可能不处理。

码上开聊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社区不仅是他的“练功房”，更是激发他从参与者成长为贡献者的舞台。面对未来更艰险的省选之路，他已准备好向蓝紫黑题发起新一轮冲锋。这份源于热爱的专注，或许正是他一路“稳”下去的最大底气。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击回顾往期访谈 >>

【GeOI-M1】赛时答疑帖

奖金 3.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] 验题完成

堆学习笔记

叠甲： > 本文为学习笔记，非创作计划。所以格式上的问题，大佬喷轻点。 堆及堆的性质 > 堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。 > > 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．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

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

666上榜了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最近闲得慌想写一篇关于acgo这个网站从上线到现在发生的大事件的合集，编成一部“史书”，各位dalao能帮我提供一些大事件吗，越大越好的那种 目前已知：25.8.15反动书事件，25.9.15左右的芙宁娜&滚C事件，25.10月左右的和平宣言事件，26.1.14ACGO第一届嘻哈赛开始报名，26.1.15开始竞赛