XP（三系统，内测）

关于我一不小心发了4200个罐头

如题所示，我这一生如履薄冰，还是不小心操作失误，给嘻哈赛第10期的前200名同学发了4200个罐头（本来应该是平分的），被通知竟然无法撤回，请同学们好好对待这笔横财，如果还有下期，我一定不会发错了 所以有时间参加嘻哈赛的同学欢迎每期参加

社区现状

活动具体可参考活动规则 社区现状： 一、 首先是用户，以下为法兰西玫瑰一事总结：<法兰西他本身就是抄的样例，按理说道歉就算了，还以盗号这种非常扯淡的借口来掩盖自己的罪过。然后是粉丝，没有眼睛看是非就算了，还瞎掺和，公然为他辩护。关键在于粉丝们为了面子放弃原则，公然与敢说真话者对骂。然后就是骂到2024，有人摆证据，徐建博退站，事件平息。>一只姜退站以后，社区风气就不好了。法兰西事件后，一只姜退了，虽然她口吐芬芳（2024.8.23）。之前她会主动去核对代码、抓 AI 刷题造假，哪怕手段有争议，但确实震慑了一批刷榜的人。她一走，没有其他人专门花大量精力深度核查代码，AI 抄题、套题、刷榜单的行为慢慢变多。 二、 如果官方一直不做强 AI 代码检测，榜单造假持续泛滥，认真学信息学的学生会慢慢转移到其他平台，社区人气持续流失。《救狗救 ACGO》《Deep 变法》这些帖子，本质就是用户看到这个趋势，提出自救方案，但是官方并没有大规模采纳。 三、 @Deep欠揍 | 深度欠揍 @star_best他们的变法是基于ACGO现状的补救措施，就比如Deep革命——救救ACGO，针对了社区问题进行改革。还有就是救狗救ACGO，和Deep革命一样，高质量。但是官方并未采纳。这说明什么？现在的社区不想自救。虽然官方曾经把《救狗救ACGO》这条帖子上榜，但是他并未理睬。 四、 你要知道如果趋势发展下去，ACGO的用户就只有小码王学员了。但别想着变法，官方理都不会理，即便你的改革天衣无缝。官方非常懒，不会改的。所以变法，根本，没用！

我天，管理员竞赛给我发了4200个罐头！

我的小号报了ACGO嘻哈赛#10，然后大号报不了了（不是点不了，竞赛说明里确说了多账号禁止，每位选手仅限使用一个账号参赛，一经发现，取消本次奖励，并视情节予以禁言或封号处理）写完题后🧠有点烦，毕竟竞赛分是加在小号上。等竞赛结束了终于收到了加罐头的通知，结果，不看不知道，一看吓一跳，下面就是我看到的内容： 管理员竟然给我发了4200个罐头！ 原本我还是不相信的，去罐头商城里看了加罐头的记录，又一次被吓到了 是真的！！！ 然后，我就拿这些罐头买了39个空间扩容卡，全充团里了，加上以前换的一些，就有这么多空间了 难不成，今天是我的幸运日？？？ 后续： 得知真相的我十分感激朱老师，希望他下次手再抖一点，每人发8888个罐头 榜三了？？！ 榜二？！！

我体育会不会完蛋

坐位体前屈，一只手，有人帮忙压，极限-5 一般两只手，没人压，-10左右 800m，只有1m是快的，其它路程不比走路快多少，我还跑的累死 学校没操场，绕教学楼跑 排球垫球莫名的，最近只能垫到20几个 50米14秒，我果然是区 我仰卧起坐为什么是13个，我为什么跟区一样蠕动 为什么我才1.58 我为什么是53公斤左右啊 我班里有个23公斤的，还有赵一鸣(假名)是110.7公斤 我肺活量感觉不错，3628 我立定跳远145 https://www.acgo.cn/discuss/rest/96560 精心编辑，25年11月/12月首发

大师主宰级团队 · 改名投票（第一阶段）

大师主宰级团队现启动更名，本次为第一阶段初筛。以下候选名分为两类：纯字母名（4—5 字母、全大写、无中文名）与英文名 + 中文名组合。请投票选出你最支持的一个，票数靠前者进入下一阶段。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、纯字母名 选项 名称 字母数 含义说明 A APEX 4 顶点、顶尖，暗含大师义，兼有“居于顶端”的主宰感。极短好记。 B PRIME 5 首要、第一、顶尖，同时压“大师（顶尖）”与“主宰（首要）”。干净、通用。 C ARCHS 5 Archon 的缩写变体，保留“主宰 + 大师”内核，更短更利落。 D ARCHI 5 Archon / Architect 的词根，含“主导、建造秩序”的意味。 E VIRTU 5 取自 virtuoso（大师、名家），字面不出现 master，偏文气。 F SOVRA 5 Sovereign 的变体缩写，保留“主宰”的发音骨架，字面规避直译。 G KORON 5 取 crown（王冠、主宰）的变体拼写，暗含“加冕者”的大师义。 H REGIS 5 拉丁语“王者、统治者”，压主宰义；王者在技艺上亦称大师。 I NOBIL 5 拉丁语 nobilis（卓越、高贵）的缩写，暗含大师的卓越义与主宰的高位感。 J ZSZL 4 取自“宗师执政”拼音首字母，字面不出现禁词。 K ARCN 4 ARCHON 去元音缩写，保留“执政官（主宰）+ 精通者（大师）”内核，像技术代号。 L VRTU 4 VIRTU 的变体，取 virtuoso 词干，短、冷、像代号。 M PRIM 4 PRIME 去尾字母，保留“首要/顶尖”双义（大师 + 主宰）。 N SOVR 4 SOVRA 再缩一档，保留 Sovereign 发音骨架。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、英文名 + 中文名组合 选项 英文名 中文名 含义说明 O ARCHON 宗师执政联盟 6 字母 + 6 字。ARCHON = 古希腊执政官，兼含“统治者（主宰）”与“精通治理者（大师）”；宗师接大师，执政接主宰，联盟接社群。中英一一对应。 P PRIME 首席执政团 5 字母 + 5 字。PRIME = 首要、第一，压大师与主宰双义；“首席”接大师，“执政”接主宰，“团”接社群。短促有力。 Q APEX 巅峰执掌社 4 字母 + 5 字。APEX = 顶点、顶尖；“巅峰”接大师，“执掌”接主宰，“社”接社群。轻快好记。 R REGIS 王者宗师盟 5 字母 + 5 字。REGIS = 拉丁语“王者、统治者”；“王者”接主宰，“宗师”接大师，“盟”接社群。古典气质。 S SOVRA 主宰宗师阁 5 字母 + 5 字。SOVRA = Sovereign 变体，保留主宰骨架；“宗师”接大师，“阁”接社群，气质偏文雅。 T VIRTU 名家执政社 5 字母 + 5 字。VIRTU = virtuoso 词干（大师、名家）；“名家”接大师，“执政”接主宰，“社”接社群。 选项U：不改名 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、投票方式 在评论区回复你支持的字母（可多选，但请标出首选）。本阶段截止后统计票数，票数靠前者进入下一阶段。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、后续阶段 * 第一阶段（本次）：候选名初筛，按票数选出前 X（待定） 名。 * 第二阶段：开放新名称投稿 + 第一阶段前 X（待定） 名共同进入终选投票，最终团队名在第二阶段产生。

X的日记

