周航锐 hehezhou、罗恺、叶李溪、黄洛天、许庭强题目选讲
周航锐 hehezhou
110.【PR 5】双向奔赴
111.AT_agc043_d Merge Triplets
112.【JOI Open 2020】黑白点
113.apio2022 游戏
考虑到关键点连成一条线，容易知道要维护 \(L_i\) 表示能到 \(i\) 的最大点，\(R_i\) 表示 \(i\) 能到的最小点。
加入边 \((u,v)\) 后暴力维护更新，容易势能分析得到 \(\mathcal O((n+m)k)\)。
当存在 \(L_i\ge R_i\) 时结束。
讨论一下 \([L_i,R_i]\) 对于 \((u,v)\) 的关系：
-
若无交，当 \(v\) 在 \(u\) 左时结束，否则不更新；
-
若有交，会产生一些更新：
- 部分交且 \(u\) 在 \(v\) 左时；(1)
- 相互包含时；(2)
考虑对关键点分块，这样相当于只有根号个关键点，当存在左右端点在统一块中的情况时预警，\(\mathcal O((n+m)\sqrt k)\)。
当一个预警点更新非预警点时，不能更新就跳过，能更新就会将这个点也预警了，均摊到每个点是 \(\mathcal O(1)\) 的。
预警点之间更新是容易的。
考虑用一个能判断有无交且有交时能处理更新的结构。
沿用上面做法，设计 \(k=2\)，即分成两个块，当跳到其中一个块时继续分块，时间复杂度近似于 \((n+m)\cdot 层数\cdot 叉数\)，考虑分治结构，将每个区间放到线段树上极小的包含它的区间上，处理情况一时，\(u,v\) 的线段树节点不变。
处理情况二时，容易谈论将 \(u\) 或 \(v\) 下放，势能分析得到 \(\mathcal O((n+m)\log n)\)。
每个点无须记录实际的 \(L,R\) 值，只需记录线段树节点编号。
114.UOJ749 【UNR #6】稳健型选手
考虑你能取的数的所有可能，发现长为 \(2i-1\) 的前缀你最多可以取 \(i\) 个，于是长为 \(n-(2i-1)\) 的后缀你至少取 \(Sum-i\) 个。
于是可以从前往后反悔贪心，每加入两个，弹出最小值，也可以从后往前。
将询问猫树分治，现在要将两区间的答案合并，二分计算即可。
时间复杂度 \(\mathcal O(n\log^2 n)\)。
115.P5327 [ZJOI2019] 语言
116.UOJ814 鸽子收费站
117.THUPC2024 I k 星连珠
118.CCPCF2024 K
119.CCPCF2024 L
120.【PR 4】到底有没有九
设这个不含 \(9\) 的数为 \(w\)，则 \((10^k-1)|w\)，相当于将 \(w\) 每 \(k\) 位切一段，每一段的和要被 \(10^k-1\) 整除。
段数 \(c\) 应该小于 \(\frac{x}{k},x\ge 18\)，\(c\) 个长为 \(k\) 的数加起来，和不超过 \(c\times 10^k\)，找出这个范围内 \(10^k-1\) 的倍数，然后数位 dp 即可。
121.【UNR #6】小火车
122.UOJ NOI Round #6 Day1 A. 面基之路 加强版
123.ECF2024 A
124.IOI2022 无线电信号塔
125.【PR #5】和平共处
罗恺
130.Nanjing22C Fabulous Fungus Frenzy
131.CF1909G
132.CF1483E
133.UOJ608机器蚤分组
134.CF1523F
135.CF1566G
136.Jinan23F Say Hello to the Future
137.UOJ656霸占排行榜
138.Qinhuangdao23L Yet Another Maximize Permutation Subarrays
139.Guilin23A Easy Diameter Problem
140.CF1142E
141.CF1450G
142.Macau23G Parity Game
143.UOJ772 企鹅游戏
144.Nanjing23E Extending Distance
145.CF1246E
146.CF1329E
147.CF1621G
http://192.168.102.138/JudgeOnline/contest.php?cid=2156