和平被看成"和平暖暖"和"裙子精英"。

六一互动｜原来我从小就是个逻辑控？

🎈六一特别企划｜不是吧！原来我从小就是个逻辑控？ hi，AC狗友们 ，不是只有写代码才叫编程🧠 小时候玩过的那些游戏/玩具 ，可能早就偷偷给你种下了 逻辑思维的种子🌱 🕹️ 看到这些DNA动了没 🥇 Scratch小猫跳一跳 👉 原来“碰到边缘就反弹”就是if语句啊喂！ 🥈 Minecraft红石电路 👉 第一次手动实现“与门”，比数学课还早 🥉 Lightbot点亮灯泡 👉 用函数调用那关，脑子直接“叮”一声通了 …… 🎁 换你了！！！ 👉 你小时候玩过哪个 游戏/玩具 让你觉得“这好像在玩逻辑”？ 👉 有没有一个瞬间，让你突然觉得“我脑子转得快是因为它”？ 评论区直接写👇 格式不限，一句话or小故事都行～ 🎁 福利时间 活动截止后：符合活动要求的评论 * 点赞前6名 → 罐头 × 60 ； @RuiDaShuai2025，@全站的狗子我嘴最臭(慕温)，@༺དༀ༒哦，那咋了༒ༀཌ༻，@💩💩百大游戏解说官💩💩，@shenzhangzheng小号，@小金 回关 * 随机抽6人 → 罐头 × 20 ；@仙布着急，@horse，@人机猫，@天之神-小天狼星·布莱克，@玩不死身游戏被转生苹果砸到（回关@天之神_†赛伊德† ⏰ 即日起 至 2026.6.8 💬 评论区交出你的启蒙游戏～ 往期互动

互动｜真没招了！那些让你当场放弃的瞬间

真没招了！那些让你当场放弃的瞬间👇 Hi，AC狗友们 。有没有那么一刻 ，你对着屏幕 / 书本 / 生活 ，默默说了一句：“算了，真没招了”。 不是摆烂，是真的尽力了 。但结果还是……emmm 🎁交出你的“没招了”瞬间🧾 👉 你最近一次觉得 “真没招了” 是什么时候？ 👉 因为什么事？后来怎么解决的（还是没解决）？ 评论区直接写👇 例子：“调代码调了俩小时，结果是中文分号，真没招了。” 格式不限，一句话 or 小故事都行～ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 福利时间 活动截止后： * 评论点赞前 5 名 → 罐头 × 50 * 随机抽 5 人 → 罐头 × 20 ⏰ 即日起 至 2026 年 6月 16 日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💬 评论区交出你的 “没招了” 瞬间 往期互动

被老师请去喝茶的一天

啊？不是，上榜了？\LARGE 啊？不是，上榜了？啊？不是，上榜了？ 我真服了呀，今天竟然被老师请去办公室喝茶了😭😭(是因为我数学考了78分，一个非常吉利的数)大家有被老师请去办公室喝茶的经历吗？给我分享一下呗꒦ິ^꒦ິ

ZDZL OJ 用户规则