写在前面 老吸说，好的文章离不开日复一日的积累，然而作者的语言组织能力堪比一根成年香蕉，写写日记倒是可以锻炼锻炼文笔，顺便记录一些生活中的琐碎，也方便日后细细品味，因此，以下的所有内容都不含AI的成分，文笔生疏，不喜勿喷 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.23 上午 物理老师我爱你 全校的物理课，我们班进度是最慢的了，可能到了期中考试课都上不完，更别说复习了，肥美的物理老师在每次上课前先花10min散布心灵鸡汤鼓舞士气，5min赞美同学2min赞美自己2min赞美太阳，才开始上课。。请给我一个进度不慢的理由。。 更神的来了，伪善的物理老师口口声声的说着，自己不爱占课，从不占课，却毫不犹豫的停掉了我们仅剩的体育音乐，不是说不能占课，事到如今，不得不占，但是你嘴上说着正义的话，却做着相反的事，是不是有点恶心了，，反思一下自己吧，少说废话，多干正事，这才是别人上的又快又好的诀窍，都是初中生了，不需要你的鸡汤，该怎么学、是否该好好学大家心知肚明，真正不思进取也听不进去，所以几句话根本就改变不了什么 晚上 今天晚自习发生了一件非常恶劣的事，是这样的:当时我和同桌正在与作业进行激烈的斗争，一只苍蝇忽然飞到了我的作业上，呃呃呃我也是心生爱慕了啊用我尊贵的手反复挥动试图将它赶走，可是这只苍蝇不但对我的动作置之不理，还悠哉悠哉的搓起了手和屁股，我一下子就怒了啊，这分明是在挑衅我的权威，于是拿出一张面巾纸啪的一下把他拍在作业本上，同桌深感同情，将它担到了地上。。这时愧疚感油然而生，我赶忙下地查看，那只苍蝇的四肢还在不停的抽动着，还好，它没死，只是刚刚被拍晕了。。 最恶劣的来了，同嘬鬼点子生成中。。。用圆规的尖端残忍的扎进了它的身体，力道刚刚好，没有把他扎死，反而将它提了起来，苍蝇仿佛察觉到了危险，四肢抽动的更剧烈了，无力的挣扎着(这里是地狱吗)。。同嘬就把那只圆规静静的架在桌角，像一只罪恶的艺术品(这里是地狱吗。。。我的心被大大的震撼了，生命不该这样被践踏，更何况杀生不虐生，要么就给个痛快，要么就让它继续活着(作者是圣母)怎么办怎么办，今晚要被苍蝇托梦了，功德-1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.24 饿啊今天早上起来头好晕啊，不会生病了吧，没招了撑着吧还有作业要写呢 下午去上课，不不不这段时间是我一天中状态最差的时候了，头微微发热，可能发烧了，还有点犯恶心，没办法，靠不了任何人，继续撑着，题都不会写了，脑子一片空白，只想快点结束。 晚上 终于熬完了，我爱你们所有人 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.25 真想穿越到小学炸鱼啊，今天突然想起了小学举办的辩论赛，辩题是“少年识得/不识愁滋味”，我是反方，记得正方举了一个例子来反驳我们的观点，大概是一个乡下的孩子从小就很懂事最后考上了某名牌大学，未完待续我爱你们，B不想写了，烂尾了 别急别急，晚上还有很多事 又是索然无味的一天，全天唯一的亮点就是从课外班回家的路上吃了一家路边摊，味道不错，服务到位，五星好评👍，图待会放。。 回去的时候看到这一幕:一群熊孩子推搡着一个穿着充气玩偶的人类(做广告的那种人，大家应该都见过)，这种小孩家长真的该管管，小孩子不懂事很正常，但是家长要尽自己的责任才行，换位思考一下，玩偶里的打工人应该很绝望吧，又热又闷又狭窄，还要时刻保持平衡防摔倒。。。唉

100道题目竞赛

竞赛链接1:100道题目竞赛 PART 1（WECE） 竞赛时间：2026-11-01 00:00 至 2027-02-06 00:00 (时长：97天） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 满分1000分，一题10分，如果作弊1题（不管对还是错）-∞分 此竞赛是码农爱历史的亡语 > 空白团队池：88个 第1名：50个空白团队 第2名：20个空白团队 第3名：10个空白团队 幸运奖8个（500分以上）：1个空白团队 (暂定，2026年10月17日，可截图保存) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 惩罚： 1.如果发现有抄袭 AI/其他人代码 现象，1000年不得参加我团及合作团的所有竞赛，发帖并取消奖励。 2.如果有管理员私自修改题目或公告的，一律取消管理员资格。 3.以上2条想取消的话，需要发帖（不得删除，否则继续惩罚）道歉，不许AI生成，永久放在讨论区即可取消惩罚，但奖励还是取消。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 进度： 一、2026.10.17，已完成100+题编辑，正在筛选中...... ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 练习区(废题，目前有 2\COLOR{GREEN}22 道)： 1.道路监控 2.等比数列求和 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正在修改/编辑中🚧...... ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 其他帖子： 恭喜

有什么小众游戏/圈子让我开开眼吧！！！

防透视###################################################################################################################################################################################################### 入团吗团名：（小众这一块） 芜湖！居然在生日当天上榜了！开心~ 这是我第一次上榜呢

官方题解 | 巅峰赛#39题解

导语 久违的巅峰赛，这次巅峰赛是以Dp和状压作为压轴的，毕竟许多朋友的状压熟练度还有待提升 (笑) 。 以下为题解 目录 题目编号 题目标题 难度 T1 Yuilice 的手工套装 入门 T2 Yuilice 的相册整理 普及- T3 Yuilice 的分批冲印 普及/提高- T4 Yuilice 的打印店 普及+/提高 T5 Yuilice 的小区接送 普及+/提高 T6 Yuilice 的共用设备 普及+/提高 YUILICE 的手工套装 题意简述 有 aaa 张大卡纸和 bbb 张小卡纸，每套手工套装需要一张大卡纸和一张小卡纸。可以把一张大卡纸剪成两张小卡纸，剪过的卡纸不能再当大卡纸使用。求最多能制作多少套。 样例 1 中输入为 5,05,05,0。剪开两张大卡纸后，还剩 333 张大卡纸和 444 张小卡纸，因此可以制作 333 套。样例 2 中小卡纸已经足够，直接使用 222 张大卡纸即可。 解题思路 解题方法 设剪开 xxx 张大卡纸，其中 0≤x≤a0\le x\le a0≤x≤a。操作结束后： * 大卡纸有 a−xa-xa−x 张； * 小卡纸有 b+2xb+2xb+2x 张。 每套需要两种卡纸各一张，所以固定 xxx 时最多制作 min⁡(a−x,b+2x)\min(a-x,b+2x) min(a−x,b+2x) 套。枚举全部合法的 xxx，取最大值即可。 1. 读入 a,ba,ba,b，答案初始为 000。 2. 枚举 x=0,1,…,ax=0,1,\ldots,ax=0,1,…,a。 3. 计算当前值 min⁡(a−x,b+2x)\min(a-x,b+2x)min(a−x,b+2x)，更新答案。 任意一种制作方案都会剪开某个合法数量 xxx 的大卡纸，因此一定会被程序枚举。固定 xxx 后，套数不能超过剩余大卡纸数量，也不能超过小卡纸数量，所以最多是 min⁡(a−x,b+2x)\min(a-x,b+2x)min(a−x,b+2x)；取出这么多张两种卡纸后可以逐套配对，说明这个上限能够达到。 程序枚举了所有可能的 xxx，并取其中最大值，所以得到的正是最优答案。 时间复杂度为 O(a)O(a)O(a)，额外空间复杂度为 O(1)O(1)O(1)。因为 a,b≤106a,b\le10^6a,b≤106，中间数量不超过 3×1063\times10^63×106，使用 int 足够。 * 剪纸后要同时减少大卡纸、增加小卡纸。 * 可以一次都不剪，x=0x=0x=0 必须被枚举。 * 不能直接输出 min⁡(a,b)\min(a,b)min(a,b)，因为剪纸可能增加可制作套数。 部分分 * 测试点 1~10（无额外限制）：枚举裁剪数量即可获得满分。 参考代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ YUILICE 的相册整理 题意简述 有 nnn 张照片，日期为 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 。如果 ai>ai+1a_i>a_{i+1}ai >ai+1 ，则位置 iii 有一处日期回退。可以不操作，也可以选择一段恰好包含 kkk 张照片的连续区间反转一次，求最少回退数。 反转只改变顺序，不改变日期；日期相等不算回退。 解题思路 解题方法 先记原序列的回退总数为 BBB，考虑反转区间 [l,r][l,r][l,r]，其中 r=l+k−1r=l+k-1r=l+k−1。 区间内部的相邻关系会全部反向：原来严格上升的关系会变成回退，原来的回退会消失，相等关系仍然不计数。设区间内部严格上升数为 UUU、回退数为 DDD，内部部分反转后对答案的贡献就是 U−DU-DU−D。 区间外的关系都不变，只需要检查最多两条连接边： * 如果 l>1l>1l>1，原来的 (al−1,al)(a_{l-1},a_l)(al−1 ,al ) 变成 (al−1,ar)(a_{l-1},a_r)(al−1 ,ar )； * 如果 r<nr<nr<n，原来的 (ar,ar+1)(a_r,a_{r+1})(ar ,ar+1 ) 变成 (al,ar+1)(a_l,a_{r+1})(al ,ar+1 )。 这样，每个区间都能在 O(1)O(1)O(1) 时间内算出答案。区间右移一格时，内部关系只删除最左边一对、加入最右边一对，因此 U,DU,DU,D 可以滑动维护。 1. 统计原序列的回退数 BBB，并令答案初始为 BBB，表示可以不操作。 2. 统计第一个长度为 kkk 的区间内部的上升数 UUU 和回退数 DDD。 3. 枚举区间左端点，用 B+U−DB+U-DB+U−D 加上两侧连接的变化量得到当前答案。 4. 窗口右移时删除离开窗口的相邻关系，加入新进入窗口的相邻关系。 5. 输出所有方案中的最小值。 把原序列的相邻关系分为三类：反转区间内部、区间左侧连接、区间右侧连接。内部关系反转后方向全部交换，因此贡献从 DDD 变成 UUU；两侧连接按反转后的端点重新计算；其他关系完全不变。三类关系覆盖了所有相邻位置且互不重复，所以公式准确计算了该区间的回退数。 滑动窗口每次只删除一条内部关系并加入一条新关系，故维护的 U,DU,DU,D 始终正确。算法枚举了所有长度为 kkk 的区间，同时保留了不操作方案，取最小值后就是全局最优解。 时间复杂度为 O(n)O(n)O(n)，空间复杂度为 O(n)O(n)O(n)。比较关系必须使用严格不等号，日期相等时不计回退。 * 只处理两侧连接，忘记区间内部的方向会全部反转。 * 把相等关系算进上升或回退。 * 忘记不操作方案，或漏掉贴着首端、末端的区间。 * 这里统计的是相邻回退，不是任意两张照片组成的逆序对。 部分分 * 测试点 1~4（n≤2000n\le2000n≤2000，20 分）：可以实际反转每个区间，再重新统计回退数。 * 测试点 5~20（无额外限制，80 分）：使用滑动窗口维护区间内部贡献，并处理两侧连接。 参考代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ YUILICE 的分批冲印 题意简述 按顺序处理 nnn 张照片。第 iii 张照片的打印时间为 tit_iti ，准备参数为 sis_isi 。要把照片分成至多 kkk 个连续、非空批次。 一个批次的耗时是该批次所有 tit_iti 的总和，加上其中最大的 sis_isi 。目标是让所有批次中最大的耗时尽可能小。 解题思路 解题方法 二分答案。假设限制每个批次的耗时不能超过 XXX，从左到右尽可能多地把照片放入当前批次： 当前批次维护打印时间和 sum、准备参数最大值 mx。如果加入下一张照片后满足 sum+ti+max⁡(mx,si)≤X,\text{sum}+t_i+\max(\text{mx},s_i)\le X, sum+ti +max(mx,si )≤X, 就继续加入；否则从这张照片开始新批次。 “尽可能长”必然合法，因为删去一个批次的前缀后，打印时间总和不会增加，准备参数最大值也不会增加。因此，贪心得到的批次数最少。 当 XXX 增大时，原来可行的分批方案仍然可行，所以可行性具有单调性，可以二分最小的 XXX。 1. 二分下界取 max⁡i(ti+si)\max_i(t_i+s_i)maxi (ti +si )，上界取 ∑ti+max⁡isi\sum t_i+\max_i s_i∑ti +maxi si 。 2. 在 check(X) 中从左到右维护当前批次的 sum 和 mx。 3. 如果单张照片都超过 XXX，直接判定失败。 4. 超过上限时新开批次，并清空当前批次的统计量。 5. 统计最少批次数是否不超过 kkk，据此继续二分。 对于固定的 XXX，设贪心算法第一批覆盖到位置 rrr。由于它取的是最长可行前缀，任何合法方案的第一批都不能超过 rrr。把贪心覆盖的前缀从任意合法方案中删去时，至多有一个批次被删去一部分前缀；剩余部分仍然合法，而且剩余批次数不会增加。 对剩余照片重复这个论证，得到贪心使用的批次数不超过任意合法方案，因此它得到的就是最少批次数。于是 check(X) 正确。又因为可行性随 XXX 增大而单调，二分找到的最小可行值就是答案。 一次 check 为 O(n)O(n)O(n)，二分次数为 O(log⁡U)O(\log U)O(logU)，其中 U=∑ti+max⁡siU=\sum t_i+\max s_iU=∑ti +maxsi ，总复杂度为 O(nlog⁡U)O(n\log U)O(nlogU)，空间复杂度为 O(n)O(n)O(n)。答案和中间和必须使用 long long。 * 准备参数取批次最大值，不是把所有 sis_isi 相加。 * 新开批次时要同时清空 sum 和 mx。 * 判断条件使用“加入后是否超过 XXX”，等于 XXX 时仍然合法。 * 需要先检查单张照片的 ti+sit_i+s_iti +si 是否超过 XXX。 部分分 * 测试点 1~2（k=1k=1k=1 或 k=nk=nk=n，10 分）：直接计算整段或每张照片单独成批的答案。 * 测试点 3~6（n≤16n\le16n≤16，20 分）：枚举相邻位置是否切分。 * 测试点 7~20（无额外限制，70 分）：二分答案，使用最长可行前缀贪心。 参考代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ YUILICE 的打印店 题意简述 有 ppp 台打印机，共用一个先进先出等待队列。提交订单、取消等待订单、暂停打印机接单和恢复打印机接单都发生在给定时刻。 同一时刻必须按三步处理：先结算所有完成订单，再按输入顺序处理这一时刻的全部操作，最后按打印机编号从小到大统一接单。正在打印的订单不会因为暂停或取消而中断。 输出每个订单的完成时刻；被取消输出 −1-1−1；最终一直等待、没有开始打印输出 −2-2−2。 解题思路 解题方法 不能按时间单位逐秒模拟，因为时刻最多达到 10910^9109，订单完成时间还可能更大。系统状态只会在两类时刻发生变化： 1. 下一条外部操作发生的时刻； 2. 某台打印机完成当前订单的时刻。 每次跳到这两类时刻的最小值即可。维护每台打印机的状态、当前订单和完成时刻，维护每个订单的状态以及等待队列。 到达时刻 now 后严格执行： 1. 把所有完成时刻等于 now 的订单标记为完成，并释放打印机； 2. 按输入顺序执行 now 时刻的所有操作； 3. 按打印机编号扫描空闲且允许接单的机器，从队首跳过已取消订单后派单。 最后一条外部操作结束后仍要继续处理打印完成事件。若没有外部操作、也没有正在打印的订单，队列中的订单就不可能再开始，答案保持为 −2-2−2。 1. 读入全部操作，保存操作顺序。 2. 用 state 区分等待、打印中、完成和取消。 3. 每轮找到下一外部操作时刻与最早完成时刻的较小值。 4. 依次完成结算、批量处理操作、按机器编号派单。 5. 记录完成时刻、取消结果和最终等待结果。 相邻两个事件时刻之间没有新操作，也没有订单完成，所以跳过中间时间不会遗漏状态变化。每轮第一步结算所有完成订单，第二步按照原输入顺序处理全部操作，第三步按题目规定的打印机编号和队列顺序派单，因此这一轮得到的状态与真实过程完全一致。 由初始状态正确，按事件时刻归纳可知整个模拟正确。每个订单只会在完成时被记录一次；取消只会对仍在等待的订单生效。模拟结束时，仍等待的订单已经没有可接单的打印机，所以输出 −2-2−2 正确。 设提交订单数为 nnn。事件时刻数量不超过 q+nq+nq+n，每轮最多扫描 ppp 台打印机，因此时间复杂度为 O(p(q+n))O(p(q+n))O(p(q+n))，空间复杂度为 O(p+q+n)O(p+q+n)O(p+q+n)。完成时刻使用 long long。 * 同一时刻的多条操作之间不能派单。 * 暂停只影响接收新订单，不会打断正在打印的订单。 * 取消正在打印、已经完成或已经取消的订单都没有额外效果。 * 最后一条操作之后还要继续结算完成事件。 * 等待队列里的取消订单可以延迟到队首时跳过。 部分分 * 测试点 1~2（p=1p=1p=1，只有提交操作，10 分）：维护单台打印机的结束时间。 * 测试点 3~6（只有提交操作，20 分）：模拟多台打印机和共享队列。 * 测试点 7~10（只有提交、取消操作，20 分）：增加等待订单取消和状态判断。 * 测试点 11~20（无额外限制，50 分）：完整处理完成、操作、派单的时序。 参考代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ YUILICE 的小区接送 题意简述 给定一棵树，每个站点有端点服务费 pip_ipi ，每条道路有行驶费用 www，每条路线还要支付一次固定派车费 CCC。要把所有站点划分成互不相交的简单路径，单个站点也可以单独成路。 多站路径只收两个端点的服务费，内部站点不收费；单站路径只收该站点一次服务费。求总费用最小值。 解题思路 解题方法 在树上保留一部分道路。只要每个站点被保留的道路数不超过 222，保留下来的每个连通块就是一条合法路径；反过来，每种路径划分也对应这样一组保留道路。 设保留边集合为 FFF，则路径数量为 n−∣F∣n-|F|n−∣F∣，所有路径固定费用为 (n−∣F∣)C(n-|F|)C(n−∣F∣)C。每条保留边贡献道路费用 www，同时让两个连通块合并，减少一份派车费 CCC。端点和单站服务费统一写成“度数不超过 111 的点付一次”： 总费用=nC+∑e∈F(we−C)+∑deg⁡(v)≤1pv.\text{总费用}=nC+\sum_{e\in F}(w_e-C)+\sum_{\deg(v)\le1}p_v. 总费用=nC+e∈F∑ (we −C)+deg(v)≤1∑ pv . 把树定根，定义 dp[u][0]dp[u][0]dp[u][0] 表示父边不保留时，uuu 子树的最小变形费用；dp[u][1]dp[u][1]dp[u][1] 表示父边保留时的最小变形费用。 假设所有子边都不保留，基准为 BBB。保留连接儿子 vvv 的边后，新增代价为 dv=dp[v][1]+wuv−C−dp[v][0].d_v=dp[v][1]+w_{uv}-C-dp[v][0]. dv =dp[v][1]+wuv −C−dp[v][0]. 父边不保留时，uuu 最多选两条子边；父边保留时，最多再选一条子边。只需维护最小的两个 dvd_vdv 。注意不能只选负增量：两条正增量也可能一起省下当前点的端点服务费。 1. 迭代遍历树，记录每个点的父亲和遍历顺序。 2. 按逆序处理节点，保证儿子状态已知。 3. 计算所有子边不选的基准值，并维护最小的两个增量。 4. 根据父边是否保留，枚举允许选取的子边数量，得到两个 DP 状态。 5. 根节点没有父边，输出 nC+dp[1][0]nC+dp[1][0]nC+dp[1][0]。 费用公式逐项对应原题：nCnCnC 是假设每个站点单独成路的固定费用，保留一条边会减少一份派车费并增加 www，度数不超过 111 的点恰好是路径端点或单站点，因此最后一项正好表示服务费。 固定 uuu 的父边状态后，各个儿子子树之间没有其他连接，子树贡献可以独立相加。uuu 的总度数最多为 222，所以父边不保留时最多选两条子边，父边保留时最多选一条子边。程序枚举这些全部可能，并在固定选择数量时取最小增量，因此两个状态都取得最优值。 由叶子向根归纳，根状态覆盖所有合法路径划分，最终答案正确。 每条边只被处理常数次，时间复杂度为 O(n)O(n)O(n)，空间复杂度为 O(n)O(n)O(n)。费用和增量使用 long long；迭代遍历可以处理最长链。 * 单站路径的服务费只收一次。 * 一个点最多连接两条保留边，不能让它成为三条路径的交汇点。 * 不能只保留负增量边。 * 所有站点都必须被覆盖，不能只求一条最便宜路径。 部分分 * 测试点 1~2（特殊性质 S，10 分）：树是星形，最多保留两条边，枚举选择数量即可。 * 测试点 3~6（n≤18n\le18n≤18，20 分）：枚举边子集，检查每点度数并直接计算费用。 * 测试点 7~20（无额外限制，70 分）：使用父边状态的树形 DP。 参考代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ YUILICE 的共用设备 题意简述 有 nnn 个任务，第 iii 个任务耗时 tit_iti 。每一批可以同时执行 111 到 333 个任务，批次耗时为其中最大的任务耗时。给出 mmm 对冲突关系，同批任务中的任意两项都不能冲突。每个任务必须恰好执行一次，求总完成时间最小值。 解题思路 解题方法 批次之间只能顺序执行，所以总时间就是每个批次最大耗时的总和。任务的具体批次顺序不重要，只需要划分集合。 用二进制集合 mask 表示还没有安排的任务，令 dp[mask] 为安排这些任务的最小总时间。固定 mask 中编号最小的任务 iii，枚举它所在的批次： * 只放 iii； * 放 iii 和一个任务 jjj； * 放 iii、jjj 和 kkk。 检查批内每一对任务都没有冲突，然后转移到移除这些任务后的集合。固定最低编号任务后，每个划分只会被枚举一次；枚举第三个任务时限制 k>jk>jk>j，避免重复。 无冲突的部分分可以排序后每三个任务分一批。完整数据使用集合划分 DP。 1. 用位掩码记录每个任务与哪些任务冲突。 2. 按 mask 从小到大计算 dp[mask]，空集合的值为 000。 3. 取出 mask 中最低编号的任务 iii。 4. 枚举与 iii 合法的单人、双人和三人批次，并更新 DP。 5. 输出全集 dp[(1<<n)-1]。 任意合法划分中，最低编号任务 iii 都恰好属于一个大小为 111、222 或 333 的批次。程序枚举了这个批次的所有合法成员组合，因此不会漏掉最优方案。 移除这一批后，剩余任务形成规模更小的同类问题。若剩余划分不是最优，就可以替换成更优划分而不影响已经选择的批次，矛盾。因此转移中的子问题必须取 dp 最优值。 反过来，每个转移都只加入合法批次，并与一个合法的剩余划分拼接，所以不会产生非法方案。按集合大小归纳，全集状态就是全局最优答案。 状态数为 2n2^n2n，每个状态枚举至多 O(n2)O(n^2)O(n2) 个双人或三人批次，时间复杂度为 O(n22n)O(n^2 2^n)O(n22n)，空间复杂度为 O(2n+n2)O(2^n+n^2)O(2n+n2)。n≤18n\le18n≤18，答案必须使用 long long。 * 三人批次必须检查三条冲突关系，不能只检查固定任务与另外两人的关系。 * 不能看到三个互不冲突的任务就立即成组，剩余任务仍需要全局最优。 * 固定最低编号任务是为了去重，不是限制最优方案的任务顺序。 部分分 * 测试点 1~2（m=0m=0m=0，10 分）：按耗时降序排序，每三个任务分一批。 * 测试点 3~6（n≤9n\le9n≤9，20 分）：递归枚举合法分组。 * 测试点 7~20（无额外限制，70 分）：固定最低编号任务所在批次，使用状压 DP。 参考代码

2026CSP-S第二轮复赛模拟赛题解

目录 题号 题目 完整算法 时间复杂度 空间复杂度 A 灯塔巡航 排序、二分、动态规划 O(nlog⁡n)O(n\log n)O(nlogn) O(n)O(n)O(n) B 优惠通道 分层状态图、Dijkstra O((n+m)log⁡(n+m))O((n+m)\log(n+m))O((n+m)log(n+m)) O(n+m)O(n+m)O(n+m) C 区间能量 懒标记线段树 O(n+qlog⁡n)O(n+q\log n)O(n+qlogn) O(n)O(n)O(n) D 树上信标 换根动态规划 O(n)O(n)O(n) O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ A. 灯塔巡航 解题思路 题意分析 记任务数量为 nnn，第 iii 个任务的时间区间为 [li,ri)[l_i,r_i)[li ,ri )、能量为 viv_ivi 。首先考虑按时间顺序执行任务。若一个方案中的任务互不冲突，它们就能按结束时刻从小到大排列。于是先将所有任务按照结束时刻排序，之后只需研究排序后的任务前缀。下文的任务编号均指排序后的编号。 任务能量不同时，只看某个局部条件无法决定是否选择任务。单个任务能量较高，也可能挤占其他任务的执行时间，导致总能量更低。因此，需要同时比较“选择当前任务”和“跳过当前任务”两类方案。 定义 dp[i]\mathrm{dp}[i]dp[i] 为只考虑前 iii 个任务时，能够获得的最大能量。这里“考虑”表示这些任务允许被选择，并不要求全部执行。没有任务时，dp[0]=0\mathrm{dp}[0]=0dp[0]=0。 对第 iii 个任务分类讨论。如果跳过它，其他任务都在前 i−1i-1i−1 个任务中，最优收益就是 dp[i−1]\mathrm{dp}[i-1]dp[i−1]。 如果选择它，之前执行的任务必须在时刻 lil_ili 或更早结束，即满足 rj≤lir_j\le l_irj ≤li 。由于结束时刻已经有序，这些任务恰好组成一个前缀。令 pip_ipi 为前 i−1i-1i−1 个任务中满足 rj≤lir_j\le l_irj ≤li 的任务数量，那么可以从前 pip_ipi 个任务中选出最优方案，再接上当前任务，获得 dp[pi]+vi\mathrm{dp}[p_i]+v_idp[pi ]+vi 点能量。若没有任务能衔接，便有 pi=0p_i=0pi =0。 因此状态转移为 dp[i]=max⁡(dp[i−1], dp[pi]+vi).\mathrm{dp}[i]=\max\bigl(\mathrm{dp}[i-1],\ \mathrm{dp}[p_i]+v_i\bigr). dp[i]=max(dp[i−1], dp[pi ]+vi ). 这里可以将前 pip_ipi 个任务的任意合法方案直接接到任务 iii 之前：该前缀内每个任务的结束时刻都不大于 lil_ili ，所以整个方案必然已在当前任务开始前完成。 现在只剩下如何快速求出 pip_ipi 。若逐个向前扫描，每个任务最多检查 nnn 个前驱，总计需要 O(n2)O(n^2)O(n2) 时间。结束时刻有序，可以使用二分查找，将一次查询缩短到 O(log⁡n)O(\log n)O(logn)。 具体来说，upper_bound 找到第一个严格大于 lil_ili 的结束时刻，它前面的元素数量就是 pip_ipi 。必须保留结束时刻恰好等于 lil_ili 的任务，才能符合半开区间的衔接规则。参考代码中的任务数组从下标 000 开始，而动态规划数组从下标 111 开始；二分查找得到的是可用前缀的长度，可以直接作为动态规划下标。 最终，dp[n]\mathrm{dp}[n]dp[n] 就是所有任务的最优答案。 部分分说明： * 测试点 1∼51\sim51∼5（n≤1000n\le1000n≤1000，ri≤104r_i\le10^4ri ≤104，vi≤103v_i\le10^3vi ≤103）：按结束时刻排序，使用同样的动态规划，但通过逐个扫描前面的任务求出 pip_ipi 。时间复杂度为 O(n2)O(n^2)O(n2)，可以处理这一组数据。 * 测试点 6∼106\sim106∼10（所有任务满足 vi=Vv_i=Vvi =V）：总能量等于选择的任务数乘以 VVV，转为最大化互不冲突的任务数量。按结束时刻排序，每次选择最早结束且能够衔接的任务。最早结束的选择会给后续任务留下尽可能多的时间，因此区间选择贪心可以处理这一组数据。 * 测试点 11∼1511\sim1511∼15（ri≤106r_i\le10^6ri ≤106）：可以按整数时刻做动态规划。令 f[t]f[t]f[t] 表示所有选中任务不晚于时刻 ttt 完成时能获得的最大能量，将任务按结束时刻分组，计算 f[t]=max⁡(f[t−1], max⁡ri=t(f[li]+vi))f[t]=\max\bigl(f[t-1],\ \max_{r_i=t}(f[l_i]+v_i)\bigr)f[t]=max(f[t−1], maxri =t (f[li ]+vi ))，初始化 f[0]=0f[0]=0f[0]=0。由于 li<ril_i<r_ili <ri ，转移时需要的状态均已算出。令 T=max⁡riT=\max r_iT=maxri ，时间与空间复杂度均可控制在 O(n+T)O(n+T)O(n+T)。 * 测试点 16∼2016\sim2016∼20（完整数据范围）：结束时刻可达 10910^9109，使用按结束时刻排序、二分查找前驱的动态规划，时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。这一做法也适用于前面的全部测试点。 实现步骤 1. 读入所有任务，按照结束时刻从小到大排序，并保存排序后的结束时刻数组。 2. 建立长度为 n+1n+1n+1 的动态规划数组，将 dp[0]\mathrm{dp}[0]dp[0] 初始化为 000。 3. 按顺序处理第 iii 个任务，在前 i−1i-1i−1 个结束时刻中使用 upper_bound 求出 pip_ipi 。 4. 按照转移式比较跳过和选择当前任务的收益，得到 dp[i]\mathrm{dp}[i]dp[i]。 5. 输出 dp[n]\mathrm{dp}[n]dp[n]。 正确性证明 对考虑的任务数量 iii 进行归纳，证明 dp[i]\mathrm{dp}[i]dp[i] 等于前 iii 个任务的最优收益。 当 i=0i=0i=0 时，没有任务可以执行，最大收益为 000，与初始化一致。 假设所有下标小于 iii 的状态都已正确求出。考察前 iii 个任务的任意最优方案。 若方案没有选择第 iii 个任务，它完全由前 i−1i-1i−1 个任务组成，收益至多为 dp[i−1]\mathrm{dp}[i-1]dp[i−1]；由归纳假设，该收益也确实能够达到。 若方案选择了第 iii 个任务，因为第 iii 个任务的结束时刻在前 iii 个任务中最晚，且每个任务都有 lj<rjl_j<r_jlj <rj ，其他任务不可能安排在它之后，只能在它开始前结束。这些任务均满足 rj≤lir_j\le l_irj ≤li ，属于前 pip_ipi 个任务，所以它们的总收益至多为 dp[pi]\mathrm{dp}[p_i]dp[pi ]。反过来，前 pip_ipi 个任务的最优方案能够合法地接上第 iii 个任务，达到 dp[pi]+vi\mathrm{dp}[p_i]+v_idp[pi ]+vi 。 两类方案覆盖了所有可能，分别取各类最大收益再取最大值，就得到正确的 dp[i]\mathrm{dp}[i]dp[i]。由数学归纳法，最终输出的 dp[n]\mathrm{dp}[n]dp[n] 正确。 复杂度分析 排序需要 O(nlog⁡n)O(n\log n)O(nlogn) 时间，每个任务进行一次 O(log⁡n)O(\log n)O(logn) 的二分查找与一次常数时间的转移，总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。任务数组、结束时刻数组和动态规划数组共占用 O(n)O(n)O(n) 空间。 参考代码 B. 优惠通道 解题思路 题意分析 设原图有 nnn 个路口和 mmm 条双向道路，起点为 111，终点为 nnn。普通最短路只记录到达每个路口的最小时间。但在本题中，到达同一个路口的两条路线，还可能具有不同的优惠券使用情况。 例如，到达某个路口时，一条路线耗时较少，但优惠券已经使用；另一条路线耗时略多，却保留着优惠券。若后面有一条耗时很大的道路，第二种状态就可能得到更好的最终结果。因此，不能只保留一个最短距离，需要将“优惠券是否已经使用”也加入状态。 将状态记为 (u,k)(u,k)(u,k)，其中 uuu 是当前路口，k=0k=0k=0 表示优惠券尚未使用，k=1k=1k=1 表示已经使用。定义 d[u][k]\mathrm{d}[u][k]d[u][k] 为从起点出发，到达这一状态的最小耗时。初始时人在路口 111，优惠券尚未使用，所以 d[1][0]=0,\mathrm{d}[1][0]=0, d[1][0]=0, 其余状态暂设为无穷大。 现在考虑从路口 uuu 沿一条权值为 www 的道路走到路口 vvv。如果正常通行，优惠券的使用情况保持不变，状态转移为 (u,k)⟶(v,k),费用为 w.(u,k)\longrightarrow(v,k),\qquad \text{费用为 }w. (u,k)⟶(v,k),费用为 w. 如果优惠券还未使用，还可以在这次经过道路时使用它，使当前费用变为 000，状态转移为 (u,0)⟶(v,1),费用为 0.(u,0)\longrightarrow(v,1),\qquad \text{费用为 }0. (u,0)⟶(v,1),费用为 0. 已经使用优惠券的状态只允许继续正常通行。这样，任意一条状态转移路径最多只会发生一次从未使用到已使用的变化，也就准确地限制了优惠券的使用次数。 可以将每个原图路口拆成两个状态。这个状态图共有 2n2n2n 个点；原图每条无向道路对应两种方向，每个方向有两条正常通行的状态边，以及一条使用优惠券的状态边，因此状态边数为 6m6m6m。实际编程时保存原图邻接表，在遍历道路时进行上述转移即可。 所有状态边的权值都非负，包括使用优惠券产生的零权边，因此可以使用 Dijkstra 算法。用小根堆维护当前距离最小的待处理状态，每次取出后沿原图相邻道路进行松弛。一个状态的距离被改小时，将新的记录放入堆中；之后若取出的记录已经过期，就直接跳过。 到达终点时，优惠券可以已经使用，也可以仍然保留，所以答案为 min⁡(d[n][0], d[n][1]).\min\bigl(\mathrm{d}[n][0],\ \mathrm{d}[n][1]\bigr). min(d[n][0], d[n][1]). 若两者都是无穷大，终点不可达，输出 -1。特别地，当 n=1n=1n=1 时，已经位于终点，可以不经过道路、不使用优惠券，正确答案为 000；对两个状态取最小值会自然地覆盖这种情况。 部分分说明： * 测试点 1∼51\sim51∼5（n,m≤1000n,m\le1000n,m≤1000）：仍然使用两个优惠券状态，但采用朴素 Dijkstra。每轮扫描全部 2n2n2n 个状态，选出尚未确定且距离最小的状态，再通过邻接表进行松弛。时间复杂度为 O(n2+m)O(n^2+m)O(n2+m)，可以处理这一组数据。 * 测试点 6∼106\sim106∼10（n,m≤2×105n,m\le2\times10^5n,m≤2×105，每条道路的权值均为 WWW）：一条经过 kkk 条道路的路线，最小耗时是 max⁡(k−1,0)W\max(k-1,0)Wmax(k−1,0)W。这一值随 kkk 增大而不减，因此对原图运行 BFS，求出从 111 到 nnn 最少需要经过多少条道路即可。若不可达输出 -1，否则用该公式计算答案，时间复杂度为 O(n+m)O(n+m)O(n+m)。 * 测试点 11∼2011\sim2011∼20（完整数据范围）：使用状态扩展和堆优化 Dijkstra。该做法适用于所有测试点。 实现步骤 1. 读入道路，按照双向道路建立邻接表。 2. 将所有距离初始化为无穷大，令 d[1][0]=0\mathrm{d}[1][0]=0d[1][0]=0，把状态 (1,0)(1,0)(1,0) 及距离 000 放入小根堆。 3. 取出距离最小的状态；如果堆中的距离与当前记录不一致，跳过这条过期记录。 4. 遍历相邻道路，尝试正常通行，更新相同优惠券状态下的距离。 5. 如果当前优惠券尚未使用，再尝试免费经过该道路，更新已使用优惠券的状态。每次成功更新后，将新记录放入堆。 6. 堆为空后，取终点两个状态距离的最小值；不可达时输出 -1，否则输出这一最小值。 正确性证明 首先证明原问题中的合法路线与状态图中的路径相互对应，并且总费用相同。 给定一条至多使用一次优惠券的合法路线，从状态 (1,0)(1,0)(1,0) 开始。正常经过道路时，走状态图中费用为原边权且优惠券状态不变的边；若在某次经过道路时使用优惠券，就走从未使用状态到已使用状态的零权边。这样能够到达终点的某个状态，且每次经过道路的计费方式与原路线一致。 反过来，给定一条从 (1,0)(1,0)(1,0) 出发的状态图路径，将每次转移还原为原图中的道路经过。状态图只允许从未使用状态转为已使用状态，不能反向恢复，因此路径至多包含一次免费经过。还原后得到合法路线，且费用保持不变。 于是，题目要求的最小耗时等于状态图中从 (1,0)(1,0)(1,0) 到 (n,0)(n,0)(n,0)、(n,1)(n,1)(n,1) 的最短距离的较小值。 状态图所有边的权值均非负。Dijkstra 每次选择当前距离最小的未确定状态时，如果存在更短路径，则该路径上第一个未确定状态的前驱已经被处理过，相应松弛会给出不大于这条更短路径前缀的距离。由于之后的边权非负，这会与当前选出的距离最小性矛盾。因此每次确定的距离正确，所有可达状态的最短距离都能正确求出。 最终取终点两个状态的较小距离，恰好涵盖使用和不使用优惠券的全部合法路线；两者均不可达时输出 -1。因此算法正确。 复杂度分析 状态图有 2n2n2n 个状态和 6m6m6m 条有向状态边。邻接表建图需要 O(n+m)O(n+m)O(n+m) 时间，堆优化 Dijkstra 的时间复杂度为 O((n+m)log⁡(n+m))O((n+m)\log(n+m))O((n+m)log(n+m))，距离、邻接表和堆共占用 O(n+m)O(n+m)O(n+m) 空间。这里用 log⁡(n+m)\log(n+m)log(n+m) 计入堆中可能保留的过期记录。 参考代码 C. 区间能量 解题思路 题意分析 设数组长度为 nnn，操作次数为 qqq，数组初始全为 000。 从直接维护数组开始。 对区间 [l,r][l,r][l,r] 加上 vvv 时，逐个修改数组中的元素；查询时，逐个累加区间中的元素。每次操作最多访问 nnn 个位置，总时间复杂度为 O(nq)O(nq)O(nq)。当 n,q≤1000n,q\le 1000n,q≤1000 时，这个方法可以完成计算；当两者都达到 2×1052\times 10^52×105 时，需要更快的区间维护方法。 静态数组可以用前缀和快速查询，但本题修改与查询交替出现。一次区间修改会影响多个前缀和，逐个重新维护仍可能花费 O(n)O(n)O(n) 时间。我们需要同时加速区间修改和区间查询。 用线段树维护区间和。 线段树根节点管理 [1,n][1,n][1,n]，每个非叶节点将所管理的区间 [L,R][L,R][L,R] 分成 [L,M][L,M][L,M] 与 [M+1,R][M+1,R][M+1,R]，其中 M=⌊(L+R)/2⌋M=\lfloor(L+R)/2\rfloorM=⌊(L+R)/2⌋。节点 ppp 用 sump\mathrm{sum}_psump 保存其区间的元素和。若左右子节点都已包含应有的修改，父节点的和等于左右子节点的和： sump=sum2p+sum2p+1.\mathrm{sum}_p=\mathrm{sum}_{2p}+\mathrm{sum}_{2p+1}. sump =sum2p +sum2p+1 . 查询区间可以分成若干个线段树节点管理的区间，答案就是这些区间和的总和。 整段修改只更新总和。 假设当前节点管理 [L,R][L,R][L,R]，这段区间完全包含在修改范围中。区间中共有 R−L+1R-L+1R−L+1 个位置，每个位置增加 vvv，总和就增加 v(R−L+1).v(R-L+1). v(R−L+1). 因此可以直接执行 sump←sump+v(R−L+1)\mathrm{sum}_p\gets\mathrm{sum}_p+v(R-L****ump ←sump +v(R−L+1)。若同时递归修改所有叶节点，仍然可能访问整个数组。我们把“这段区间中每个位置还应增加多少”记在当前节点，暂缓更新子节点。 懒标记保存每个位置的增量。 令 tagp\mathrm{tag}_ptagp 表示已经计入 sump\mathrm{sum}_psump 、尚未传给两个子节点的统一增量。完整覆盖当前节点时，执行 sump←sump+v(R−L+1),tagp←tagp+v.\mathrm{sum}_p\gets\mathrm{sum}_p+v(R-L+1),\qquad \mathrm{tag}_p\gets\mathrm{tag}_p+v. sump ←sump +v(R−L+1),tagp ←tagp +v. 多次加法可以合并，例如先增加 333 再增加 −1-1−1，等价于每个位置增加 222。所以懒标记用加法累计。 这里需要区分两种量：sump\mathrm{sum}_psump 是整段区间的和，tagp\mathrm{tag}_ptagp 是区间内每个位置的待传增量。给总和增加增量时，要乘区间长度；累计懒标记时，直接加上增量。 访问子节点前下传标记。 当修改或查询只涉及当前节点的一部分时，需要访问子节点。此时先把 tagp\mathrm{tag}_ptagp 传给左右子节点：分别给子节点的区间和加上“增量乘以该子区间长度”，再给子节点的懒标记加上同一增量，最后清空 tagp\mathrm{tag}_ptagp 。 例如，节点 [1,4][1,4][1,4] 整段增加 333 后，它的区间和增加 121212，懒标记为 333。若之后要查询 [2,3][2,3][2,3]，先向子区间 [1,2][1,2][1,2] 和 [3,4][3,4][3,4] 分别传递增量 333，两个子节点的区间和各增加 666，然后继续向下查询。父节点的区间和已经包含这次增加，下传时保持原值。 对子区间完成修改后，当前节点的标记已清空，重新用左右子节点之和更新父节点即可。查询只汇总答案，下传也只是把已经发生的修改传给子节点，所以查询不会改变数组的实际值。 为什么每次操作只要 O(log⁡n)O(\log n)O(logn)。 递归时，完全被操作区间覆盖的节点直接停止。每一层至多有两个与操作端点相交、还需要继续拆分的节点，其余被访问的节点完整覆盖后就停止。线段树高为 O(log⁡n)O(\log n)O(logn)，因此一次区间修改或查询的时间复杂度都是 O(log⁡n)O(\log n)O(logn)。 部分分说明： * 测试点 1∼51\sim 51∼5（n,q≤1000n,q\le 1000n,q≤1000）：直接使用数组模拟区间加法和区间求和，总时间复杂度为 O(nq)O(nq)O(nq)。 * 测试点 6∼106\sim 106∼10（特殊性质 A，所有修改均满足 l=rl=rl=r）：用树状数组维护单点增加与前缀和，区间和为两个前缀和之差，每次操作为 O(log⁡n)O(\log n)O(logn)。 * 测试点 11∼2011\sim 2011∼20（完整数据）：使用带加法懒标记的线段树，同时支持区间加法与区间求和，每次操作为 O(log⁡n)O(\log n)O(logn)。 实现步骤 1. 开设区间和数组与懒标记数组。数组初始全为 000，线段树各节点的区间和、标记也都初始化为 000。 2. 编写整段增加函数：将节点的区间和增加“增量乘以区间长度”，并累计该节点的懒标记。 3. 编写下传函数：把当前节点的增量分别作用于左右子节点，然后清空当前标记。 4. 处理区间修改：若当前区间被完整覆盖，直接整段增加；否则先下传标记，再递归修改有交集的子区间，最后合并左右子节点的区间和。 5. 处理区间查询：若当前区间被完整覆盖，返回区间和；否则先下传标记，再递归查询有交集的子区间，并累加返回值。 6. 依次执行所有操作，每次查询返回相应的区间和。 正确性证明 对线段树维护的状态进行归纳。初始所有元素均为 000，所有节点的区间和与懒标记也为 000，状态正确。 对于非叶节点，维护如下关系：它的区间和等于左右子节点保存的区间和之和，再加上当前节点尚未下传的统一增量对整段区间的贡献，即 sump=sum2p+sum2p+1+tagp(R−L+1).\mathrm{sum}_p=\mathrm{sum}_{2p}+\mathrm{sum}_{2p+1} +\mathrm{tag}_p(R-L+1). sump =sum2p +sum2p+1 +tagp (R−L+1). 这里子节点可能尚未包含祖先的标记；从根向下递归访问时，先下传路径上的标记，就能使被访问节点包含祖先修改的全部影响。 整段增加时，区间中每个位置增加 vvv，区间和增加 v(R−L+1)v(R-L+1)v(R−L+1)，懒标记增加 vvv，上述关系保持成立，保存的修改也与题目要求一致。 下传时，将同一增量作用于两个子区间。由于两个子区间不相交且恰好组成父区间，子节点区间和增加的总量为 tagp(R−L+1)\mathrm{tag}_p(R-L+1)tagp (R−L+1)。清空父节点标记后，父节点区间和等于两个子节点区间和之和，实际数组的值保持不变。 区间修改部分覆盖当前节点时，先下传，再递归处理所有有交集的子区间。根据归纳假设，子区间中的修改正确，重新合并后父节点区间和也正确。因此每次修改均正确维护数组状态。 区间查询完整覆盖当前节点时，路径上的祖先标记已经下传，直接返回的区间和就是当前实际区间和。部分覆盖时，查询范围被拆成左右两个不相交的部分，递归返回各部分的正确区间和，将它们相加便得到原查询范围的答案。因此算法输出的每个查询结果均正确。 复杂度分析 零初始化需要 O(n)O(n)O(n) 时间，每次修改或查询需要 O(log⁡n)O(\log n)O(logn) 时间，总时间复杂度为 O(n+qlog⁡n)O(n+q\log n)O(n+qlogn)，空间复杂度为 O(n)O(n)O(n)。 参考代码 D. 树上信标 解题思路 题意分析 设树有 nnn 个节点。固定一个起点，遍历整棵树就能计算这个起点到所有点的距离，时间复杂度为 O(n)O(n)O(n)。如果为每个起点分别做一次遍历，总时间复杂度是 O(n2)O(n^2)O(n2)，只能用于较小的数据。 两个相邻节点作为起点时，到其他点的距离存在简单的变化规律。先求出一个节点的答案，再根据相邻节点的关系逐步求出所有答案，就是本题的换根思路。 先固定根，计算子树信息 暂时把节点 111 作为根。对每个节点 uuu，定义两个量： sz⁡[u]=以 u 为根的子树中的节点数,\operatorname{sz}[u]=\text{以 }u\text{ 为根的子树中的节点数}, sz[u]=以 u 为根的子树中的节点数, f⁡[u]=∑x 在 u 的子树中dist⁡(u,x).\operatorname{f}[u] =\sum_{x\text{ 在 }u\text{ 的子树中}}\operatorname{dist}(u,x). f[u]=x 在 u 的子树中∑ dist(u,x). 子树大小包含节点 uuu 自身。对于叶子节点，有 sz⁡[u]=1\operatorname{sz}[u]=1sz[u]=1、f⁡[u]=0\operatorname{f}[u]=0f[u]=0。 设 vvv 是 uuu 的一个儿子，边 (u,v)(u,v)(u,v) 的长度为 www。从 uuu 到 vvv 子树中的任意节点，都要先经过这条长度为 www 的边，再从 vvv 走到目标节点。因此，这棵子树对 f⁡[u]\operatorname{f}[u]f[u] 的贡献是 f⁡[v]+sz⁡[v]×w.\operatorname{f}[v]+\operatorname{sz}[v]\times w. f[v]+sz[v]×w. 遍历 uuu 的所有儿子，就得到 sz⁡[u]=1+∑v 是 u 的儿子sz⁡[v],\operatorname{sz}[u]=1+\sum_{v\text{ 是 }u\text{ 的儿子}}\operatorname{sz}[v], sz[u]=1+v 是 u 的儿子∑ sz[v], f⁡[u]=∑v 是 u 的儿子(f⁡[v]+sz⁡[v]×wu,v).\operatorname{f}[u] =\sum_{v\text{ 是 }u\text{ 的儿子}} \left(\operatorname{f}[v]+\operatorname{sz}[v]\times w_{u,v}\right). f[u]=v 是 u 的儿子∑ (f[v]+sz[v]×wu,v ). 由于节点 111 的子树就是整棵树，节点 111 的完整答案为 ans⁡[1]=f⁡[1].\operatorname{ans}[1]=\operatorname{f}[1]. ans[1]=f[1]. 沿一条边推导换根公式 设 ppp 是 uuu 的父节点，边 (p,u)(p,u)(p,u) 的长度为 www。删除这条边，树会分成两部分：一部分是 uuu 的子树，包含 sz⁡[u]\operatorname{sz}[u]sz[u] 个节点；另一部分包含 n−sz⁡[u]n-\operatorname{sz}[u]n−sz[u] 个节点。 把起点从 ppp 移到 uuu 后，对于 uuu 子树中的节点，起点到它们的路径都减少了边 (p,u)(p,u)(p,u)，每个节点的距离减少 www，总共减少 sz⁡[u]×w\operatorname{sz}[u]\times wsz[u]×w。 对于子树外的节点，起点到它们的路径都新增了边 (u,p)(u,p)(u,p)，每个节点的距离增加 www，总共增加 (n−sz⁡[u])×w(n-\operatorname{sz}[u])\times w(n−sz[u])×w。 两部分合并，得到 ans⁡[u]=ans⁡[p]−sz⁡[u]×w+(n−sz⁡[u])×w=ans⁡[p]+(n−2sz⁡[u])×w.\begin{aligned} \operatorname{ans}[u] &=\operatorname{ans}[p] -\operatorname{sz}[u]\times w +(n-\operatorname{sz}[u])\times w\\ &=\operatorname{ans}[p]+(n-2\operatorname{sz}[u])\times w. \end{aligned} ans[u] =ans[p]−sz[u]×w+(n−sz[u])×w=ans[p]+(n−2sz[u])×w. 这里的 sz⁡[u]\operatorname{sz}[u]sz[u] 始终按照最初以节点 111 为根时的父子关系计算。计算不同起点的答案时，只改变距离和，不改变这些子树大小。 用非递归顺序完成两轮计算 可以从节点 111 开始，建立一个遍历序列 ord⁡\operatorname{ord}ord。处理序列中的节点时，把它的儿子追加到末尾，同时记录每个节点的父节点和父边长度。这样，父节点一定出现在儿子之前。 逆序处理 ord⁡\operatorname{ord}ord，每个节点的儿子都已经处理完，可以把当前节点的子树大小和子树距离和累加给父节点。 再顺序处理 ord⁡\operatorname{ord}ord，每个节点的父节点答案都已经求出，可以使用换根公式计算当前节点的答案。两轮计算都只处理每条父子关系一次。 当树是一条长度很大的链时，递归深度可能达到 nnn。参考代码使用遍历序列完成上述过程，额外调用栈深度为常数。 数值范围与输出 距离和需要使用足够大的整数类型。考虑 n=200000n=200000n=200000、每条边长为 10910^9109 的一条链。从端点出发，到各点的距离依次为 0,109,2×109,…,(n−1)×1090,10^9,2\times10^9,\ldots,(n-1)\times10^90,109,2×109,…,(n−1)×109，距离总和为 109∑i=0n−1i=109×200000×1999992=19999900000000000000.10^9\sum_{i=0}^{n-1}i =10^9\times\frac{200000\times199999}{2} =19999900000000000000. 109i=0∑n−1 i=109×2200000×199999 =19999900000000000000. 这个值超过有符号 long long 的最大值 922337203685477580792233720368547758079223372036854775807。因此，参考代码使用 __int128 保存 f⁡\operatorname{f}f、ans⁡\operatorname{ans}ans，并在乘法之前转换到 __int128。边权本身使用 long long 保存即可。 printf 没有直接输出 __int128 的格式符，可以不断取十进制末位，把得到的数字逆序后输出。所有答案均为非负整数；当 n=1n=1n=1 时，唯一节点的答案是 000，输出函数也要能处理这一情况。 部分分说明： * 测试点 1∼51\sim51∼5（n≤1000n\le1000n≤1000）：枚举每个起点，分别遍历整棵树，累加从该起点出发的所有距离，总时间复杂度为 O(n2)O(n^2)O(n2)。 * 测试点 6∼106\sim106∼10（特殊性质 A，整棵树是一条链）：从端点出发恢复链上节点的顺序，设第 iii 个节点的位置为 xix_ixi ，前缀和为 Pi=∑j=1ixjP_i=\sum_{j=1}^{i}x_jPi =∑j=1i xj ，且 P0=0P_0=0P0 =0。它到左侧节点的距离和为 (i−1)xi−Pi−1(i-1)x_i-P_{i-1}(i−1)xi −Pi−1 ，到右侧节点的距离和为 (Pn−Pi)−(n−i)xi(P_n-P_i)-(n-i)x_i(Pn −Pi )−(n−i)xi ，两部分相加即可。恢复顺序、计算前缀和以及求全部答案的时间复杂度均为 O(n)O(n)O(n)，位置前缀和及答案使用 __int128。也可以先求一个端点的答案，再按相邻节点间的距离变化逐点递推。n=1n=1n=1 时直接输出 000。 * 测试点 11∼2011\sim2011∼20（无额外限制）：使用完整的换根算法，逆序计算子树大小和子树距离和，再顺序求出所有节点的答案，总时间复杂度为 O(n)O(n)O(n)。 实现步骤 1. 读入树，使用邻接表保存每条无向边的两个方向。 2. 从节点 111 开始生成遍历序列 ord⁡\operatorname{ord}ord，记录每个节点的父节点 fa⁡[u]\operatorname{fa}[u]fa[u] 和父边长度 pw⁡[u]\operatorname{pw}[u]pw[u]。 3. 初始化所有 sz⁡[u]=1\operatorname{sz}[u]=1sz[u]=1、f⁡[u]=0\operatorname{f}[u]=0f[u]=0。 4. 逆序处理序列中除根以外的节点 uuu，令 p=fa⁡[u]p=\operatorname{fa}[u]p=fa[u]，将 sz⁡[u]\operatorname{sz}[u]sz[u] 累加到 sz⁡[p]\operatorname{sz}[p]sz[p]，将 f⁡[u]+sz⁡[u]×pw⁡[u]\operatorname{f}[u]+\operatorname{sz}[u]\times\operatorname{pw}[u]f[u]+sz[u]×pw[u] 累加到 f⁡[p]\operatorname{f}[p]f[p]。 5. 设置 ans⁡[1]=f⁡[1]\operatorname{ans}[1]=\operatorname{f}[1]ans[1]=f[1]。 6. 顺序处理序列中除根以外的节点 uuu，计算 ans⁡[u]=ans⁡[fa⁡[u]]+(n−2sz⁡[u])×pw⁡[u]\operatorname{ans}[u]=\operatorname{ans}[\operatorname{fa}[u]]+(n-2\operatorname{sz}[u])\times\operatorname{pw}[u]ans[u]=ans[fa[u]]+(n−2sz[u])×pw[u]。 7. 按节点编号从小到大，把每个 __int128 答案转成十进制输出。 正确性证明 首先证明逆序计算得到的子树信息正确。 叶子节点的子树只有它自身，所以初始化的 sz⁡[u]=1\operatorname{sz}[u]=1sz[u]=1、f⁡[u]=0\operatorname{f}[u]=0f[u]=0 正确。对于任意非叶子节点 uuu，逆序处理保证它的全部儿子已经处理完成。不同儿子的子树互不相交，与节点 uuu 自身恰好组成 uuu 的子树，因此大小累加得到正确的 sz⁡[u]\operatorname{sz}[u]sz[u]。对每个儿子 vvv，到它子树内所有节点的距离贡献为 f⁡[v]+sz⁡[v]×wu,v\operatorname{f}[v]+\operatorname{sz}[v]\times w_{u,v}f[v]+sz[v]×wu,v ，累加后得到正确的 f⁡[u]\operatorname{f}[u]f[u]。由此，全部子树信息正确，ans⁡[1]=f⁡[1]\operatorname{ans}[1]=\operatorname{f}[1]ans[1]=f[1] 也正确。 其次证明换根计算正确。设 ans⁡[p]\operatorname{ans}[p]ans[p] 已经正确，uuu 是 ppp 的儿子。删去边 (p,u)(p,u)(p,u) 后，所有节点被完整地分成 uuu 的子树和子树外两部分。起点由 ppp 移到 uuu 时，这两部分的距离总和分别减少 sz⁡[u]×w\operatorname{sz}[u]\times wsz[u]×w、增加 (n−sz⁡[u])×w(n-\operatorname{sz}[u])\times w(n−sz[u])×w。因此，换根公式准确计算出 ans⁡[u]\operatorname{ans}[u]ans[u]。 顺序遍历中，父节点总在儿子之前。以正确的 ans⁡[1]\operatorname{ans}[1]ans[1] 为起点归纳，全部节点的答案都正确。最终按照节点编号输出，因此算法符合题目要求。 复杂度分析 建立遍历序列时，每条无向边被检查两次；逆序计算和顺序换根各处理 n−1n-1n−1 条父子关系。因此，总时间复杂度为 O(n)O(n)O(n)。 邻接表、遍历序列以及各状态数组占用 O(n)O(n)O(n) 空间。十进制输出的位数有固定上界，不改变上述复杂度。 参考代码