专栏文章

9 月做题记录

SSkeleton_Huo
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minw0sx4
此快照首次捕获于
2025/12/02 09:16
3 个月前
此快照最后确认于
2025/12/02 09:16
3 个月前
查看原文

R14

T1

略。

T2

通过一些观察，我们发现操作序列一定形如 C P C P P P C P P ...。
我们将每一段长度记为 aia_i，有 kk 段，则字符串长度为 ∏iai\prod_i{a_i}，花费为 ∑iai\sum_i{a_i}。
我们需要在满足 ∏iai≥N\prod_i{a_i} \ge N 的前提下，最小化 ∑iai\sum_i{a_i}。
根据均值不等式，aia_i 一定越平均越好，我们也可以用调整法证明：a={t,t,…,t+1,t+1,… }a = \{t,t,\dots,t+1,t+1,\dots\}。
注意到 k≤log⁡Nk \le \log N，直接枚举。tt 和 t+1t+1 的分界点也可以直接枚举。然后二分出 tt 的值。
总 O(log⁡3Nlog⁡log⁡N)O(\log^3 N \log\log N)。

T3

首先染色容易想到倒着做，这样变化会少不少。
然后区间 DP，不过显然我们只需关心区间长度，于是 fi,j,0/1f_{i,j,0/1} 表示使用到倒数第 ii 个颜色，区间长度为 jj，终点位于左/右端点的方案数。
可以更新到 fk,x,0/1f_{k,x,0/1}，其中颜色 [k+1,i−1][k+1,i-1] 在 jj 内部跳，kk 跳出去。转移可以考虑用 gk,xg_{k,x} 表示否能转移到，套一层 DP 计算即可。

T4

我们设 fif_i 为经过节点 ii 的路径个数。显然 ANS≥max⁡fiANS \ge \max{f_i}。
我们经过手玩和大胆猜想，试图证明可以取等。
考虑归纳构造的套路。如果我们能选出一个集合，使得 max⁡fi\max{f_i} 减 11，那么我们就完成了证明与构造。
显然选择方法就是选择若干无交路径，覆盖所有 f=max⁡fif = \max{f_i} 的点。再具体一点，我们每次选择 ff 最大的最浅点 uu，并选择以其为 LCA 的路径。这样的路径总是存在的，否则 uu 的父亲会是更浅的符合要求的点。该过程可以用树剖 + 线段树加速。

R15

T1

数数问题，考虑清楚方案的生成方式就不难。

T2

神秘构造题。
考虑最大效用的发挥每条线的作用。当一条线满足 (Δx,Δy)=1(\Delta x, \Delta y) = 1 时，该线在每列都能覆盖 22 格。
于是第一步连 (0,0)(0,0) 与 (n,n−1)(n, n-1)，往下每次两端点移动两个就能高效覆盖下半部分。
上半部分是对称的，我们可能会先考虑连 (0,0)(0,0) 和 (n−1,n)(n-1,n)。但由于最后边缘部分会有漏的，要用额外两条线补充，所以这样构造可能 ⌈(n−1)/2⌉+⌈(n−1)/2⌉+2>n+1\lceil (n-1)/2 \rceil + \lceil (n-1)/2 \rceil + 2 > n + 1。
所以我们先连 (0,1)(0,1) 和 (n−2,n)(n-2,n)，这样就没问题了，⌈(n−1)/2⌉+⌈(n−2)/2⌉+2≤n+1\lceil (n-1)/2 \rceil + \lceil (n-2)/2 \rceil + 2 \le n + 1。

T3

神秘计算几何 + 数数。
首先凸多边形的面积计算可以拆成三角形，我们需要锚定一个点，注意这个点是任意的，并不一定要是给定点中的，明白这一点才会有后面灵活的贡献拆解。
要注意边的方向问题，我们规定边一律指向顺时针方向，然后可以用原点到边两端点的叉积判断正负。
于是我们发现一条边对应一个三角形，依次考虑每条边的贡献，O(n4)O(n^4) 地枚举所有边，考虑它在多少个 pp 中出现，可以 O(n)O(n) 解决。