第一章 总则 第一条【立规目的】 ZDZL OJ 作为一个纯粹的 Online Judge 平台，需要所有用户共同维护秩序。为保障 ZDZL OJ 正常运营，制定本规。 第二条【适用范围】 本规则适用于 ZDZL OJ 的各项功能。包括讨论、题目、比赛、站内消息、我的文件、作业（暂未开放）及训练（暂未开放）等所有 ZDZL OJ 支持的用户交互模块。以及账户、评测等基础功能。 第三条【基本原则】 遵纪守法： 任何违反国家法律法规的行为在 ZDZL OJ 绝对禁止。 尊重友善： 尽量保持包容，避免人身攻击或辱骂等不友善的行为。 学术诚信： 抵制抄袭、作弊等违背学术诚信的行为。 第二章 处罚种类与适用 第四条【处罚种类】 违反本规则的用户，视违规类型和情节严重程度，将受到以下处罚： * 警告：由管理员发送站内消息警告。 * 禁言：不允许在公共区域发言 * 禁止使用讨论：无法查看讨论。 * 禁止站内消息：无法发送站内消息。 * 禁止查看他人评测：无法查看他人评测。 * 封禁账户：无法登录。 * 其他为制止违规、恢复秩序所的管理措施。 第五条【处罚期限规则】 * 如未明确表明处罚时间的非封禁账户的处罚，默认期限为 30 个自然日。 * 封禁账户默认期限为 60 个自然日。 * 各项处罚如在执行时有限定具体处罚时间的，以限定时间为准。 * 严重的违规行为会导致永久封禁。 第六条【连带处罚】 若用户使用自己的多个账号之一故意违规，或者被罚后开设或使用其他账户绕过处罚，将对该用户所有账户追加同等或更重处罚；多次试图绕过处罚者，永久封禁其所有及未来注册的新账户。 第三章 违规行为与量罚细则 第七条【一般扰乱秩序行为】 用户在讨论区域有下列行为的，处以警告、禁言或禁止使用讨论；在站内消息下列行为的，处以禁止站内消息。 * 发布夺人眼球、哗众取宠、令人反感或恶作剧的内容； * 短时间内 5 次以上发布、回复无意义内容； * 发表辱骂、歧视、人身攻击等不友善内容，或泄露他人隐私； * 讨论轻微涉政、**、低俗等敏感话题； * 在讨论区或站内消息中，发布未经许可发布 ZDZL OJ 站外广告，或宣传非公开比赛。 对于特别严重的违规，可能处以永久性的处罚。 第八条【严重扰乱秩序行为】 有下列行为之一，严重扰乱社区或管理秩序的，处以封禁账户： * 发表违反法律法规、反动言论、政治梗，或讨论及影射国家机关及相关人物； * 严重违反社会公德，造成恶劣影响； * 多次实施违规行为，或警告后仍然实施违规行为； * 辱骂管理员或志愿者； * 其他严重违反《ZDZL OJ 用户规则》、损害 ZDZL OJ 利益的行为。 对于特别严重的违规，可能处以永久封禁的处罚。 第九条【一般违背学术诚信】 有下列行为之一的，处以警告或禁止查看他人评测： * 评测时大量提交抄袭他人的代码或者 AI 生成的代码； * 违反公开比赛参赛规则； * 提交题解含有抄袭内容。 第十条【严重破坏学术诚信】 有下列行为之一的，处以封禁账户： * 提交卡评测代码，或大量提交无意义的代码； * 评测时大量提交抄袭他人的代码或者 AI 生成的代码，或者之前已经被处罚或警告，仍然提交抄袭他人的代码或者 AI 生成的代码； * 多次违反公开比赛参赛规则； * 多次【一般违背学术诚信】的； * 多次将明显不符合《公开比赛规范及要求》的低质量比赛提交公开赛审核，经警告后未改正； 第十一条【违规文件】 * 用户上传严重违规的文件，包括但不限于涉黄、涉政（如**）、血腥的，直接处以封禁账户。 第十二条【个人信息及其他账号违规】 * 头像、签名等包含违法、不良内容，或冒充官方、政要、名人的，处警告或封禁账户，并强制修改信息。 * 针对用户的处罚均以实际作出违规行为的账户为准。如果账户被他人使用，则账户的主人承担该账户下的一切违规责任。若有证据表明其他用户实施了盗用他人账户的行为，也可同时处罚实施盗用账户行为的用户。 第四章 处罚流程 第十四条【违规行为的举报】 * 用户发现其他用户的违规行为的，可以发送站内消息给管理员或发送邮件至 zdzloj_shensu@163.com 进行举报（站内消息发送请尽量发送给 uid=4 的管理员）； * 用户在管理员发现其违规行为之前自首坦白自己的违规行为，可以从轻、减轻或免除处罚。 * 对于多次违规后的“投机式”自首，管理员有权拒绝从宽处理。 第十五条【违规行为的处置】 * 对违规内容，管理员可以立即删除或者采取其他必要处置措施。 * 处罚决定由站长或者管理员作出。除不宜公开的情形外，处罚信息将在固定的帖子中公开。 第十六条【申诉权利与时效】 * 用户对处罚有异议的，有权在处罚作出后一周内提出申诉。用户通过邮箱 zdzloj_shensu@163.com 提交。管理组将在收到申诉后一周内给出加重、维持或撤销原处罚的决定。 第五章 处罚解除 第十七条【解除条件与前置评估】 * 当用户满足期满解除、手写检讨解除等条件时，可通过发送邮件申请解除处罚。申请时必须提供理由，并声明保证已阅读且遵守《ZDZL OJ 用户规则》。 * 管理组将在 7 天内评估。若判定用户不会再犯，则解除处罚（可能不另行通知）；若判定认错态度不佳、大概率继续违规，或发现检讨存在虚假、非手写、AI生成等行为可能不予处理直接忽略。 * 多次提交失败的解封申请 ZDZL OJ 可能不再接受对应账号的解封申请。 第十八条【处罚解除渠道】 * 申请解除处罚（包括期满解封、提前解封等），应当提交发送邮件至 zdzloj_shensu@163.com。管理员会在 7 个自然日以内处理或直接忽略。 第十九条【期满解除】 * 任何处罚需要在处罚期满后，由用户主动发送邮件至 zdzloj_shensu@163.com 申请解除。 第二十条【手写书面检讨解除】 * 检讨内容需包含：事情的起因经过、造成的不良影响、今后改进措施。 * 手写书面检讨应当是手写，用笔写在纸上，通过邮箱提交拍照或扫描件。无条件者可用鼠标在画图工具手写。严禁使用 AI 或计算机生成的文字/图片，违者驳回并加重处罚。 第六章 附则 第二十一条【数量的定义】 * “以上”、“以下”均包含本数； * “多次”为 3 次以上； * “大量”为 15 次以上。 第二十二条【规则效力】 除本规则外，用户还应自觉遵守如下规则和规范： * ZDZL OJ 申请举办公开比赛相关规范及要求 * ZDZL OJ 公开赛参赛规则 如果专项规则对处罚规定更加明确的，以专项规则为准。 第二十二条【特别裁量权】 对于本规则未尽事宜，或存在特殊、重大情形的事件，经社区管理组集体讨论并报请站长批准后，管理组可以行使特别裁量权，不受本规则具体量罚标准与解封条款的限制，视具体情况予以从轻、减轻、免除或从重、加重处罚。 第二十三条【生效时间】 本规则在 2026/6/6 开始实行。

