6767MJ

X的日记

写在前面 老吸说，好的文章离不开日复一日的积累，然而作者的语言组织能力堪比一根成年香蕉，写写日记倒是可以锻炼锻炼文笔，顺便记录一些生活中的琐碎，也方便日后细细品味，因此，以下的所有内容都不含AI的成分，文笔生疏，不喜勿喷 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.23 上午 物理老师我爱你 全校的物理课，我们班进度是最慢的了，可能到了期中考试课都上不完，更别说复习了，肥美的物理老师在每次上课前先花10min散布心灵鸡汤鼓舞士气，5min赞美同学2min赞美自己2min赞美太阳，才开始上课。。请给我一个进度不慢的理由。。 更神的来了，伪善的物理老师口口声声的说着，自己不爱占课，从不占课，却毫不犹豫的停掉了我们仅剩的体育音乐，不是说不能占课，事到如今，不得不占，但是你嘴上说着正义的话，却做着相反的事，是不是有点恶心了，，反思一下自己吧，少说废话，多干正事，这才是别人上的又快又好的诀窍，都是初中生了，不需要你的鸡汤，该怎么学、是否该好好学大家心知肚明，真正不思进取也听不进去，所以几句话根本就改变不了什么 晚上 今天晚自习发生了一件非常恶劣的事，是这样的:当时我和同桌正在与作业进行激烈的斗争，一只苍蝇忽然飞到了我的作业上，呃呃呃我也是心生爱慕了啊用我尊贵的手反复挥动试图将它赶走，可是这只苍蝇不但对我的动作置之不理，还悠哉悠哉的搓起了手和屁股，我一下子就怒了啊，这分明是在挑衅我的权威，于是拿出一张面巾纸啪的一下把他拍在作业本上，同桌深感同情，将它担到了地上。。这时愧疚感油然而生，我赶忙下地查看，那只苍蝇的四肢还在不停的抽动着，还好，它没死，只是刚刚被拍晕了。。 最恶劣的来了，同嘬鬼点子生成中。。。用圆规的尖端残忍的扎进了它的身体，力道刚刚好，没有把他扎死，反而将它提了起来，苍蝇仿佛察觉到了危险，四肢抽动的更剧烈了，无力的挣扎着(这里是地狱吗)。。同嘬就把那只圆规静静的架在桌角，像一只罪恶的艺术品(这里是地狱吗。。。我的心被大大的震撼了，生命不该这样被践踏，更何况杀生不虐生，要么就给个痛快，要么就让它继续活着(作者是圣母)怎么办怎么办，今晚要被苍蝇托梦了，功德-1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.24 饿啊今天早上起来头好晕啊，不会生病了吧，没招了撑着吧还有作业要写呢 下午去上课，不不不这段时间是我一天中状态最差的时候了，头微微发热，可能发烧了，还有点犯恶心，没办法，靠不了任何人，继续撑着，题都不会写了，脑子一片空白，只想快点结束。 晚上 终于熬完了，我爱你们所有人 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.25 真想穿越到小学炸鱼啊，今天突然想起了小学举办的辩论赛，辩题是“少年识得/不识愁滋味”，我是反方，记得正方举了一个例子来反驳我们的观点，大概是一个乡下的孩子从小就很懂事最后考上了某名牌大学，未完待续我爱你们，B不想写了，烂尾了 别急别急，晚上还有很多事 又是索然无味的一天，全天唯一的亮点就是从课外班回家的路上吃了一家路边摊，味道不错，服务到位，五星好评，图待会放。。 ok，图找到了以下是对菜品的评价: * 图片上方是一碗肥美幸福饭，里面有些牛肉、几坨牛油果、淋了一些血红色的不明液体(大概率是红烩酱)、一个很嫩的鸡蛋，要把鸡蛋戳破了拌着吃，口感一般 * 中间是一碗肥美的牛肉河粉，服了，粉是辣的，我吃不得，给浮木吃去)浮木的地位( * 左下角是牛肉饭，牛肉七分熟，口感一般，并不是太惊艳 总之菜不贵，期望也没太高，整体还是不错的(一共花了30RMB) 回去的时候看到这一幕:一群熊孩子推搡着一个穿着充气玩偶的人类(做广告的那种人，大家应该都见过)，这种小孩家长真的该管管，小孩子不懂事很正常，但是家长要尽自己的责任才行，换位思考一下，玩偶里的打工人应该很绝望吧，又热又闷又狭窄，还要时刻保持衡防平摔倒。。。唉 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.26 无事发生 又是凡的平一天 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.28 鲁迅真的是一个很伟大的人，今天学到了他的文章《故乡》，对于其中的一些句子很是喜欢 “我在朦胧中，眼前展开一片海边碧绿的沙地来，上面是深蓝的天空中挂着一轮金黄的圆月。我想:希望本是无所谓有，无所谓无的。这正如地上的路； 其实地上本没有路，走的人多了，也便成了路其实地上本没有路，走的人多了，也便成了路其实地上本没有路，走的人多了，也便成了路” 这句话有着很深的哲理啊，儿时变听闻过鲁迅先生的这句名言，当时啥也不懂，只是一味的崇拜，现在也有些自己的思考了。。 呃呃呃首先啊这句话运用了比喻的修辞手法，将希望比做了地上的路，(呃呃呃套话不想写了，写点感悟吧) * 知识分子的深刻反省 * 需要许许多多的人共同努力 * 仅仅具有崇高的理想是不够的，还需要无所畏惧的实践、行动(实则是老师上课笔记。。自爆了( ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.29 学习狗子的大爱无疆/bx ，见到活人就说我爱你，得到了大家的一致好评 唉，班上那些超标怪怎么都那么强，反观我，多么平庸又猎奇的一个人。。。 今天晚自习，作业很多，但还是有几个大佬写完了家庭作业，并在我们绝望之时写完了n篇课外。。。就很好奇哈，他们是怎么做到又快又好的？换我们『物理老尸』的话说，他们是怎么做到功率大，效率高的？这对我们来说，似乎很令人费解，但是在，他们看来，只是基操罢了。。 于是，我越来越不相信，天赋是可以靠努力超越的了。天赋就像一座地基，有了地基不建房，永远也不见成果；但是没有这地基，你连建房的机会都没有。。曾经那个信心满满的小将，已经在一次次磨难中，越发的挫败了，温水煮了将军梦，也许，梦就该这样结束了吗，希望不是吧，人生才刚刚开始，还有很多美丽的事和物等着我们去发现，不能因此就失了士气哦 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 10.30 旁边好像有商场着火了，不清楚，我爸说来的路上看到好几辆救火车和救护车，貌似挺严重的 �� 10.31 今天是亲戚家小屁孩的生日，作业那么多还要去参加倒霉生日会，坐标新街口，人多堵车停车费又贵，搞得我心中满是怨气，路上途径总统府，看到了南京为数不多的劳斯莱斯门店，里面停了一辆，但是由于车子太贵，这家店无人问津，破败不堪，好像门都锁了，可能已经濒临倒闭了，惨惨

AC君赶快把我禁言

AC君，请赶快将我禁言，我的信息如下： > 个人信息 > 我为什么要禁言 > 禁言要求 愿AC君尽快查收 > 彩蛋

呵呵

有什么东西是这样死的？再往下翻之前，你先思考一下。 等会儿怎么上榜了？

社区现状

活动详情见大大大大大活动！ 社区已经露出了许多弊端，ACGO若在现况下不做出有效的措施，再怎么改革都无法获得满意的结果。此情形永远得不到改变，ACGO将持续没落，直至衰亡。以下为社区现状： 一、 由于某种神秘原因，现在的竞赛都出现了“CSP模拟”的名字，结束时间极其逆天。或许官方想让比赛的选手们先做完比赛的试题，然后放松身心后在下一天紧张的打开ACGO查看自己的排名？有点神圣。

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

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

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

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

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) 空间。十进制输出的位数有固定上界，不改变上述复杂度。 参考代码

活动规则

11月将会选出前三名最积极的用户并发放奖励。若想要当“数评论”的私信（数前三名评论量最多的），待遇不会少。若评论数>=2，私信，否则可能不会被看见。如果有人说什么评论数达标但没关注，我将一律无视。

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

大师主宰级团队现启动更名，本次为第一阶段初筛。以下候选名分为两类：纯字母名（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（待定） 名共同进入终选投票，最终团队名在第二阶段产生。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广告： MHCA#1竞赛综合帖

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

目录 题号 题目 完整算法 时间复杂度 空间复杂度 A 三站积分榜 结构体排序 O(nlog⁡n)O(n\log n)O(nlogn) O(n)O(n)O(n) B 展板分层 贪心 O(20∑n)O(20\sum n)O(20∑n) O(20)O(20)O(20) C 断连充能 动态规划 O(n)O(n)O(n) O(1)O(1)O(1) D 三轨信号 动态规划 O(n)O(n)O(n) O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ A. 三站积分榜 解题思路 题意分析 每名队员都对应一组相关信息：原始编号、三站成绩、有效成绩。使用结构体保存这些信息，再用结构体数组保存所有队员。排序时整条队员记录一起移动，编号与成绩就能始终对应。 读入第 iii 名队员时，把编号记为 iii。先求三站成绩的最小值，再用三站成绩之和减去这个最小值，得到有效成绩。每站最高为 100100100，有效成绩最高为 200200200，使用 int 就能保存所有成绩和编号。 接下来，关键是写清楚两名队员谁应该排在前面。比较函数 cmp 返回 true，表示第一名队员应排在第二名队员前面。题目的三条规则具有先后顺序，必须先判断优先级更高的条件，只有这一项相同时，才继续比较下一项。 设正在比较的队员为 x,yx,yx,y。如果两人的有效成绩不同，就由有效成绩决定顺序，成绩大的排在前面；如果有效成绩相同，再比较第三站成绩，第三站成绩大的排在前面；如果这两项都相同，最后比较编号，编号小的排在前面。 例如两名队员的有效成绩分别为 170170170 和 160160160，即使后者第三站成绩更高，也应当由有效成绩为 170170170 的队员排在前面。只有有效成绩相同，第三站成绩才参与决定顺序。 当两名队员的有效成绩、第三站成绩都相同时，较小编号表示输入时更早出现的队员。原始编号已经存入结构体，排序后仍然按保存的编号比较和输出。 调用 sort，传入结构体数组和比较函数，数组就会按照这三条规则排列。程序使用下标 111 至 nnn 保存队员，对应的排序区间写为 sort(p + 1, p + n + 1, cmp)。排序完成后，依次输出数组中每名队员的编号和有效成绩。 实现步骤 1. 定义队员结构体，保存编号、三站成绩和有效成绩，并建立结构体数组。 2. 对第 iii 名队员，将原始编号记为 iii，用三站成绩总和减去其中的最低分，得到有效成绩。 3. 编写比较函数：有效成绩不同时按有效成绩降序；否则，第三站成绩不同时按第三站成绩降序；两项都相同时按编号升序。 4. 使用 sort 对全部队员排序。 5. 按排序后的顺序输出队员编号和有效成绩。 正确性证明 首先，对于任意队员，算法先求出三站成绩的最小值，再用三站成绩之和减去这个值，恰好符合有效成绩的定义。因此，算法保存的每名队员的有效成绩正确。 下面说明比较函数能正确判断任意两名队员的先后顺序。 如果两人的有效成绩不同，比较函数让有效成绩较高者排在前面，符合第一条排名规则。如果有效成绩相同、第三站成绩不同，比较函数让第三站成绩较高者排在前面，符合第二条规则。如果有效成绩和第三站成绩都相同，比较函数让编号较小者排在前面，符合第三条规则。三种情况覆盖了任意两名不同队员的比较，所以比较函数与题目规定的顺序完全一致。 sort 按照比较函数排列全部队员，因此排序后的数组顺序就是题目要求的排名顺序。结构体保存了每名队员的原始编号及正确的有效成绩，排序时这些信息一起移动，所以依次输出数组中的编号和有效成绩，就是正确答案。 复杂度分析 读入并计算全部队员的有效成绩需要 O(n)O(n)O(n) 时间。比较函数每次只比较固定数量的整数，耗时为 O(1)O(1)O(1)，排序需要 O(nlog⁡n)O(n\log n)O(nlogn) 时间。输出需要 O(n)O(n)O(n) 时间，因此总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。 结构体数组保存 nnn 名队员的信息，占用 O(n)O(n)O(n) 空间；排序过程的辅助空间不超过这一数量级，因此总空间复杂度为 O(n)O(n)O(n)。 参考代码 B. 展板分层 解题思路 题意分析 设展示墙宽度为 WWW，共需摆放 nnn 块展板。所有展板的高度都相同，决定能否放进一层的只有宽度。我们逐层摆放展板：每开始一层，剩余宽度设为 WWW；然后从最大的宽度开始考虑，当前宽度的展板能放多少块，就放多少块，再继续考虑更小的宽度。 例如墙宽为 101010，剩余展板中有宽度为 8,4,28,4,28,4,2 的展板。当前层先放一块宽度为 888 的展板，剩余宽度为 222。宽度为 444 的展板留给后面的层，当前层继续放入宽度为 222 的展板。某种宽度放不下时，仍然要继续检查更小的宽度。 这个贪心策略依赖于展板宽度都是 222 的整数次幂。对于宽度为 2p2^p2p 的展板，所有更小的宽度都能整除 2p2^p2p。若一批更小展板的总宽度至少为 2p2^p2p，就一定能从中选出若干块，使宽度之和恰好为 2p2^p2p。因此，可以通过交换一块大展板和若干块小展板，将某个最优方案逐步调整成上述从大到小的摆法。完整的交换过程见正确性证明。 接下来考虑如何快速找到每种宽度的展板。因为 wi≤106w_i\le10^6wi ≤106，可能出现的宽度只有 20,21,…,2192^0,2^1,\ldots,2^{19}20,21,…,219，共 202020 种。使用数组 cnt[p]\mathrm{cnt}[p]cnt[p]，记录宽度为 2p2^p2p 的展板还剩多少块。读入一块展板时，将它的宽度不断除以 222，直到变为 111，除法次数就是对应的指数 ppp。 设当前层剩余宽度为 r\mathrm{r}r。考虑宽度为 2p2^p2p 的展板时，当前层最多还能放 ⌊r/2p⌋\lfloor\mathrm{r}/2^p\rfloor⌊r/2p⌋ 块，同时也不能超过剩余数量。因此，本次放入的数量为： k=min⁡(cnt[p],⌊r2p⌋).\mathrm{k}=\min\left(\mathrm{cnt}[p],\left\lfloor\frac{\mathrm{r}}{2^p}\right\rfloor\right). k=min(cnt[p],⌊2pr ⌋). 放入后，将该宽度的剩余数量减少 k\mathrm{k}k，当前层剩余宽度减少 k⋅2p\mathrm{k}\cdot2^pk⋅2p，未摆放的展板总数也减少 k\mathrm{k}k。从 p=19p=19p=19 枚举到 p=0p=0p=0 后，当前层摆放结束，答案增加 111。重复这个过程，直到全部展板放完。 题目保证每块展板的宽度都不超过 WWW。只要还有展板，每个新层就至少能放入一块，所以最多会开出 nnn 层，循环一定能够结束。 部分分说明： * 测试点 1∼31\sim31∼3（一份输入中 ∑n≤103\sum n\le10^3∑n≤103）：可以先将展板宽度从大到小排序，记录每块是否已放置。每开一层就完整扫描一次数组，将尚未放置且能放下的展板依次放入，最多扫描 nnn 层，每组数据的时间复杂度为 O(n2)O(n^2)O(n2)。 * 测试点 4∼124\sim124∼12（一份输入中 ∑n≤105\sum n\le10^5∑n≤105）：统计 202020 种宽度的剩余数量，每层从大到小批量放置展板。每组数据的时间复杂度为 O(20n)O(20n)O(20n)，能够处理全部数据。 实现步骤 1. 对每组数据，将宽度计数数组 cnt\mathrm{cnt}cnt 清零。 2. 遍历每块展板的宽度，求出对应的指数 ppp，将 cnt[p]\mathrm{cnt}[p]cnt[p] 增加 111。 3. 将未摆放展板数设为 nnn，答案设为 000。只要还有展板，就新开一层，并将该层剩余宽度设为 WWW。 4. 从 p=19p=19p=19 到 p=0p=0p=0，计算当前宽度能放入的数量 k\mathrm{k}k，更新宽度计数、该层剩余宽度和未摆放展板数。 5. 枚举完所有宽度后，将答案增加 111。所有展板放完后，输出该组答案。 正确性证明 首先证明一个关于宽度的引理：设 sss 是 222 的整数次幂，一批展板的宽度都是小于 sss 的 222 的整数次幂。如果它们的宽度之和至少为 sss，则能从中选出若干块，使总宽度恰好为 sss。 证明时，将两块宽度相同的展板临时合并为一个宽度翻倍的整体，不断执行这一操作。每个整体都对应原来的一组展板，且这些组互不重叠。如果得到了宽度为 sss 的整体，其对应的原展板就是所需的集合。如果始终没有得到这样的整体，那么最终每种小于 sss 的宽度至多剩下一个整体，它们的总宽度最多为 1+2+4+⋯+s/2=s−11+2+4+\cdots+s/2=s-11+2+4+⋯+s/2=s−1，与原总宽度至少为 sss 矛盾。因此引理成立。临时合并仅用于证明，并不改变实际摆放规则。 下面证明：对于任意一批尚未摆放的展板，存在一个最优方案，使它的第一层与贪心算法所选的展板宽度和数量完全相同。 取一个最优方案，按照宽度从大到小调整它的第一层。设当前考虑的宽度为 sss，所有大于 sss 的展板数量已经与贪心第一层一致。这些较大展板占用的宽度确定以后，贪心会放入尽可能多的宽度为 sss 的展板。原方案第一层中这种展板的数量不会超过贪心数量，因为两者受到相同的剩余容量和展板总数限制。 如果原方案第一层中的宽度为 sss 的展板还不够，就从其他某一层取来一块宽度为 sss 的展板。这样的展板一定存在，因为贪心数量不超过当前这批展板中宽度为 sss 的总数量。 设移动前第一层的空余宽度为 FFF，其中所有小于 sss 的展板的总宽度为 BBB。由于第一层还能在贪心目标中增加一块宽度为 sss 的展板，必有 F+B≥sF+B\ge sF+B≥s。如果 F≥sF\ge sF≥s，直接移入即可。如果 F<sF<sF<s 且 B≥sB\ge sB≥s，根据引理，可以从第一层选出总宽度恰好为 sss 的小展板；如果 F<sF<sF<s 且 B<sB<sB<s，就选出第一层的全部小展板，此时它们与原空余位置合起来至少能腾出宽度 sss。 后两种情况中，将选出的小展板移到提供大展板的那一层，再将这块宽度为 sss 的展板移入第一层。移出的小展板总宽度不超过 sss，能够放进另一层腾出的空间；第一层也腾出了足够空间。这个交换保持了每层合法，不增加层数，也不会改变第一层中已经确定的较大展板数量。 重复交换，可以让第一层中宽度为 sss 的展板数量达到贪心数量。再依次处理更小的宽度，就得到一个层数仍然最优、第一层与贪心完全一致的方案。 最后，对展板数量作归纳。没有展板时，算法使用 000 层，显然最优。有展板时，设最优层数为 HHH。由上述交换过程，可以选取一个最优方案，使第一层恰好采用贪心摆法，其余展板在剩下的 H−1H-1H−1 层中能够放完。第一层至少放入一块展板，所以剩余展板数量更少；由归纳假设，贪心处理剩余展板时使用的层数不超过 H−1H-1H−1。于是算法总共不超过 HHH 层。算法给出的摆放始终合法，层数也不可能小于最优值 HHH，因此算法恰好使用最少层数。 复杂度分析 每块展板最多除以 222 共 191919 次，统计宽度数量需要 O(20n)O(20n)O(20n) 时间。每层枚举 202020 种宽度，最多开出 nnn 层，所以摆放过程需要 O(20n)O(20n)O(20n) 时间。每组数据的总时间复杂度为 O(20n)O(20n)O(20n)；设一份输入中所有展板数量之和为 N=∑nN=\sum nN=∑n，总时间复杂度为 O(20N)O(20N)O(20N)。 计数数组固定包含 202020 个元素，其他变量数量固定，额外空间复杂度为 O(20)O(20)O(20)，即常数空间。 参考代码 C. 断连充能 解题思路 题意分析 设共有 nnn 个装置，第 iii 个装置的能量为 aia_iai 。每个装置只有选和不选两种决定，因此可以先考虑枚举所有选择方案。对于一个方案，检查是否存在连续三个都被选择的装置；如果方案合法，就计算能量总和并更新答案。一共有 2n2^n2n 个方案，每个方案最多检查 nnn 个装置，时间复杂度为 O(n2n)O(n2^n)O(n2n)。这个方法适用于 n≤5n\le5n≤5 的子任务，但无法处理 n=200000n=200000n=200000 的数据。 为了减少重复计算，按照从左到右的顺序处理装置。处理完前 iii 个装置后，下一个装置能不能选择，取决于当前末尾已经连续选择了几个装置。如果末尾连续选择了 222 个，下一个就必须跳过；如果末尾连续选择了 000 个或 111 个，下一个仍然可以选择。 因此，把所有合法方案按照“末尾连续选择的数量”分成三类。令 f0,f1,f2f_0,f_1,f_2f0 ,f1 ,f2 分别表示处理完当前前缀后，末尾连续选择 000 个、111 个、222 个装置时，能够获得的最大能量总和。末尾连续选择 000 个，表示当前最后一个装置没有被选择；末尾连续选择 111 个，表示最后一个选择了，前一个没有选择；末尾连续选择 222 个，表示最后两个都选择了。 这三个状态已经足够决定后续选择是否合法。对于末尾连续选择数量相同的两个方案，之后可以接上的选择完全相同；能量较小的方案，无论接上哪种后续选择，都不会优于能量较大的方案。因此，每一类只保留最大的能量总和，就能保留得到最优答案所需的信息。 假设已经处理完前 i−1i-1i−1 个装置，三个旧状态为 f0,f1,f2f_0,f_1,f_2f0 ,f1 ,f2 ，当前装置的能量为 aia_iai 。用 g0,g1,g2g_0,g_1,g_2g0 ,g1 ,g2 保存处理完第 iii 个装置后的新状态。 如果不选择第 iii 个装置，末尾连续选择的数量变为 000。前面无论属于哪一类，都可以跳过当前装置，而且总能量不变，因此 g0=max⁡(f0,f1,f2).g_0=\max(f_0,f_1,f_2). g0 =max(f0 ,f1 ,f2 ). 如果选择第 iii 个装置，并使末尾恰好连续选择 111 个，那么第 i−1i-1i−1 个装置必须没有选择，前一状态只能是 f0f_0f0 ，因此 g1=f0+ai.g_1=f_0+a_i. g1 =f0 +ai . 如果选择第 iii 个装置，并使末尾恰好连续选择 222 个，那么前一状态必须恰好连续选择了 111 个，即来自 f1f_1f1 ，因此 g2=f1+ai.g_2=f_1+a_i. g2 =f1 +ai . 当 f1f_1f1 不可达时，g2g_2g2 也不可达。不能从 f2f_2f2 继续选择当前装置，因为这会出现三个连续选择的装置。 三个新状态必须全部根据旧状态计算完成，再同时替换旧状态。如果刚算出 g0g_0g0 就覆盖 f0f_0f0 ，随后计算 g1g_1g1 时用到的就是已经处理过当前装置的状态，破坏了转移的含义。使用两组变量，可以明确区分处理当前装置前后的状态。 开始时还没有处理任何装置，只有一个都不选的方案，因此初始化为 f0=0,f1=f2=−∞.f_0=0,\qquad f_1=f_2=-\infty. f0 =0,f1 =f2 =−∞. 这里的 −∞-\infty−∞ 表示不存在这种选择方案。代码用 long long 最小值的四分之一作为负无穷标记，它远小于任何合法能量总和；不可达的 f1f_1f1 不参与加法，保证负无穷标记不会变成一个普通状态值。选择这个标记也避免直接使用最小整数参与算术时产生下溢。 每次跳过当前装置时，都可以继承之前的空选方案。因此，f0f_0f0 始终至少为 000，全部装置能量为负数时，也会得到正确答案 000。 处理完全部装置后，合法方案的末尾连续选择数量只能是 000、111 或 222，答案为 max⁡(f0,f1,f2).\max(f_0,f_1,f_2). max(f0 ,f1 ,f2 ). 每一轮只依赖上一轮的三个状态，可以使用滚动动态规划，只保存这三个值。装置的能量也可以一边读入一边处理。 部分分说明： * 子任务 111（1≤n≤51\le n\le51≤n≤5）：枚举全部 2n2^n2n 种选择方案，检查是否存在连续三个都被选择的装置，统计合法方案的能量总和并取最大值。每个方案需要 O(n)O(n)O(n) 时间，总时间复杂度为 O(n2n)O(n2^n)O(n2n)。 * 子任务 222（完整数据，1≤n≤2000001\le n\le2000001≤n≤200000、−109≤ai≤109-10^9\le a_i\le10^9−109≤ai ≤109）：使用末尾连续选择数量为 000、111、222 的三个状态进行滚动动态规划，时间复杂度为 O(n)O(n)O(n)，可以处理全范围数据。 实现步骤 1. 将状态 f0f_0f0 初始化为 000，将 f1,f2f_1,f_2f1 ,f2 初始化为负无穷，表示这两类方案还不存在。 2. 从左到右遍历装置，设当前装置的能量为 xxx，用三个旧状态的最大值计算不选当前装置的新状态 g0g_0g0 。 3. 计算 g1=f0+xg_1=f_0+xg1 =f0 +x；如果 f1f_1f1 可达，再计算 g2=f1+xg_2=f_1+xg2 =f1 +x，否则保持 g2g_2g2 为负无穷。 4. 三个新状态全部计算完成后，再令 f0=g0f_0=g_0f0 =g0 、f1=g1f_1=g_1f1 =g1 、f2=g2f_2=g_2f2 =g2 ，继续处理下一个装置。 5. 处理完全部装置后，输出三个状态的最大值。 正确性证明 证明在处理完前 iii 个装置后，对于每个 j∈{0,1,2}j\in\{0,1,2\}j∈{0,1,2}，状态 fjf_jfj 都等于所有末尾连续选择 jjj 个装置的合法方案中的最大能量总和；如果这一类方案不存在，对应状态为负无穷。 当 i=0i=0i=0 时，还没有处理任何装置。只有一个都不选择的方案，能量为 000，末尾连续选择数量为 000。因此 f0=0f_0=0f0 =0、f1=f2=−∞f_1=f_2=-\inftyf1 =f2 =−∞，结论成立。 假设处理完前 i−1i-1i−1 个装置后结论成立，考虑第 iii 个装置。 若不选择第 iii 个装置，则新的末尾连续选择数量为 000。此前任意合法方案都可以直接跳过它，所以新状态的最优值为 g0=max⁡(f0,f1,f2)g_0=\max(f_0,f_1,f_2)g0 =max(f0 ,f1 ,f2 )。 若选择第 iii 个装置，且新的末尾连续选择数量为 111，则此前末尾连续选择数量必须为 000；反过来，任意属于 f0f_0f0 的合法方案选择当前装置后，都恰好属于这一类。因此新状态的最优值为 g1=f0+aig_1=f_0+a_ig1 =f0 +ai 。 若选择第 iii 个装置，且新的末尾连续选择数量为 222，则此前末尾连续选择数量必须为 111；任意属于 f1f_1f1 的合法方案选择当前装置后，都恰好属于这一类。因此当 f1f_1f1 可达时，新状态的最优值为 g2=f1+aig_2=f_1+a_ig2 =f1 +ai ；否则这一类方案不存在。 此前末尾连续选择数量为 222 的方案，继续选择当前装置会违反限制，因此不能产生合法的新状态。上述三个转移覆盖了处理完前 iii 个装置后的全部合法方案，而且各自取到了对应类别中的最优值，归纳结论成立。 处理完全部 nnn 个装置后，所有合法方案都属于这三类之一，空选方案也被保留。因此，输出 max⁡(f0,f1,f2)\max(f_0,f_1,f_2)max(f0 ,f1 ,f2 ) 就是满足要求的最大能量总和。 复杂度分析 每个装置只进行常数次比较和加法，时间复杂度为 O(n)O(n)O(n)。 算法只保存三个旧状态、三个新状态及少量变量，读入能量后立即处理，空间复杂度为 O(1)O(1)O(1)。 参考代码 D. 三轨信号 解题思路 题意分析 设共有 nnn 天，第 iii 天三种模式的基础分分别为 ai,bi,cia_i,b_i,c_iai ,bi ,ci 。每天有三种选择，最直接的做法是枚举全部 3n3^n3n 种安排。可以用深度优先搜索依次决定每天的模式，选择时加上当天基础分，再减去与前一天有关的切换费用。在搜索过程中累计得分，枚举完全部天数后更新答案。这种方法适合天数很少的情况，但无法处理 n=100000n=100000n=100000 的数据。 观察切换规则可以发现，决定第 iii 天的得分变化时，只需要知道第 i−1i-1i−1 天选了什么模式。更早几天的模式，只通过已经累积的得分影响答案。 假设有两种前 i−1i-1i−1 天的安排，它们最后一天都选 A，但累计得分不同。此后接上完全相同的安排时，两者获得的后续基础分、支付的后续切换费用都相同。因此，原本得分较低的安排始终不会更优，可以只保留得分较高的安排。对于以 B、C 结尾的安排，也分别保留一个最大得分。 于是，按最后一天的模式分类，只需要维护三个动态规划状态。令 fiAf_i^AfiA 表示前 iii 天全部安排完，并且第 iii 天选择 A 时的最大累计得分；fiBf_i^BfiB 和 fiCf_i^CfiC 分别表示最后一天选择 B、C 的对应最优值。 第一天没有切换费用，因此初始化为 f1A=a1,f1B=b1,f1C=c1.f_1^A=a_1,\qquad f_1^B=b_1,\qquad f_1^C=c_1. f1A =a1 ,f1B =b1 ,f1C =c1 . 对于第 iii 天，如果今天选 A，昨天可能选 A、B 或 C。昨天选 A 时保持不变，不扣费用；昨天选 B 时，需要扣除 B 到 A 的费用 baiba_ibai ；昨天选 C 时，需要扣除 C 到 A 的费用 caica_icai 。再加上今天的基础分 aia_iai ，得到 fiA=ai+max⁡(fi−1A, fi−1B−bai, fi−1C−cai).f_i^A=a_i+\max\left(f_{i-1}^A,\ f_{i-1}^B-ba_i,\ f_{i-1}^C-ca_i\right). fiA =ai +max(fi−1A , fi−1B −bai , fi−1C −cai ). 同理，今天选 B 时，需要考虑 A 到 B、保持 B、C 到 B 三种情况： fiB=bi+max⁡(fi−1A−abi, fi−1B, fi−1C−cbi).f_i^B=b_i+\max\left(f_{i-1}^A-ab_i,\ f_{i-1}^B,\ f_{i-1}^C-cb_i\right). fiB =bi +max(fi−1A −abi , fi−1B , fi−1C −cbi ). 今天选 C 时，需要考虑 A 到 C、B 到 C、保持 C 三种情况： fiC=ci+max⁡(fi−1A−aci, fi−1B−bci, fi−1C).f_i^C=c_i+\max\left(f_{i-1}^A-ac_i,\ f_{i-1}^B-bc_i,\ f_{i-1}^C\right). fiC =ci +max(fi−1A −aci , fi−1B −bci , fi−1C ). 计算当天状态时，只会用到前一天的三个状态，因此可以用三个变量滚动保存。代码中用 f0、f1、f2 分别保存以 A、B、C 结尾的旧状态，用 g0、g1、g2 保存新状态。先使用旧值计算三个新值，等三个新值都算完后，再一起替换旧值。如果算出新的 A 状态后就立即覆盖旧值，接下来计算 B、C 状态时就可能混入当天状态，破坏转移关系。 处理完全部 nnn 天后，最后一天可以是任意模式，所以答案为 max⁡(fnA,fnB,fnC).\max\left(f_n^A,f_n^B,f_n^C\right). max(fnA ,fnB ,fnC ). 这些状态都要求已经为前面每一天选择了模式，因此即使累计得分为负数，也必须保留实际得到的最优值，不能用 000 表示放弃安排。多天基础分和切换费用的累加会超出 int 范围，状态、基础分、费用以及转移中的差值统一使用 long long。 部分分说明： * 子任务 111（1≤n≤51\le n\le 51≤n≤5）：枚举每天的三种模式，共 3n3^n3n 种安排，逐一计算基础分与切换费用，取最大值。 * 子任务 222（完整数据，1≤n≤1000001\le n\le 1000001≤n≤100000）：按最后一天的模式维护三个状态，使用线性动态规划，并用滚动变量将额外空间压到常数。 实现步骤 1. 用第一天的三个基础分分别初始化三个状态；第一天不扣除切换费用。 2. 从第二天开始，依次处理当天的三个基础分和六个有方向的切换费用。 3. 使用前一天的三个状态，分别计算当天以 A、B、C 结尾的三个最大累计得分。 4. 三个新值全部算完后，再统一替换三个旧状态，继续处理下一天。 5. 处理完第 nnn 天后，输出三个状态中的最大值。 正确性证明 对已处理的天数 iii 进行归纳，证明算法保存的三个状态分别等于前 iii 天以 A、B、C 结尾的最大累计得分。 当 i=1i=1i=1 时，只有一天，每种结尾模式对应唯一的选择。第一天没有切换费用，因此三个状态分别等于 a1,b1,c1a_1,b_1,c_1a1 ,b1 ,c1 ，与定义一致。 假设处理完第 i−1i-1i−1 天时，三个状态均已正确。考虑第 iii 天选择 A 的任意合法安排，前一天的模式一定是 A、B、C 中的一种。 如果前一天是 A，则今天不扣切换费用，最优得分为 fi−1A+aif_{i-1}^A+a_ifi−1A +ai 。如果前一天是 B，则今天扣除 baiba_ibai ，最优得分为 fi−1B−bai+aif_{i-1}^B-ba_i+a_ifi−1B −bai +ai 。如果前一天是 C，则今天扣除 caica_icai ，最优得分为 fi−1C−cai+aif_{i-1}^C-ca_i+a_ifi−1C −cai +ai 。根据归纳假设，这三种情况下使用的前一天状态都是各自类别中的最优值，且每一种转移都对应合法安排。三种情况覆盖了今天选择 A 的所有安排，因此取最大值恰好得到 fiAf_i^AfiA 。 今天选择 B、C 时，同样按昨天的三种模式分类，并扣除对应方向的切换费用，就能分别得到正确的 fiB,fiCf_i^B,f_i^CfiB ,fiC 。算法先算出全部新状态，再替换旧状态，因此三条转移都基于正确的第 i−1i-1i−1 天状态，归纳结论成立。 处理完第 nnn 天后，每一种合法安排都以 A、B、C 中的一种模式结束。三个状态覆盖了所有合法安排，取其中最大值就是题目要求的最大最终得分。 复杂度分析 每天计算三个状态，每个状态只比较三个来源，因此总时间复杂度为 O(n)O(n)O(n)。 输入逐天读取，只保存前一天和当天的三个状态及当前输入的常数个数值，因此额外空间复杂度为 O(1)O(1)O(1)。 参考代码