T4

神秘贪心 + 推式子 + DS。
把 00 变成 −1-1 以变成前缀和问题。
先考虑解决单次查询的静态问题。我们有一个贪心解法：
  1. 从左到右依次选数，如果某次选数会使得前缀和 <0< 0，删除该数。
  2. 在已经得到的序列上倒着如是做一遍。
其正确性是显然的，最优性的证明也不难。
用 aia_i 表示前缀和，bib_i 表示后缀和。因为这个问题有多次查询和修改，我们需要看看有没有从这两个数组出发简便得到答案的方法。
OBS 1：第一次删除的个数为 max⁡i−ai\max_i -a_i。
每次删除都相当于 aa 的后缀 +1+1，通过一定手模不难看出。
令第一次删除后的后缀和为 bi′b'_i，则第二次删除个数为 max⁡i−bi′\max_i -b'_i。
OBS 2：bi′=bi+max⁡j=1n{−aj}−max⁡j=1i−1{−aj}b'_i = b_i + \max_{j=1}^{n}\{-a_j\} - \max_{j=1}^{i-1}\{-a_j\}。
注意删除的都是 −1-1，所以是显然的。
一共删除 max⁡i=1n{−ai}+max⁡i=1n{−bi′}=−min⁡1≤i<j≤n{ai+bj}\max_{i=1}^n\{-a_i\} + \max_{i=1}^n\{-b'_i\} = -\min_{1 \le i < j \le n}\{a_i + b_j\}。
这里需要一些 max⁡\max 运算技巧，与 ∑\sum 类似。
我们容易看出这其实是一个最大子段和。

证明：P10334 [UESTCPC 2024] 饮料

神秘贪心题，至今不会证。

P10875 [COTS 2022] 游戏 M

连通性相关。

P10680 [COTS 2024] 双双决斗 Dvoboj

根号分治，小块分治数组，大块递归。

AT_arc201_c [ARC201C] Prefix Covering

字符串优先考虑 Trie。

AT_arc201_b [ARC201B] Binary Knapsack

神秘贪心题，考虑奇偶性。
若 WW 为奇数，不妨先选择一个价值最大的 X=0X=0 的物品，然后把 WW 减 11。
于是 X=0X=0 的物品只能选偶数个，我们可以贪心的两两合并成 X=1X=1 的物品，如果剩下单个就舍弃。
此时 WW 和所有物品的重量都是偶数，可以全部除以 22。

AT_arc203_c [ARC203C] Destruction of Walls

比较复杂的数数题。有一定的转化和巧思。
自己做的时候把路径长 =H+W= H + W 的情况漏了。
https://www.luogu.com.cn/article/zvf63hbo

难：AT_arc202_c [ARC202C] Repunits

神秘数学题。
用到 min-max 容斥和莫比乌斯反演，还有一点和式手法。
https://www.luogu.com.cn/article/w2d98cnb

AT_arc197_c [ARC197C] Removal of Multiples

观察到删除并不会使数过于稀疏，所以可以直接暴力线段树。
严谨点的说法是质数 pp 一定在 Ai=pA_i = p 的时候被删除，所以至少大约第 QQ 个质数还留着，线段树开到 3e63e6。

AT_abc209_e [ABC209E] Shiritori

字符串双端作点，字符串作边。注意不要用字符串作点，不然边数很多，而且不是标准的有向图游戏。
初始时无出边的点必败。在删点过程中，没有被标记为必胜，但无出边的点也必败。
然后将确定状态的点删去，为什么？
  1. 如果必败，其前驱必胜，该打的标记都打完了，留在图中没有用。
  2. 如果必胜，其前驱一定会避免走到该点，其存在与否不会影响前驱的必胜与必败。
最后未删的点是平局的，因为每个点在原图都没有必败后继（否则它就是必胜的，会被删去），且它不会走到原图的必胜后继，否则就输了。然后此时没有无出边的点，所以会永远周旋。

难：AT_arc165_f [ARC165F] Make Adjacent

先考虑局部，对于两个数字，有 aabb、abab、abba 三种情况。其中前两种都是变成 aabb 最优，后一种随意，操作次数的下限分别是 0,1,20, 1, 2。
我们可以证明，存在方案使得对于每一对数字都能取到下限。
解释：我们每次操作只会影响到两个数字间的相对关系，所以这里的下限是影响了两个数字间相对关系的操作次数。显然总下线就是任意两个数字的下限和。（要理解清楚需要灵活的视角，主体是一个机械的过程，这个过程中会不连续地对不同数对间的操作代价产生贡献）
若 Ra<RbR_a < R_b 且 La<LbL_a < L_b，则连边 a→ba \rightarrow b，求字典序最小的拓扑序。
这样边数是 O(n2)O(n^2) 的，由于是二维偏序，所以可以用 CDQ 优化建图或者主席树优化建图（不会）。

难： AT_arc199_c [ARC199C] Circular Tree Embedding

TT 为树，PP 为排列。
OBS：随意钦定一个根节点，(T,P)(T,P) 合法当且仅当 TT 的任意子树在 PP 上是连续的（环的意义下）。
证明不难，必要性可以看出，充分性可以归纳考虑。
对元素做映射，使得 P1=0,1,…,nP^1 = 0, 1, \dots, n。这样区间就和值域吻合了，后面更加方便。
令 fl,rf_{l,r} 表示 P1P^1 的 [l,r][l,r] 区间的树的个数。
转移考虑以 midmid 为根，左右是区间构成的森林，用 gl,rg_{l,r} 表示。
fl,r=∑midgl,mid−1gmid+1,rf_{l,r} = \sum_{mid}{g_{l,mid-1} g_{mid+1,r}}
考虑到还有其他排列的限制，我们预处理值域 [l,r][l,r]，是否在所有区间上都是连续的。它只用于判断 fl,rf_{l,r} 是否是 00，因为这无法通过方程直接算出。
其他排列的限制看起来存在感有点低，但确实如此。

好：CF1628D2 Game on Sum (Hard Version)

博弈论 DP + DP 优化。
首先博弈论 DP 一定画出决策树，这样十分清晰。
设 fi,jf_{i,j} 表示 ii 次减法，jj 次加法的最终得分。
fi,j=max⁡kmin⁡(fi−1,j−k,fi,j−1+k)f_{i,j} = \max_k{\min(f_{i-1,j}-k, f_{i,j-1}+k)}
画出 min⁡(fi−1,j−k,fi,j−1+k)\min(f_{i-1,j}-k, f_{i,j-1}+k) 关于 kk 的图象，发现十分优美。
得到
fi,j=(fi−1,j+fi,j−1)/2f_{i,j} = (f_{i-1,j} + f_{i,j-1}) / 2
通过一定展开，发现可以把贡献拆开计算，答案跟路径计数有关。
小结：很久没见过跟函数图像有关的 DP 优化了，还是要多尝试。

难：CF843D Dynamic Shortest Path

我们为什么构建 Johnson 图？
因为在这个图上的最短路都是 00。
每次给 cc 条边加权，最短路至多增加 cc。这样我们就可以不用 priority_queue 而是用桶来实现 Dijkstra，使得总复杂度降一个 log⁡\log。
我陷入了什么误区？
我以为 Johnson 图中选取的势能是增加完 cc 条边的边权后的 disdis。但这样显然是无法直接得到的（不然我不就直接找到最短路了吗？）。
事实上我们选取的 disdis 是加权前的。
这个误区的根本是什么？
Johnson 图只要求一个图和一个势能即可。对于图和势能的关系没有任何要求，而我误以为势能一定要选择图的最短路。
放到这里，我们用的是加权后的图和加权前的 disdis 构成 Johnson 图。加权的过程不改变势能。
怎么避免？
  1. 理解清楚势能与图的关系。
  2. 一步一步了解我们需要做什么。

难：CF1163F Indecisive Taxi Fee

代码较难
我们有四种情况：
  1. 改小，边在最短路。直接减。
  2. 改小，边不在最短路。全最短路和过边最短路取 min⁡\min。
  3. 改大，边不在最短路。不用管。
  4. 改大，边在最短路。最复杂，展开讨论。
首先我们能想到如果不是最短路必经边，并不会影响答案。但仍避免不了必经边的 case。所以我们不用管必经与否。
朴素的想法是处理出删去每一条最短路上的边后的最短路。最短路有多条，但钦定一条比较方便解决问题，记为 PP。
我们得到一个线性结构（最短路），考虑维护一个线性 DS 解决这个问题，线段树即可做到。
具体地，我们对于每个点 uu，记录 LuL_u 为 11 到 uu 的最短路与 PP 的公共前缀的最右端的边的编号。这里的两条最短路在同一个最短路树上，也就是没有构成环。RuR_u 与之对称。
为了方便，我们用 Le,Re,e=(u,v)L_e, R_e, e = (u,v) 分别表示 Lu,RvL_u, R_v。
我们枚举每条边 (u,v)(u,v)，对 PP 中 LuL_u 到 RvR_v 之间的边进行 checkmin。整理成数据结构题，可以用吉司机树在线做，或者普通线段树离线做（从大到小枚举避免 checkmin），或者 multiset 离线做（扫描线）。
这样为什么是对的？
我们只需证明：对于任何一个 PP 上的边 ee 和 ee 的删边最短路在 PP 之外的部分 QQ，存在 e′∈Qe' \in Q 更新了 ee。
假设所有的 e′∈Qe' \in Q 都没有更新 ee，则在 QQ 上一定存在一对相邻的边 f,gf, g，RfR_f 与 LgL_g 在 PP 上构成的区间包含了 ee。
我们记 f,gf,g 用于更新的最短路分别为 df,dgd_f, d_g，我们可以调整一下两条最短路使得 df+dg>df′+dg′d_f + d_g > d'_f + d'_g，则至少有 df>df′d_f > d'_f 或 dg>dg′d_g > d'_g。矛盾。
关于求 L,RL,R：
求最短路树即可。注意倒着的时候要固定 PP 那一部分。

P3530 [POI 2012] FES-Festival

考虑极端情况是分析问题的一般方法。我们考虑 DAG 和 SCC 的情况。
对于 DAG：显然解在数轴上可以无限拉长，只要按字典序排列。所以答案就是点数。
对于 SCC：显然变量两两之间的差值都有了上下界。
OBS：这个图是很紧凑的，边权都是 0,1,−10,1,-1，所以对于任何一个解，变量的数轴上的分布都是连续的。
现在我们的任务变成了，最大化两个变量之间的差值。
任意两个变量之间的差值的最大值是它们之间的最短路，这是一个经典结论。
于是我们的答案就是任意两点最短路的最大值，还要 +1+1，因为要算上起点的 00。
一般图：答案就是所有 SCC 的答案加起来，因为 SCC 由 DAG 连接，区间之间可以被扯得无限长。

AT_abc345_f [ABC345F] Many Lamps

首先奇数无解。
My solution：首先观察到我们只需要找一棵生成树即可，因为非树边是可以通过树上路径平替的，另外还发现我们可以改变树上任意两点的状态。然后按照 DFS 序构造，一次点亮一个儿子和父亲。可能会在叶子上遇到孤立点，我们记下来等 DFS 到一个不亮的点再一起点亮。
Other solution：我们每次操作都是让亮的灯数 +2,0,−2+2,0,-2。用中值定理的思想，00 到 maxkmaxk 的所有值我们都是可以构造出来的。还是找生成树，具体的构造方法 DFS 从子树开始构造，每次都操作当前点和一个儿子，保证儿子都点亮。
这种中值定理的思想比较重要。

典：CF888G Xor-MST

首先建 Trie。
Kruskal 做法：观察到对于 Trie 上的两棵子树间连边显然不如子树内连边优，但要求连通，所以只要有一条。于是可以递归连边，连跨子树边的时候用启发式合并或者直接合并都行（因为树高有限），合并的时候贪心走 Trie。
Boruvka 做法：求一个块的最小边的时候先把块内的点从 Trie 上删掉，然后对每个点贪心走 Trie，最后加回来即可。

难：CF2041N Railway Construction

最小生成树经典结论
囊的过分的一道题（
考虑根号分治。
Tips：
  1. 认为 nn 与 mm 同阶。
  2. 由于禁用边和完全图的性质，本题复杂度分析有大量均摊。
先算静态问题：
将点按 aa 排序，先进行一轮魔改 Boruvka。前 BB 个点不连安全边，后面的点只连前 BB 个点。
具体地，类似 mexmex，只有前面若干个禁用边连续的时候才会起效，于是我们判断当前点的第 ii 条禁用边是否连向 ii 即可。
这样会形成若干菊花图和若干单点。菊花图中，前 BB 个点作花心。单点数为 m/Bm / B。m+m/B>2mm + m/B > 2\sqrt m，B=mB = \sqrt m 取最小。
故总块数 O(m)O(\sqrt m)。
处理出两两块之间的最小边，跑不带堆优化的 Prim 就完成了。
具体地，我们记块 p,qp, q 之间的边数为 mp,qm_{p,q}，由完全图的性质，我们要尽量选择 pp 中小的点去连 qq 中最小能连的点，而这些禁用边至多 ban 掉 pp 中前 mp,qm_{p,q} 个点，我们扫描前 mp,q+1m_{p,q}+1 个点即可。总复杂度是 O(m)O(m) 的。
关于怎么求最小能连的边，既然有了根号，不妨大胆些。用一个 vector 存下任意两个块之间的边。然后枚举每一对块，利用边现场建新图，然后用上面的方法即可。
复杂度 O(n)O(n)。
动态问题：
如果删去的是 MST 上的叶子，显然是容易的。
而非叶子个数为 O(n)O(\sqrt n)，原本的花心，加上 Prim 每步至多产生 22 个非叶子。
所以如果删非叶子，直接重跑 MST。
总复杂度 O(nn)O(n\sqrt n)。
无解情况（图不连通）：
  1. n=2n=2 直接输出两个 00。
  2. 只有一个孤立点，则除删该点外，其他都是 −1-1。
  3. 否则所有都是 −1-1。
小结：
根号方法其实是万用的，它能让很多暴力具有优秀的复杂度，又不过分依赖题目的性质，不妨多多尝试。
代码细节：
非常非常多。这里仅列出现 TLE 后的问题。
  1. t 不能太小，否则 m 过小的时候就会有问题，可以取 max(n,m)。
  2. 清除 f 的过程忘了以 cnt 为上限，导致复杂度假了。这启示我们对于从代码不能明显看出复杂度的题，要用一个计数器来检测一下计算量。
  3. define int long long 的常数有点大，卡常时要关掉。
code

AT_abc424_f Adding Chords

赛场上想到了 Hash 做法，可惜太颓了不想写。
首先断环成链，这一步无需任何代价。考虑给边的两端打赏正负标记，查询时只需求区间和就能判断是否有交。
刚开始想用 11 和 −1-1，但显然不同边会相互影响，为了去除影响，我们给每个点赋随机权值（或者 2i mod P2^i \bmod P），就解决了。
这很像某和哈希。
（哈希就是给结构赋值）

AT_arc206_d LIS ∩ LDS

神秘构造题。题解
比较合理的做法是爆搜出小规模的情况，人肉构造还是太吃注意力了。

典：P12444 [COTS 2025] 发好奖 / Hijerarhija

DFS 序的树形 DP。
挺有收益的一道题。虽然之前做过类似的题，但并不熟悉。
小结：
  1. 这类题通常有两个转移方向：子树内、子树外。
  2. 转移只需要最简转移，当前点不选的方案也可以更新到子树内，但我们不用管。就好像 LIS 也可以一次拼接两个数，但没必要。
  3. 转移方向跟当前点的选择有关。我们当然可以搞个 0/1/20/1/2 位来辅助。但更巧妙的是把状态描述改为左闭右开区间：fi,jf_{i,j} 表示考虑 DFS 序中 [1,i)[1, i) 人，使用 jj 奖金的最大积极性。
树上背包的经典优化技巧能不能用于这道题？

P12449 [COTS 2025] 吸尘 / Usisavač

又被构思题创飞了。
我们定义高度 hih_i 为 ii 往子树中能走的最远距离，did_i 为深度。
经过一定的手玩，我们发现在高度大的位置，每条边至少经过 44 次。并且下界可达。
而高度小的边（其较深端点 ii 满足 hi<rh_i < r）至少 22 次。并且下界可达。
又由于 DFS 的原因，又一条从 11 到叶子的经过次数还能再 −1-1。我们让这个叶节点为最深的点即可取到最优解。
ANS=4(n−1)−2∑i[hi<r]−max⁡idiANS = 4(n-1) - 2\sum_i [h_i<r] - \max_i d_i
其中 2∑i[hi<r]2\sum_i [h_i<r] 是仅和 rr 有关的，可以用双指针轻松求解，用个数组存下来（离线）。

P12359 [eJOI 2024] 古迹漫步 / Old Orhei

虽然很简单，但是线段树优化游走还是有点意思的。
因为 e 数组 M 写成 N，调了半天。越界也是可能 WA 的，如果发现有玄学错误，记得检查边界。

难：P12448 [COTS 2025] 观草 / Trava

套路数据结构题。
我还是喜欢从代数角度推理。
做法一：
常见技巧：
∑iai=∑t≥1t∑i[ai=t]=∑t≥1∑i[ai≥t]\sum_i{a_i} = \sum_{t \ge 1}{t\sum_i{[a_i=t]}} = \sum_{t \ge 1}{\sum_i{[a_i \ge t]}}
对于本题，
∑1≤i≤N−k+1max⁡i≤j≤i+k−1aj=∑t∑1≤i≤N−k+1[max⁡i≤j≤i+k−1aj≥t]\sum_{1 \le i \le N-k+1}{\max_{i \le j \le i+k-1}{a_j}} = \sum_t{\sum_{1 \le i \le N-k+1}{[\max_{i \le j \le i+k-1}{a_j} \ge t]}}
但是这个 max⁡≥t\max \ge t 并不好处理，我们不妨转换成 min⁡≥t\min \ge t。拿最大值减去 aia_i 即可。
这样我们的目标就是对每个 tt，求满足 [ai≥t]=1[a_i \ge t] = 1 的长为 kk 的区间数量。
我们可以维护 cntktcnt^t_k 为长为 kk 的极长区间数量，sumktsum^t_k 为长度和。但我们不可能每次都扫一遍 tt，所以我们维护的 cntcnt 和 sumsum 为各个 cntktcnt^t_k 和 sumktsum^t_k 的和。
Query(k)=∑i≥k(sumi+(−k+1)cnti)Query(k) = \sum_{i\ge k}{(sum_i + (-k+1)cnt_i)}
而且 tt 的范围很大，我们可以将 aa 排序后，每次加入一个 aia_i 的时候，把历史中的 tt 都结算一下（就是几何的扫描线）。这里也可以用左闭右开技巧，每次只结算历史的，而不结算当前的，这样好写。
还需要一个并查集来维护。
此时我们解决的静态问题。
关于修改，注意我们修改的 aa 的定义，所以变成 −1-1，也就是在我们对 tt 扫描时出现得晚了一个单位。这个对 cntcnt 和 sumsum 的影响是在可控范围内的，写一个二分和区间修改即可。
做法二：
类似 NOIP2024 T4，计算每个点的贡献，最后好像可以用 CDQ 处理修改，但我不会（

CF2151E Limited Edition Shop

我们不妨重标号使得 b=[1,2,…,n]b = [1,2,\dots,n]。记 SS 为 Alice 选择的物品集合。
OBS：SS 合法 ⇔∀i<j,ai>aj\Leftrightarrow \forall i < j, a_i > a_j 若 aj∈Sa_j \in S，则 ai∈Sa_i \in S。
换言之，若 ai∉Sa_i \notin S，则 aj∉Sa_j \notin S。
于是 fi,j=f_{i,j} = 考虑 aa 的前 ii 个元素，最大 ∉S\notin S 的元素为 jj 的最大价值和。
转移：考虑 fi−1,jf_{i-1,j} 向后转移。若 ii 被选择，转移到 fi,jf_{i,j}，需要满足 j<aij < a_i；若不选择，转移到 fi,max(j,ai)f_{i,max(j,a_i)}，不需要条件。
max⁡\max 可以分讨展开，接下来用线段树维护 DP 数组即可。
小结：
我们设计状态的时候，把限制较为直接的搬进状态里是更有利于转移的。
原本的想法：fi,jf_{i,j} 表示前 ii 个元素，只考虑 ≤j\le j 的元素的最大价值和。
它无法进行优化，甚至 O(n2)O(n^2) 都要上数据结构优化。

难：P11239 [KTSC 2024 R2] 跳跃游戏

暴力 DP：fi=f_i = 跳到 ii 的最大得分。fi=max⁡(fi−1,fi−K+Ai−K)f_i = \max(f_{i-1},f_{i-K} + A_{i-K})。
为了方便，把 AA 整体右移一下。fi=max⁡(fi−1,fi−K+Ai)f_i = \max(f_{i-1},f_{i-K} + A_i)。
Trick 1：注意到我们只关心，后 KK 位的值，所以可用循环数组。更新时，fi mod K←max⁡(fi mod K+Ai,f(i−1) mod K)f_{i \bmod K} \leftarrow \max(f_{i \bmod K} + A_i, f_{(i-1) \bmod K})。等价于 +Ai+ A_i 后与前一个数 chkmax。
这个 trick 是经典的。
OBS 1：AA 的相同值极长段的数量是 O(Q)O(Q) 的。
我们考虑把若干个连续的、相同的 AA 合在一起转移。
CPP
   L-----
---x-----
---y-----
---z-R
该图是一个 AA 段在 ff 上的投影形态。L 和 R 是端点，x、y、z 都是是与 L 对齐的位置。
我们批量处理第一行：
OBS 2：对每一位 +Ai+A_i 再与前一位 chkmax 等价于，集体 +Ai+A_i 后再集体 chkmax。
于是我们可以用线段树维护（先假设 KK 比较小）。由于 ff 是单增的，所以循环之后就是两段单增拼到一起，chkmax 可以通过二分 + 区间覆盖实现。
贪心：从 x 开始，不需要考虑 fi−1f_{i-1} 的转移情况，因为总是不如 fi−Kf_{i-K} 优。
于是从 x 到 z 都可以批量加，最后再补加 z 到 R。
离散化：离散化是数据结构优化后考虑的，此时的 KK 比较大，但由于 AA 的段数有限，所以投影到 ff 上的关键点也有限。

弱项：P11915 [PA 2025] 瞬间传送 / Teleport

枚举答案是最优化问题的常见技巧，其优化就是二分答案。
从大到小枚举能获得更多信息。
我们设当前枚举到的答案为 ansans。我们需要检查是否存在 00 边 (u,v)(u,v) 使得任意 (i,j)(i,j) 的距离 ≤ans\le ans。
我们考虑用 (i,j)(i,j) 淘汰 (u,v)(u,v)。
若 d(i,j)>ansd(i,j) > ans，设 d(i,u)≤d(i,v)d(i,u) \le d(i,v)，则需要满足 d(i,u)+d(v,j)≤ansd(i,u)+d(v,j) \le ans，否则 (u,v)(u,v) 就是不可行的。可以证明，我们不需要考虑 d(i,v)+d(u,j)d(i,v)+d(u,j) 的情况，因为这种方案不如不用 (u,v)(u,v)。
我们可以枚举 ii，对每一个 vv，维护 max⁡d(i,j)>ansd(v,j)\max_{d(i,j)>ans}d(v,j)（看题解的时候没理解到这里也是跟 ii 有关的）。
这里的实现需要一些均摊。
小结：
都是一些很朴素的程序设计技巧，但显然我并不熟练。

CF786B Legacy

线段树优化建图模板。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...