关于我在豆包上搜堵开学事件大 开 眼 界

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这是我搜豆包的图 神奇 我就想问他说的哪件事是真的？！？！？！？！ 《提议不上线、不刷题》 《刷****词语》 《用AC数量堵住开学》 不是 这个贴不是说用fu mu堵住吗？？？ 何意味没一条真的 《满屏堵开学》一小时内上千条回复倒是真的，但是其实满屏都是骂 《花似雪、几名大佬用户也发》花似雪早就退了，而且“几名大佬发”是何意味 《冲到第一盖过欢乐赛》冲到榜一倒是不假，但是欢乐赛是什么鬼，难道说神秘的欢乐赛题解百年一遇的上榜了？没有吧 还有很多地方我不想说了，主要是这鬼畜玩意能不能依据事实啊…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 神秘艾特环节（输入“@”以后随便按的） @请输入文本. @景梓萌（看猴常@） @吐司喵喵 @tomyyf @༺ད黯渊◈天蝎ཌ༻ @༺ཌༀཉི༒SSCD刹༒༃ༀད༻ @烟火 @凌霄戍卫(一只焉民)(六一快乐)

谁是你的梦中情站！！！！！！！！！！！！

关注我一下，谢谢 --------------------------------------------------正文开始--------------------------------------------------------- 打个广告 打个广告2 1.游戏网站 poki(在小码王里用不了！！！555) Free Online Games on CrazyGames | Play Now!(这个可以用！！！happy这个老权威了) bloxd（和MC差不多，游戏多一点） florr（和zorr差不多） digdig(解压) zorr（和florr差不多） 4399(老游戏了) 360（还行吧） PCL 正版MC（非常牛B） 跑酷 跑酷2 空调(解压) 枪战 一些game 你画我猜 枪战游戏 海战 恐龙跳跳 领地 马里奥 2.学习网站 acgo本go 小码王本王 小白板 打字 洛谷 NOI GESP&&CCF 3.看视频的网站 抖音 哔哩哔哩 4.游戏下载 王者 taptap(在这里有很多游戏)

深高北-贪心算法

贪心算法笔记（C++版） 一句话理解 > 贪心算法：每一步都选当前看起来最优的选择，不管以后会怎样。 就像吃自助餐——每次只拿最贵的菜，最后不一定吃得最爽，但在某些问题上这就是最优解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、什么是贪心算法？ 贪心算法：在每一步都做出当前状态下最好的选择，希望通过局部最优达到全局最优。 核心思想：只看眼前，不回头，不后悔。 特点： * 步骤简单，容易想 * 不一定每次都对（需要证明贪心是正确的） * 一旦正确，效率很高 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、贪心算法的基本框架 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、经典题目 题目1：活动安排（选最多的活动） 题目描述：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。同一个时间只能参加一个活动，问最多能参加几个活动。 贪心策略：按结束时间从小到大排序，每次选结束最早的、且不冲突的活动。 输入样例： 输出样例： 为什么按结束时间选是对的？：结束越早，留给后面的时间越多。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目2：排队接水（平均等待时间最小） 题目描述：有 n 个人接水，第 i 个人接水需要 t[i] 分钟。问怎样排队能使所有人的平均等待时间最小？输出总等待时间。 贪心策略：按接水时间从小到大排队。 输入样例： 输出样例： （等待时间 = 0 + 3 + (3+1) + (3+1+4) + (3+1+4+2) = 0+3+4+8+5=20） 为什么按接水时间排序是对的？：用时短的人先接水，后面的人等得更少。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目3：找零钱（用最少硬币） 题目描述：有 1 元、5 元、10 元、20 元、50 元、100 元的硬币无限个。要支付 M 元，问最少需要多少硬币。 贪心策略：先用最大面额的硬币，不够再用小面额。 输入样例： 输出样例： （100+50+10+5+2+1？不对，这是金额。注意：M=168时：100元1个+50元1个+10元1个+5元1个+1元3个？等等算错了。100+50=150，差18，10元1个=160，差8，5元1个=165，差3，1元3个=168。一共1+1+1+1+3=7个。） 注意：这种贪心在人民币面额下是对的（因为每种面额都是更大面额的约数）。如果不是这种面额（比如1,3,4元，要付6元，贪心会选4+1+1=3个，但最优是3+3=2个），贪心不一定对。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、贪心的正确性 贪心算法不一定总是对的！使用前需要判断： 情况 说明 适用 问题有“贪心选择性质”（局部最优能推出全局最优） 不适用 当前选择会影响后面的选择 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、贪心 VS 其他算法 对比 贪心 动态规划 枚举 思路 每步选最优 考虑所有可能 全部试一遍 时间复杂度 通常 O(n log n) O(n²) 或更高 可能很高 正确性 需要证明 一定正确 一定正确 适用场景 有贪心性质的问题 最优化问题 数据范围小 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、贪心常见题型 题型 贪心策略 活动安排 按结束时间排序 排队问题 按时间排序 区间选点 按右端点排序 删数问题 找第一个下降点删除 找零钱 用最大面额（特定面额下） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、总结 要点 内容 核心思想 每步都选当前最好的 优点 简单、高效 缺点 不一定正确 使用前 证明或确认贪心是正确的 经典应用 活动安排 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 记忆口诀 > 贪心每步选最好，局部最优不烦恼 > 活动安排按结束，排队接水按时长 > 用前必须想清楚，贪心性质要记牢 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#创作计划 浅谈高级数据结构

吉司机线段树/历史最值 (ps：之前写过线段树总结，现在觉得这块内容放这个板块较为合适。) 很久以前用一知半解态度过的模板题，现在重新学习了下，不算难。 我的文章风格可能都有点刨根问底的感觉，理解的层次至少会阐述正确性（而不是说做法然后直接放代码）。 阅读门槛是需要知道线段树，标记合并。其实很低，如果势能分析看不懂也没关系。 PART1 区间最值操作 吉司机这个东西是可以在对数平方时间内维护区间最值修改的，操作如同： * 对 [l,r][l,r][l,r] 中的所有数执行 ai→min⁡(ai,k)a_i \to \min(a_i,k)ai →min(ai ,k)，其中 kkk 是给定常数。 当然上面的 min⁡\minmin 换成 max⁡\maxmax 也是完全可以的，我们先来阐明一下解决思路，再考虑时间复杂度的具体分析。 针对取 min⁡\minmin 操作进行讨论，另外的取 max⁡\maxmax 操作是完全对称的。在此基础上如果只需要查询最值则可以简单做到 O(nlog⁡n)O(n \log n)O(nlogn)，但这只是单纯的利用最值标记实现的简单线段树，并不是我们今天所讨论问题。所以，我们同时还需要支持查询区间总和等相关问题。 我们先明白查总和相对查最值更难做的原因，其实在于总和信息和取最值是没有结合律等优良性质的，刚刚所谈论的最值好做是因为操作和查询本身就支持信息合并。 更简单的说，单次修改中总和的修改量不能快速通过标记合并快速维护。所以我们必须考虑转化问题，这是线段树维护复杂信息的常见思路。本质在于让原问题变成更常见的问题，然后就可以很轻松地处理原问题。 一个简单的优化是跳过最大值小于等于 kkk 的节点，然而是不好直接做修改的。将问题转化为最小值大于等于 kkk 就做区间推平，特判叶子节点的想法。其实是完全不行的，因为最坏情况所有区间叶子都会被修改一次，修改总量完全没有保证，和暴力没有本质不同。所以我们需要做一个相对合理的批量修改方法。 换另一个可能更好的想法：维护最大值 maxnmaxnmaxn，最大值个数 cntcntcnt，严格次大值 sesese。修改的时候同样跳过最大值小于等于 kkk 的节点，并且当可以修改的节点满足 se<k≤maxnse < k \le maxnse<k≤maxn 就直接打删除标记 mul=k−maxnmul = k-maxnmul=k−maxn。这里表示将最大值区间加 mulmulmul，实际上效果相当于把最大值改成 kkk。维护一个标记 tagxtag_xtagx 表示当前节点 xxx 的最大值需要加多少就可以了，更新总和的时候贡献就是 tagx∗cnttag_x * cnttagx ∗cnt。 这里其实我们可以发现一件事情：最大值被单独列出维护了一个标记。这意味着如果还需要支持其他操作：比如区间加。则我们必须要维护两套标记：一个是针对最大值的，一个是针对除最大值以外的所有数。 其实底层原因也很简单，就是因为最大值对于的区间加标记不会作用于其它数上，就导致最大值所需要考虑的信息更多，当然如果这些信息不会影响到某种标记合并也可以分开维护。 首先考虑两个问题：答案正确性和时间复杂度分析。答案的正确性是比较显然的，接下来考虑时间复杂度的分析。这里其实直接分析单次修改是很容易绕弯子的，事实上证明用了一个高级技巧：势能分析。 在这里我会尽量用文字阐述下证明思路和过程，这里我们引入一个概念函数 W(u)W(u)W(u)，其满足以下性质： * 当节点 uuu 的最大值不等于其父亲节点的最大值时，有 W(u)=1W(u) = 1W(u)=1。 * 否则都有 W(u)=0W(u) = 0W(u)=0。 因为我们访问节点 uuu 需要的代价实际上是还需要考虑深度，换句话说总势能在 O(nlog⁡n)O(n \log n)O(nlogn) 量级，也就是 ∑W(x)×depx\sum W(x) \times dep_x∑W(x)×depx ，这里一个节点的深度可以粗略的看做 log⁡n\log nlogn。 然后我们考虑分析修改操作对势能总和的相对影响，这个所谓的势能实际上可以简单认为它等于程序总运行次数（也就是时间复杂度总量）。 至于根本原因，完全可以这样理解： * 考虑一个节点 xxx 满足 W(x)=0W(x) = 0W(x)=0，我们发现此时必然满足 maxnx<maxnfxmaxn_x<maxn_{f_x}maxnx <maxnfx ，此时 maxnxmaxn_xmaxnx 只能贡献到 sefxse_{f_x}sefx 。又因为此时暴力递归必有 sefx<kse_{f_x} < ksefx <k，所以我们知道 xxx 这个节点不可能会被暴力递归访问到，访问它的时间复杂度是 O(log⁡n)O(\log n)O(logn) 级别的，所以我们就依据这个性质设计势能函数值为 W(x)×depxW(x) \times dep_xW(x)×depx 。 同时，只需要聚焦于因为值域问题暴力递归处理节点的情况。其他情况就是普通线段树的时间复杂度。 回到势能分析中，当节点 xxx 的次大值 sesese 大于等于 kkk 时，我们显然有： * 两个子节点 lsxls_xlsx 和 rsxrs_xrsx 的最大值一定大于等于 kkk。 * 其中一定有一个孩子（不妨设为 rsxrs_xrsx ）的最大值小于 xxx 的最大值，否则如果两个子节点最大值都等于 maxnxmaxn_xmaxnx ，则次大值不可能 ≥k\ge k≥k。除非子树内有更深的分裂，这会在继续递归的儿子中被讨论，这里直接认为就是满足条件的。 当我们在该子树执行完操作并向上回溯后： * lsxls_xlsx 和 rsxrs_xrsx 的最大值由于被 kkk 截断，现在全部变成了 kkk。 * 父亲节点 xxx 的最大值也更新为 kkk。 * 此时，由于 maxnrsx=maxnx=kmaxn_{rs_x} = maxn_{x} = kmaxnrsx =maxnx =k，原本不相等的最大值现在对齐了。于是，W(rsx)W(rs_x)W(rsx ) 从 111 变成了 000。 势能减少了，严格来说减小的势能实际上是 deprsx=depx+1dep_{rs_x} = dep_x+1deprsx =depx +1。 由于 xxx 是暴力递归节点，虽然我们在当前层花费了 O(1)O(1)O(1) 的常数时间，但我们成功让一个深度为 depx+1dep_x+1depx +1 的节点的 WWW 归零，释放了 depx+1dep_x+1depx +1 的势能。同时也可以通过这个方面说明每一次暴力递归都可以在后续递归中找到某个节点，让它势能 WWW 归零来为时间复杂度的开销买单。 同时还需要分析区间加操作带来的势能变化，一共会拆成 log⁡\loglog 个节点，最坏情况下每个节点 xxx 的父亲 fxf_xfx 的另一个儿子的势能由 000 变成 111，总变化量量级至多为 O(qlog⁡2n)O(q \log ^2 n)O(qlog2n)。并且加标记下传不会影响势能 WWW 变化，增减势能的情况就上面两种。 势能总量为 O((n+q)log⁡2n)O((n+q) \log^2 n)O((n+q)log2n) 量级，单次操作会增加或消耗 O(log⁡2n)O(\log ^2 n)O(log2n) 的势能，总时间复杂度自然为 O((n+q)log⁡2n)O((n+q) \log ^2 n)O((n+q)log2n)。 当时吉老师的论文如果我没记错的话是修改的势能分析错判为 O(log⁡n)O(\log n)O(logn)，并且其实势能增量卡慢其实不简单，所以实际表现和常数大一点的 O(nlog⁡n)O(n \log n)O(nlogn) 没什么区别。 PART2 历史最值 这块部分严格来说和最值修改完全没关系，一个位置的历史最值的定义是该位置上的数在所有时刻中的最值。相对吉司机要简单很多。 同样的，我们考虑历史最大值的做法，记 AiA_iAi 表示当前时刻位置 iii 上的值，BiB_iBi 表示所有时刻位置 iii 的最大值。实际上我们是在维护的历史最大值可以看做一个前缀时间内数的最大值。 首先我们要维护的区间历史最值显然只会被区间最大值更新，换到线段树上就是考虑标记的合并与迭代。只维护加标记 tag1tag_1tag1 的想法是错误的，原因在于标记可能经过多次合并，实际意义就是加了很多次数。我们一定会考虑维护 tag1tag1tag1 的历史最大值，记作 tag2tag2tag2,用它来更新答案。 由于标记下传后贡献已经清除，所以本质上我们只是在维护： * tag1tag1tag1 表示上一次下传标记后到现在的加标记。 * tag2tag2tag2 表示上一次下传标记后到现在的时刻中，tag1tag_1tag1 的最大值。 同时记最大值为 m1m_1m1 ，历史最大值为 m2m_2m2 。考虑下传节点 xxx 的标记： * tag1sonx→tag1sonx+tag1xtag1_{son_x} \to tag1_{son_x} + tag1_xtag1sonx →tag1sonx +tag1x ，加标记合并。 * tag2sonx→max⁡(tag2sonx,tag2x+tag1sonx)tag2_{son_x} \to \max(tag2_{son_x},tag2_x+tag1_{son_x})tag2sonx →max(tag2sonx ,tag2x +tag1sonx )，理由很简单，此时 xxx 标记对 sonxson_xsonx 的影响在于 tag1xtag1_xtag1x ，而由于我们维护的 tag1xtag1_xtag1x 实际上是一个时间点的加标记，换句话说是落在该节点的加操作之和。本质上我们应该遇到一个操作就直接下传儿子修改，但是为了复杂度我们选择了延迟下传，所以就会选择使用 tag2xtag2_xtag2x 更新。正确性只需要考虑 tag2xtag2_xtag2x 合法（一定是某个时刻的 tag1xtag1_xtag1x ）并且最优（根据定义它最大）。 然后依据历史最大值标记的最大贡献 tag2x+m1(x)tag2_x+m1(x)tag2x +m1(x) 取更新 sonxson_xsonx 的 m2m_2m2 即可。整个过程的设计思路比较自然。 PART 3 结合问题 模版题把两个问题合并在了一起，实际上做法还是依据上述思路维护线段树信息，之前在第一部分我也顺便提到过：由于吉司机把最大值单独考虑，所以要针对最大值和非最大值设计两种标记组。 什么意思，就是实际上我们需要维护四个标记 tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4，但是其实是因为 tag1,tag2tag1,tag2tag1,tag2 服务于区间最大值（定义同第二部分），其余的 tag3,tag4tag3,tag4tag3,tag4 服务于其余所有数，本质上只是迫不得已维护了两套一模一样的标记而已。 这段代码是在处理节点 xxx 加入的四个标记分别为 v1,v2,v3,v4v1,v2,v3,v4v1,v2,v3,v4 后的影响。首先更新和，考虑最大值个数和其余数个数（里面 clenxclen_xclenx 是节点 xxx 代表的线段树区间长度）和标记组合即可。剩下的都是刚刚推导里面就有的，注意这里需要判断次大值是否存在的情况。 然后考虑标记下传函数： 这段代码考虑了 W(sonx)W(son_x)W(sonx ) 的情况，也就是说我们需要考虑某个儿子的最大值是不是节点 xxx 的最大值，如果不是则不需要考虑最大值标记信息不同带来的影响。因为下传的 tagtagtag 是以节点 xxx 的视角设计的，下传到 sonxson_xsonx 需要变换成 sonxson_xsonx 的视角，也就是说如果 sonxson_xsonx 本身对最大值没贡献则会被自动规约到 tag3x,tag4xtag3_x,tag4_xtag3x ,tag4x 的管辖范围。 关键代码如下： 当然如果操作需要支持取最大值或者最小值，维护思路完全一样。但是值得注意的一点是注意特判重复贡献。理论上维护三套标记的话其中两套分别是为最大值和最小值服务的，但是如果一个数同时是最大值和最小值需要特别判断。除此之外，也需要考虑最大值同时是次小值，最小值同时是次大值的情况（不然非最值标记会重复贡献）。 总而言之这是一个相对高级的线段树技巧，但是理解起来也不是特别困难。

官方题解 | 巅峰赛#34

巅峰赛34题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的宝石容器 普及− T2 午枫的城市路线 普及/提高− T3 午枫的对称字符 普及/提高− T4 午枫的小队评分 普及/提高− T5 午枫的平衡调整 普及/提高− T6 午枫的路线封闭 普及+/提高 T1 午枫的宝石容器 题目大意 有 nnn 颗宝石，大小为 AiA_iAi ，以及 n−1n-1n−1 个容器，容量为 BiB_iBi 。现在可以额外购买一个容量为 xxx 的容器，使得总共有 nnn 个容器。要求每个容器最多放一颗宝石，且宝石大小不超过容器容量。求最小的 xxx 使得所有宝石都能放入容器中，若无法实现输出 −1-1−1。 题解思路 贪心匹配即可。为了尽量让大的宝石优先匹配大的容器，先将宝石数组 aaa 和容器数组 bbb 都按从大到小排序。 然后用双指针从大到小匹配：指针 iii 枚举宝石，指针 jjj 枚举容器。如果当前宝石 ai≤bja_i \le b_jai ≤bj ，说明可以用这个容器装下，指针 jjj 向后移动；否则说明当前宝石无法被任何已有容器容纳，只能依赖新买的容器，于是记录这个宝石。 统计这种“装不下”的宝石个数： * 如果为 000，说明原有容器已经够用，此时新容器可以取最小值，即 ana_nan ； * 如果为 111，说明只有一个宝石需要新容器，答案就是这个宝石的大小； * 如果超过 111，说明至少有两个宝石需要新容器，但我们只能买一个，因此无解。 这个贪心是正确的，因为总是优先让大宝石匹配大容器，可以保证不会浪费容量。 时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。 参考代码 T2 午枫的城市路线 题目大意 给定一张有向图，从节点 111 出发，问是否存在一条路径可以回到节点 111（即形成一个包含 111 的环）。如果存在，求这样的路径中边数最少的一条长度；否则输出 −1-1−1。 题解思路 由于所有边权为 111，要求最短路径，直接使用 BFS。 从节点 111 出发进行广度优先搜索，用数组 d[i]d[i]d[i] 记录从 111 到达节点 iii 的最短距离。每次从队列中取出一个节点，遍历它的所有出边，如果某个节点还没访问过，就更新距离并入队。 在 BFS 过程中，如果某条边可以从当前节点走回 111，那么就找到了一个回环，其长度就是当前节点的距离加 111。由于 BFS 按层扩展，第一个找到的回环一定是最短的。 如果最终没有办法回到 111，说明不存在这样的路径，输出 −1-1−1。 时间复杂度为 O(n+m)O(n+m)O(n+m)。 参考代码 T3 午枫的对称字符 题意简述 给定一个仅由大写英文字母组成的字符串 SSS，要求计算三元组 (i,j,k)(i,j,k)(i,j,k) 的数量，使得 1≤i<j<k≤∣S∣1 \le i < j < k \le |S|1≤i<j<k≤∣S∣ 且 SiSjSkS_iS_jS_kSi Sj Sk 是回文串。由于长度为 333 的回文串唯一的条件是首尾字符相同，即 Si=SkS_i = S_kSi =Sk ，中间字符可以是任意字符，因此本题实质上就是统计所有首尾字符相同的三元组数量。 解题思路 可以采用前缀计数的方法，遍历字符串时维护一个数组记录每个字母已经出现的次数，同时维护一个数组记录以每个字母为首字符的可形成组合数量。在遍历每个字符作为中间字符时，将当前字符对应的组合数量累加到结果中，然后更新以每个字母为首字符的组合数量，最后更新当前字符的出现次数。这样就能在一次遍历中统计出所有满足条件的三元组，时间复杂度为 O(n⋅26)O(n \cdot 26)O(n⋅26)，空间复杂度为 O(26)O(26)O(26)，足够应对 ∣S∣≤2×105|S| \le 2 \times 10^5∣S∣≤2×105 的情况。 参考代码 T4 午枫的小队评分 题意简述 有 NNN 名选手，每位选手都有实力值 AiA_iAi 和消耗值 BiB_iBi 。需要从中选出一个大小为 KKK 的小队 SSS，小队评分定义为： score(S)=(max⁡i∈SAi)×(∑i∈SBi)\text{score}(S) = \left(\max_{i \in S} A_i\right) \times \left(\sum_{i \in S} B_i\right) score(S)=(i∈Smax Ai )×(i∈S∑ Bi ) 目标是选择一个小队，使得评分尽可能小，并输出最小评分。 解题思路 首先将选手按照实力值 AiA_iAi 从小到大排序。然后考虑当某个选手 iii 的实力值成为小队中最大实力值时，如何选择另外 K−1K-1K−1 名选手以使得消耗值之和最小。为了高效计算，可以使用一个大根堆维护当前已选择的 K−1K-1K−1 个消耗值最大的选手，如果当前堆中超过 K−1K-1K−1 个元素，就弹出最大的，这样保证堆中始终保存消耗值最小的 K−1K-1K−1 个候选成员。每遍历一个选手，将其作为最大实力值候选时，累加堆中消耗值与自身消耗值，然后计算评分并更新最小值。这样遍历一次即可得到最优解，时间复杂度为 O(Nlog⁡K)O(N \log K)O(NlogK)，空间复杂度为 O(K)O(K)O(K)。 参考代码 T5 午枫的平衡调整 题意简述 给定 NNN 名成员，每名成员属于三个小组之一并有一个贡献值。希望通过调整部分成员的小组归属，使得三个小组的总贡献值完全相等。每次调整只能将某个成员移动到另一个已有的小组中，目标是判断是否可以实现平衡，如果可以，则输出最少需要调整的人数，否则输出 −1-1−1。 解题思路 首先计算所有成员贡献值之和，如果不能被 333 整除，则无法实现平衡，直接输出 −1-1−1。设每组的目标贡献值为总和的三分之一。使用三维动态规划，状态为 dp[i][j][k]dp[i][j][k]dp[i][j][k]，表示前 iii 个成员中，第一组总贡献为 jjj，第二组总贡献为 kkk 时所需的最少调整人数。遍历每个成员时，可以选择将其分配到任意一组，累加调整次数（若成员当前组与选择组不同则加一），更新状态。最终 dp[N][target][target]dp[N][target][target]dp[N][target][target] 即为最少调整人数，如果无法达到则为无穷大，输出 -1。 参考代码 T6 午枫的路线封闭 题意简述 给定 NNN 个地点和 MMM 条双向路线，每条路线有通行代价。随后有 QQQ 个操作，包含封闭某条路线或询问两点间最小通行代价。封闭操作总次数不超过 300300300。要求按操作顺序处理，每次询问输出当前未封闭路线下的最短路径，若无法到达输出 −1-1−1。 解题思路 由于地点数量 N≤300N \le 300N≤300，可以使用 Floyd 算法处理所有点对最短路径。关键是封闭操作较少，因此可以采用离线处理策略：先将所有封闭操作标记，并从最终状态的图出发，计算全局最短路径。然后逆序处理操作序列，每遇到一次封闭操作就“恢复”对应边，并更新受影响的最短路径；遇到查询操作直接读取当前最短路径表即可。这样只需在逆序处理时更新路径，而不必每次从头计算，保证在 O(N3+Q)O(N^3 + Q)O(N3+Q) 时间内完成。最终按正序输出查询结果即可。 参考代码

我哥的画风VS我的画风

我 可爱的小猫咪~ 我哥（不用担心因为他是一只臭福瑞控，就是那种卡哇伊唐到爆的，） 链接描述 链接描述