（自用）ABC&&CF div2. 做题记录

· · 个人记录

ABC 417

D

高桥即将收到 N 份礼物。

高桥有一个名为“情绪值”的非负整数，每收到一份礼物，他的情绪值就会发生变化。每份礼物都有价值 P、情绪值上升度 A、情绪值下降度 B 三个参数，高桥的情绪值会根据这些参数按以下规则变化：

第 i\,(1 \le i \le N) 份收到的礼物的价值为 P_i、情绪值上升度为 A_i、情绪值下降度为 B_i。

有 Q 个询问，请回答所有询问。在第 i\,(1 \le i \le Q) 个询问中，给定一个非负整数 X_i，请回答以下问题：

当高桥最初的情绪值为 X_i 时，求他收到所有 N 份礼物后的情绪值。

sol

没看到 V = 500 好似喵。直接 f_{i,x} 表示 x 经历完 i 及以后的操作后的答案。对于询问超级大的 x 先把它降到 V 量级再查表即可。

E

给你一个简单相连的无向图 G ，有 N 个顶点和 M 条边。顶点编号从 1 到 N，第 i 条边连接点 U_i 和点 V_i。

在 G 中，找出从顶点 X 到顶点 Y 的字典序最小的简单路径。

也就是说，在满足以下条件的整数序列 P=(P_1,P_2,\ldots,P_{\lvert P\rvert}) 中，找出一条字典序最小的路径：

sol

贪心遍历。注意一个点退栈的时候不要还原mark，退栈代表这是死路，以后搜到了也不能走

F

有 N 个盘子，按照盘子 1、盘子 2、\ldots、盘子 N 的顺序从左到右排列。最开始，盘子 i（1\leq i\leq N）中有 A_i 个石子。

对这些盘子进行 M 次操作。第 i 次操作（1\leq i\leq M）会给出两个整数 L_i, R_i，依次进行如下操作：

对于 i=1,2,\ldots,N，请你求出 M 次操作全部结束后，每个盘子 i 上石子的期望个数，结果对 998244353 取模。

sol

观察一下第二个样例。想到单次操作实际上是把总和均摊到所有位置。进一步想到用区间推平&区间求和SGT维护所有位置的期望。

EX

ABC 419

D

给定长度为 N 的小写英文字母字符串 S 和 T，以及 M 对整数 (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M)。

请依次对 i=1,2,\ldots,M 执行以下操作：

请输出经过 M 次操作后的字符串 S。

sol

考虑当前位置被覆盖的次数的奇偶性即可。

E

给定一个长度为 N 的整数序列 A = (A_1, A_2, \ldots, A_N)。

你的目标是反复执行如下操作，使得对于 A 的每一个长度为 L 的连续子数组，其元素和都是 M 的倍数。

请你求出在达成目标前，最少需要执行多少次操作。

sol

怎么总是有一个*1700左右的东西做不出来。菜就多练那。

首先容易观察到 i \bmod L 相同的 a_i 应当 \bmod M 同余。所以现在只需要处理前 L 个。

使 \forall a_{i+kL} \equiv x \pmod M 的代价是可以计算出来的。考虑设 f_{i,j} 表示做完了前 i 组，\bmod M 意义下的和为 j 的最小代价。DP即可。2D/1D，复杂度 O(n^3)

F

给定 N 个小写英文字母字符串 S_1, S_2, \ldots, S_N，以及一个整数 L。

请你求出长度为 L 的所有小写英文字母字符串中，包含 S_1, S_2, \ldots, S_N 作为子串的字符串个数，答案对 998244353 取模。

sol

ACAM板子。滚存计数记得要清空

EX

给定一个包含 N 个顶点（编号为 1 到 N）和 M 条边的简单连通无向图。第 i 条边连接顶点 u_i 和 v_i。

对于每个 k=1,2,\ldots,N-1，请你求出从顶点 1 到顶点 N 恰好经过 k 条边的简单路径的数量。

sol1. 广义串并联图

相似题：P8276 [USACO22OPEN] Hoof and Brain P

首先数据范围告诉我们度数超过 2 的点不超过 20 个。发现若 deg = 1，则要么是终点要么是死胡同，直接把后者删掉。若 deg = 2 则对方案数没有贡献，直接缩起来并重标边权。最后直接暴力遍历缩好的图即可。

但感觉这个东西的复杂度实际有些玄学

sol2. 虚树

其实也是优化建图。把返祖边的端点拿出来建虚树，路径就可以刻画成在虚树上走一段叶向路径，再用前向边跳到某个后代。可以发现路径和选取的前向边集合是一一对应的。若不把链缩成虚树中的边，复杂度是 O(2^kn)，缩完以后变成 O(2^kk)，可以通过。

ABC 395

感觉打的比较好的一场

D

有 N 只鸽子（编号 1,2,\ldots,N）和 N 个巢（编号 1,2,\ldots,N）。初始时，鸽子 i（1 \leq i \leq N）位于巢 i 中。

接下来对鸽子进行 Q 次操作，操作分为以下三种类型：

请输出所有类型 3 的操作的结果。

sol

史题。显然不能交换两个巢里所有鸟。考虑交换巢的tag。建立一个位置到tag的映射以及其逆映射。对于题目给的tag，先用逆映射检索到其位置，再执行操作即可。

E

给定一个包含 N 个顶点和 M 条边的有向图。第 i 条边（1 \leq i \leq M）从顶点 u_i 指向顶点 v_i。

初始时，你位于顶点 1，需要通过重复以下操作到达顶点 N：

题目保证存在从顶点 1 到顶点 N 的操作序列。

请计算到达顶点 N 所需的最小总成本。

sol

典。不用任何思考的分层图板子。

F

高桥君共有 2N 颗牙齿，其中 N 颗是上牙，剩余的 N 颗是下牙。

左数第 i 颗（1 \leq i \leq N）上牙的长度为 U_i，左数第 i 颗（1 \leq i \leq N）下牙的长度为 D_i。

当高桥君的牙齿满足以下两个条件时，称为「良好咬合」：

  1. 存在一个整数 H，使得对于所有 1 \leq i \leq N，有 U_i + D_i = H。
  2. 对于所有 1 \leq i < N，有 |U_i - U_{i+1}| \leq X。

高桥君可以执行以下操作任意次：

除上述操作外，无法通过其他方式改变牙齿长度。请计算高桥君达成良好咬合所需支付的最小金额。

sol

豪题。

首先答案显然满足单调性。对于一个合法的 H，更小 H 的方案直接把所有的牙多磨一个单位即可。

问题转化为每个位置 i 可以最多使 u_i 减少 u_i + d_i - H，让相邻差不超过 X 是否可行。考虑局部到整体的贪心策略：

首先注意到最小值一定不会再减少了。最小值的邻居必须减少，且修改完最小值的邻居后无论如何继续修改都不会变的不合法（你不会把最小值的邻居减的比最小值更小）。如果减少最小值的邻居失败则返回不合法，否则把邻居扔进堆里继续贪心修改即可。

EX

实际是斯坦纳树板子，红温了。

CF 2146 div2.

可能是炸太多了不敢交了。

A

枚举出现次数 x，把不够的直接踢掉。设还剩下 t 个数，长度就是 x\cdot t

B

考虑是否有非必选集合。只要有两个就对了（已经有三种组合方案）。没有两个一定组合不出来三个。充要性很清晰。

C

前缀最小值和后缀最大值，确定了 p_i = i。0 连续段倒序排即可。假如有长为 1 的连续段就直接判无解即可。

D1

tag：构造上界，二进制黑白染色

学习一下做构造题的套路思路。

  1. 手模，猜答案。搜一下可以发现答案是 n(n+1)=2\sum\limits_{i\le n} i。
  2. 验证答案是某上界。考虑 x\space\text{or}\space y = x + y - x\space\text{and}\space y，也就是 n(n+1) 是答案的上界。取到上界需要 \forall a_i \space\text{and}\space b_i = 0
  3. 根据要求构造。令 k = \lceil \log n \rceil。则我们希望 2^k - 1 - n 与 n 配对。可以将 [2^k-1-n,n] 区间反转后与 b 数组配对，然后 n:= 2^k-2-n 递归构造。

D2

考虑上道题的做法实际上是按照某个 2^k 对称后配对。即一个最高位由1变0/由0变1的位置对称都是优的，因为黑白区间对称后刚好错开。然而此题中最高位不一定改变，于是降序考虑每一位，当且仅当 l,r 该位不同时，找到改变的位置并对称。可以发现去除掉上面相同（绝对不可能有贡献）的几位，和上题是等价的。

E

tag：MEX，弱化条件，扫描线

CF 2128 div2.

C

tag：充分到必要，前/后缀信息

不能有上升子序列或对上升子序列提要求这样的条件太强了。

想到了一个位置只能加不超过前缀最小值的东西。实际上，从这一点可以得出充分且必要的条件。记目标数组的前缀最小值为 m_i，则合法的充分条件为 b_i \le 2m_{i-1}-1。方案：先令 x = m_{i-1} - 1，再令 x = m_i

考虑为啥这是必要的。在中间任意一个状态 \{a_1\ldots a_n\}，一定有当前的前缀最小值 m_i' \le m_i。考虑此次改变 a_i 的操作 x 一定满足 a_i < x \le m_{i-1}'，故改变后 a_i + x < 2x \le 2m_{i-1}'。

D

tag：观察序列结构

## E1 tag：**二分，赋权** 考虑二分是否存在 $\ge mid$ 的中位数。考虑假如存在某个区间 $[l,r]$ 使得 $\sum\limits_{i\in [l,r]} [a_i \ge mid] \ge \dfrac {l+r}{2}$，就存在 $\ge mid$ 的中位数。考虑区间长度不好处理，但可以直接给 $< mid$ 的位置赋权 $-1$，便只需考虑是否存在总和 $\ge 0$ 的区间。 ## E2 tag：**神题** 有气节。 首先需要注意到合法的子中位数是一个区间。因为从取最值的区间进行任意的扩展，子中位数的集合的变化都是连续的（不会漏掉中间的一个数）。那么其实做法也就可以从中得出了。我们只需要找到一个从最小值区间连续地移动到最大值的方案，**就一定能取遍所有可能的子中位数**。 # CF 2143 div2. ## C tag：**构造上界** 答案的上界是 $\sum \max(x,y)$，考虑构造取到上界。实际上这是 $n - 1$ 个不等关系，形成了一个 DAG，直接拓扑排序即可。 关于一开始想的倒序分配的思路其实有简单的hack：$(1,2,1,2),(1,3,2,2)$，排列 $(3,2,1)$ 只能取到 $3$，不是上界。 ## D1/D2 tag：**下降子序列，图论建模，优化平凡转移** 容易想到，合法的序列相当于连接所有逆序对以后不出现奇环。由于在一个下降子序列里我们会连出一个完全图，而 $K_3$ 就不可避免地有奇环了，所以有一个充分条件是LDS不超过 $2$。进一步考虑我们会把一个下降子序列连成完全图，所以存在 $\ge 5$ 的奇环一定能找到 $K_3$（任意从其中选取三个点）。所以是充要的。 然后考虑如何对这个计数。开始考虑了这个序列是否有良好的结构，但实际上啥也没有。 先考虑如何检验合法。顺序扫描这个序列，记 $x_i$ 表示最大的满足左侧有某个数大于它的数。假如 $x_i > a_i$ 就不合法。**这个转化是充要的**。 考虑设 $f_{i,x,y}$ 表示考虑了前 $i$ 位，$x_i = x$，最大值是 $y$ 的方案数。转移是简单的： $$ f_{i,x,y} \leftarrow f_{i-1,x,y} \\ f_{i,x,a_i} \leftarrow f_{i-1,x,y}[y\le a_i < x] \\ f_{i,a_i,y} \leftarrow f_{i-1,x,y}[a_i \ge x] $$ 直接转移是 3D/0D，复杂度 $O(n^3)

然后是比较牛的地方，如何优化这一坨东西：

直接列出状态确实是 3D 的；但我们真的会用全吗？实际上每次改了一行一列，用到了几个矩形的和，剩下的部分是直接复制的。考虑写出每次更新的状态和它会用到的状态：

f_{i,x,a_i} \leftarrow\sum\limits_{y\le a_i} f_{i-1,x,y} \\ f_{i,a_i,y} \leftarrow\sum\limits_{x\le a_i} f_{i-1,x,y}

发现每轮更新只会用到 O(n) 个状态，且是一个前缀和的形式。考虑对每行每列维护一个BIT用来优化求和，可以做到 O(n^2\log n)。

E

tag：ad-hoc

神题。真不知道咋想出来的。

考虑一个映射：反转所有偶数位的括号。原先的操作就变成了可以交换相邻两个相异括号。也就是，用原先的操作我们可以任意重排映射后的字符串

对于映射后的字符串，我们可以把它变换成 ())))((((( 的形式，假如两种括号都有偶数个就已经赢了。然后可以证明，不是偶数个一定寄了。记最后的匹配串翻转前，奇数位的左括号有 l_1 个，偶数位的右括号有 r_0 个，则反转后左括号数量为 l_1+r_0。又因为是匹配串所以 l_1 = r_0，故 l_1+r_0 为偶数。r_1+l_0 为偶数同理。

F

考虑判断一个子段 [a_l\ldots a_r] 是否合法。考虑一个位置能取到的所有的数是前缀线性基构成的向量空间。有一个naive的判断是扫一遍，每次将当前数 a_i 插入线性基，然后找出新的线性基能表出的数中 > a_{i-1} 的最小的数作为 a_i 的取值。可以注意到对于每个 l，存在一个 r 的分界点使得后面的 r 都不合法。

考虑上述算法有什么地方产生了浪费：线性基很多时候是不变的，变化的点只有 \log V 个。

考虑对于每个 l，记录线性基变化的若干位置 [r_1,r_2\ldots r_b]。对于每个位置 r_d，考虑在新的线性基里找 a_{r_d - 1} 的后继，然后再往后找 r_{d + 1} - r_d 名。如果找不出来，说明分界点在 [r_d,r_{d+1}]。当 l\leftarrow l - 1 时，一定有新的变化点除去 l-1 以外包含于 l 的变化点（线性基变化意味着当前向量不能被 a_{l}\ldots a_{r_d - 1} 表出）。

CF 2140 div2.

出息了然后吃席了

C

tag：分析双方最优策略

发现Bob如果想通过交换奇偶位置来减小 f，Alice在下一回换回来Bob就输麻了。所以Bob一定第一轮就结束游戏。那只要求一下Alice怎么换最优就行了

D

tag：拆贡献

不能直接让 l 最小的几个匹配 r 最大的几个然后不合法了就跳过。感性理解是对于一个 l 很小 r 很大的，我们无脑用了其中一边，但用另一边其实更优。

偶数的情况，先认为全部取 r，再调整 \frac n 2 个 l_i+r_i 最小的即可。

奇数的情况，枚举最后不取的是谁，对调整方案的影响是 O(1) 的。

E1

tag：模拟决策

当局面确定时结果就确定了。考虑设状态为所有局面对应的结果。

考虑 f_{i,S} 表示加入了 i 堆石头，每堆石头是否为 2，是alice/bob在行动。可以得到某个人走某一步后能导向哪些结果。根据目前剩余的石头数 i 可以得出当前是哪个人在行动，取对这个人更优的结果即可。

E2

tag：ad-hoc

套用ez ver.的做法，考虑对于任意的 k，f_{n,S} 表示答案是否 \ge k。即答案至少为 k。考虑枚举 k，计数所有答案至少为 k 的方案数。这样答案恰好为 k 的局面恰好被统计了 k 次。反正是真想不出来。

F

tag：分讨

不知道如何想到答案只能是 \sum a_i 或 \sum a_i - 1 或 -\infty

先排序。观察样例，注意到如果有 1 < j < k 满足 a_j,a_k 奇偶性不同，就是 -\infty。想到这儿就没继续往下想了，但从出题的角度来想，这样精心配凑的条件（还有比如2134F）一定有比较优美的性质。所以这题无法提出poly做法时应当考虑直接分讨手撕。

继续考虑，如果 \forall j>1,a_j 奇偶性相同，考虑能否通过在后面操作一次使得出现奇偶性不同。注意到只要后面 n-1 个数只要能操作一次就必定会出现奇偶性不同，考虑判定能否操作一次。结论是 \exist 2<l<n-1,1<j<k,a_j\not\equiv a_k \pmod l。证明比较简单。对于 l=n，我们要求后 n-1 个数的和不是 n-1 的倍数。如果满足后面能操作一次，也可以取到 -\infty

若后 n-1 个数无法进行操作，考虑包含进 a_1。假如对于整个数组仍然无法操作一次，那答案就是 \sum a_i。如果只能找到若干 a_1-a_k \equiv 1 \pmod l，或 \sum a_i \equiv 1 \pmod n，说明只能减 a_1，而且减完就寄了。这种情况答案是 \sum a_i - 1。否则仍然可以取到 -\infty

最后考虑如何判断是否存在 a_j \not\equiv a_k \pmod l，考虑反过来判断是否 \forall l, a_1\equiv a_2 \equiv \ldots \equiv a_n。一个充分的条件是 \forall a_i = k\times lcm(2\ldots n-1) + C。证明必要性：考虑若 \exist a_j = k \times lcm(2\ldots n-1) + b，则若 \forall l,b\equiv C \pmod l，说明 b \equiv C \pmod {lcm}，矛盾。

CF 2139 div2.

C

tag：递归

对于 a:=\frac a 2,b:=b+\frac a 2 这个操作，一定满足 b > a，也就是我们可以唯一确定上一步操作是啥。逐步还原即可。

D

tag：逆序对，下降子序列

伪证了（）

手模一下 n=3 的所有排列，发现只有321的情况能用一次操作减少超过1个逆序对。也就是说，若在交换过程中遇到了相邻三个递减的情况，就可以通过交换间隔两项减少操作数。即，[l,r] 区间存在长度为3的下降子序列。

单调栈维护一个数 p_i 左边第一个大于它的和右边第一个小于它的，得到区间 [l_i,r_i]，若包含任意一个这样的区间就是 NO。离线询问，计数区间包含即可。

E1

tag：背包

首先容易发现答案上界是最小的叶子节点深度，记为 d。若我们能把 1\ldots d 这几层填成一样的，然后把剩下的 1 扔到剩余的地方（深度大于 d 的节点）我们就取到了上界。否则我们必定要放弃一层，取到 d-1。背包计算一下能否把上面几层填成一样的即可。

CF 2134 div2.

C

tag：简化判据，贪心

先给结尾补一个 0 补成奇数。充要条件就是 \forall a_{2i-1}+a_{2i+1}\le a_{2i}

也就是现在有 \frac{n-1}{2} 对数，使一个位置减一可以影响两对数（除了边界）。求使所有数对的和低于其限制的最小操作次数。贪心地考虑，假如一个数对不满足条件，我们优先选那个可以同时影响两对未合法的数的位置-1。容易发现，一对数最多有 a_{2i-1}+a_{2i+1}-a_{2i} 的负贡献，。

D

tag：树的直径，始末态

链相关，考虑直径。最后这条链的直径为 n。设最初的直径为 d，假如过程中直径严格单增，需要 n-d 步，这是答案的下界。按同样的思路构造即可取到下界：假如有一条从 p 伸出直径的边，考虑把直径从 p 开始的另一端接到这条边的对面，即可使直径增加 1。所以我们只需要找一条伸出直径的边即可。

E

写了下官解思路。感觉交互题还完全没有开窍（）

一个位置 i 通过一次throw问不出来当且仅当弹到 i+1 和 i+2 后能继续往后弹的次数 d_{i+1} = d_{i+2}。考虑延后处理这些位置。

故考虑把未知位置换到相邻的一个位置就可以直接问出来了。为了没有后效性我们可以顺序考虑未知位置，并把它换到 $i + 1$。最后将 $n$ 换到 $n-1$ 并特判即可。 ## F tag：**染色组合意义** 只有 $0,2$ 与 $1,3$ 的相邻对贡献是 $2$，其他的相异相邻对贡献为 $1$，相同相邻对贡献为 $0$。 将 $0,2$ 染蓝色，$1,3$ 染红色，则可以拆成红蓝交替的贡献（为1）和红色段与蓝色段内部的贡献。 先单独考虑红色段。考虑设 $t_j$ 表示有 $j$ 个 $0,2$ 间的空隙的方案数。考虑枚举 $0,2$ 各自的连续段个数 $lx,ly$，则有 $t_{tx+ty-1} \leftarrow \binom {cx - 1}{lx - 1} \binom{cy - 1}{ly-1}(1+[lx=ly])

然后考虑把 0,2 切断的方案。枚举 i 和在 j 个间隙里切断的个数 p，则有 f_{i,j-p} \leftarrow t_j \binom j p \binom{cx+cy-j-1}{i-1-p}

同理可以算出 g 表示 1,3 的方案数。关于对答案的贡献就是把 f,g 卷起来。具体就是 f_{ix,jx}\times g_{iy,jy} [|ix-iy|\le 1] \rightarrow ans_{ix+jy-1+2(jx+jy)}

CF 2151 div2.

还挺牛的，虽然猜的结论（）

C

tag：图形建模，贪心

手模一下，发现肯定是先走到 k 然后在 k 和 k-1 间走折线振荡是最优的。收益可以简单前缀和维护，主要是想清楚。

D

E

tag：DP优化

对于选取方式的声称，即贪心的思路其实应该很容易被hack的。实际上限制复杂一些的最优化问题贪心是不是基本上都不太可能对。

考虑DP，可以先不纠结于列出维数较低的状态。注意到有些时候高维的DP也是可以优化的。考虑假如 alice 想买 a_i，不想买 a_j(j<i)，那 a_j 显然给 bob 买。但如果 posb_{a_i} < posb_{a_j}，就说明你想让 bob 承担 a_j 就必须让 bob 买下 a_i，那这是不合法的。所以，alice 能不能买某个物品取决于先前的策略中 bob 买到了哪里

考虑设 f_{i,j} 表示考虑了前 i 个物品，bob 买掉了他的前 j 个物品的最大收益。考虑转移：

\\ f_{i,j} \leftarrow (v_{a_i} + f_{i-1,j})[j<posb_{a_i}]

再看一下发现我们只有以下几种转移：

f_{i,posb_{a_i}} \leftarrow \max\limits_{j < posb_{a_i}} f_{i - 1, j} \\ f_{i,j} \leftarrow f_{i-1,j} + v_{a_i} \quad (j < posb_{a_i}) \\ f_{i,j} \leftarrow f_{i-1,j} \quad (j \ge posb_{a_i})

涉及到区间最值，区间加，可以直接SGT维护。

F

tag：计数转期望

当读不懂题解时请检查是不是读错题了。

我们要对终局计数，尝试考虑哪些终局情况是合理的。选择中间的位置会把三个东西合并到一起，选择边界上会合并两个。所以合法的终局是所有人在一个区间里，且除了端点人数都必须是奇数。

考虑设区间长为 len，边缘两个人分别取的 x,y，中间的每个人取的 2f_i+1。由于中间所有人地位等价，所以 f_i 的期望等于 \dfrac{n-x-y-len+2}{2(len - 2)}。发现这个式子实际上基本只和 len 有关（除去边界情况）。而将 n 个人分配到 len 个位置总方案数可以插板计算。

计算时，考虑破除边界的特殊性，把边界取偶数看作奇数+1，就只需要枚举四种情况即可。

CF 2107 div2.

D *2100

tag：字典序，长链剖分

好似喵。请记住div2.D不会为难你的。出现新的连通块直接爆搜。考虑每次直径必定下降，故所有的连通块总共只有 O(\sqrt n) 个。复杂度可以承受。

E *2600

假设要计算 \sum\limits_{S} f(S)，可以计数 \sum\limits_{x}\sum\limits_{S} [f(S) \ge x]

想到了用更优的方法表示式子，但没有想到正确的形式。答案为 \sum\limits_{i\neq 1} \binom {siz_i}{2}。每个点对都被算了 dep_{lca} 次，正确性显然。我们可以构造一个由 n 开始的严格下降序列，使得每一项是使得 \binom {a_i}{2} \le k 的最大值。尝试说明这样一定能构造出 k - \sum \binom {a_i}{2} = 0/1。

考虑归纳证明：

补充定义 \binom 1 2 = 1。假如 1\ldots n 可以构造 S_i = \sum\limits_{1\le i \le n} \binom i 2 的所有数，我们希望 \binom {n + 1} 2 \le S_n + 1。移项可得 \binom {n + 1} 2 - \binom n 2 \le S_{n - 1} + 1 即 n \le S_{n - 1} + 1，得证。

F 2300/2800

tag：1D/1D 最优化DP，李超树

F1还是应该想到的。考虑 1D/1D，策略是每一段搬一个值过来一直超。假如 (j,i] 搬 a_k 过来，代价是 a_k(i-j)+i-j-1+i-k，那么发现我们让 a_k 减少 1，不论 i-k 怎么变化都是更优的。所以直接取 (j,i] 区间最小值即可。写出转移式子：

f_i = \min\limits_{j <k\le i} f_j + a_k(i-j) + i - j - 1 + i-k

接下来考虑如何优化。有两种方法：

sol1.

这个形式启发我们往斜优/李超树上想。但是有一个区间最小值 a_k 就没法处理了。这时候可以考虑一个（可能比较经典的）trick：只进行在两端的转移，拼出中间的。即我们只考虑 i,j 分别作为 k 的转移：

f_i = \min\limits_{j < i} f_j + a_i(i - j) + i - j - 1 f_i = \min\limits_{j < i} f_j + a_j(i - j) + 2(i - j)

注意，第二个转移要求我们把 a_j 还回去。即我们不会存在两个第二种转移接在一起的情况。假如有 u<v<i，且 u\rightarrow v,v\rightarrow i 都执行的是第二种转移，那一定满足 a_u<a_v-1,a_v<a_i-1（往返带来的额外代价是2），这种情况我们直接转移 u\rightarrow i 就是更优的。这个形式可以直接李超树维护。注意由于添加的是直线，李超树只用 O(n) 的空间。

sol2.

发现把前面的东西拿过来超这种情况只会发生一次。证明同上。故直接记 f_i 表示只用上文第一种转移的最小代价，显然在单调栈顶位置转移是最优的。然后把 (a_i + 2)x + f_i - a_i\cdot i - 2i 这条直线直接丢李超树里，就可以做到查询从前面的某个位置执行第二种转移的最小代价。

CF 2147 div2.

D

策略是两个人都取当前众数。假设当前众数出现 x 次，如果某人想取 y，就算改变了先后手多获得一个 y，损失了一个 x 也是不优的。

E

tag：局部最优解，决策包容性

想到了使连续的低位是 1，但没想到最后的贪心策略。

考虑使某个位 d 变成 1 的局部最优解，是选一个 a_i \bmod 2^d 最大的位置把他加到 2^d 位是 1。然后问题转化为把低位新产生的 0 变回 1。使用决策包容性证明：假如我们选了 a_j \bmod 2^d < a_i \bmod 2^d，那我们直接用 a_i 加到 2^d 位为1，然后再把 a_j 加到原来的 a_i，肯定满足 d 位及以下是1并且代价不大于直接用 a_j 加。

F

tag：tarjan，线段树

发现原来的图是一条链加上若干返祖边，形成若干SCC。设每个SCC大小为 a_i，则答案为 n + \binom n 2 + \sum \binom {a_i} 2。考虑如何刻画这个 SCC。考虑每个点最多贡献一条返祖边 i \rightarrow u ，而这条返祖边会把 [i,u] 中所有点纳入SCC，也就是被返祖边覆盖一次的点都会被纳入SCC。考虑对于每条返祖边令 [i,u) 区间+1，那所有值为 0 的点就是SCC的分界点。设为 b_1,b_2\ldots b_k，我们要求 \sum \binom {b_i - b_{i - 1}} 2。线段树节点上存储这个区间最左边的分界点和最右边的分界点就可以push up了。

CF 2103 div2.

D *2000

tag：拓扑排序

题面居然提醒了我们 a_i \le \lceil \log n \rceil，善。考虑一个位置没有被删确定了和相邻位置的大小关系。再给一个同时被删的连续段钦定一个顺序。然后按拓扑序构造即可。

E *2600

tag：排序

首先如何判无解：若未排序并且任意两个位置加起来都不等于 k，就似了。

考虑存在两个位置加和等于 k 时，是否可以借助这两个位置通过不超过 3 次操作交换别的位置。进行一些手模，发现可以做到。具体方式如下：(u,x,k-x,v)\rightarrow(u,u,k-u,v)\rightarrow(v,u,k-v,v)\rightarrow(v,u,k-u,u)

最后发现初始找到的两个位置好像不能被更改，咋办？考虑把这两个位置移动到头尾，最后改成 0,k。随便玩一玩发现也可以做到。

F *2600

tag：拆位

做出来了但是写不出来了（）

考虑如何计算一个区间的 nor。按位考虑，容易发现最后一个 1 以后才对答案有影响。设这个位置为 x，则贡献可以快速计算：

考虑分别计算所有 r=i 对所有位置造成的贡献。进一步讨论发现对于每一位 l<x，l=x，l=x+1，l\ge x+2 可能贡献不同的取值。总共有 O(k) 个断点，考虑都拿出来分别考虑 nor 值是多少，然后对这个区间 check max。

妄图精细实现做到单log但是没有必要。可以直接枚举所有可能的变化点，直接计算这个区间的 nor 是多少，复杂度双log。是出题人的解法。避免了一切赤石分讨

CF 2152 div 1+2.

D

$\text{observation 2.}$ 若不是 $2^k$ 则一定可以进位。删到最低位是1的时候加一即可。 $\text{observation 3.}$ 如果是 $2^k + 1$ 处在没救的边缘（先手操作一步就没救了） 故需要考虑保护一些 $2^k + 1$。发现后手只能保护一半。于是只需要计数区间中有多少 $2^k$ 和 $2^k + 1$ 就可以算出后手对回合数的影响了。 ## E interactive 听说《E一串字母-S一串字母》定理很重要在此证一下。 假设最长反链长度 $< m + 1$，则链覆盖数 $\le m$。根据抽屉原理一定存在一条链长度 $> n$。 这其实可以启发做法：一次询问会给出**包含目前最靠左元素的一条链**。问 $n$ 次，每次把询问结果从下次询问集合中删掉。如果我们问出 $>n$ 的链就直接赢了。否则说明最小链覆盖 $> n$，那么一定能找到一条 $>n$ 的反链。直接倒着找第一个在当前元素左边的元素即可。 ## F tag：**调整法证贪心（P4954），倍增，图论建模** $\text{observation 1.}$（实际上并没有observe出来）充要条件是 $y_i + t < y_{i + 2} 考虑最后选出来的序列的奇数项和偶数项是**相对独立**的。比较理想的情况下我们可以直接分别从 $x_l$ 和 $x_{l+1}$ 开始选两个间隔大于 $t$ 的子序列拼在一起。但问题是，每次跳 ```upper_bound(x[i] + t)``` 可能会跳到同一个点。此时我们需要**强迫偶数项往后选一位**。 $\text{observation 3.}$ ```i -> upper_bound(x[i] + t)``` 形成了一棵树。从两个位置分别开始跳，第一次产生冲突的点是 LCA。 于是对于这种**没有修改的跳转操作**，考虑倍增维护（P1081）。维护一个倍增表 $f_{i,k}$ 表示从 $i,i+1$ 分别跳直到跳到 LCA 经过了多少个点。用一串 $f$ 拼上最后一串分别跳即可。 # CF 2119 div2. ## C 我服了。应当先判最后两位填不填的出来再判 $k \le n - 2$。 ## D ### 赛时思路 场切计数了呜啊啊 发现问题的关键在于**可以放弃一些标记不拿**。结合数据范围想到二维状态 $f_{i,j}$ 表示前 $i$ 个标签**待匹配**的有 $j$ 个的方案数。注意到每个待匹配标签 $x$ 被拿走，左端点有 $x$ 种选法，考虑贡献提前计算。得到以下转移： $$f_{i,j}\leftarrow f_{i-1,j} \\ f_{i,j}\leftarrow f_{i-1,j}\times i \\ f_{i,j}\leftarrow f_{i-1,j-1}\times i \\ f_{i-1,j}\leftarrow f_{i-1,j}\times j\times i \\ f_{i-1,j}\leftarrow f_{i-1,j+1}\times (j+1) $$ 分别表示放弃 $i$，直接选择 $i$，让 $i$ 待配，选择一个前面的并让 $i$ 待配，选择一个前面的并放弃 $i$。注意选择前面的标记时要乘 $j$，因为虽然选择某个标记时的左端点的贡献已经算上了，但是并没有计算选择哪个标记的贡献（赛时差点没调出来） 更优雅一点的形式是分别考虑该点标记和该点区间的贡献。设 $g_{i,j}$ 为考虑了标记的方案数，$f_{i,j}$ 为考虑了标记和区间的方案数。则有转移： $$ g_{i,j} \leftarrow f_{i-1,j} \\ g_{i,j} \leftarrow f_{i-1,j-1}\times i \\ f_{i,j} \leftarrow g_{i,j} \\ f_{i,j} \leftarrow g_{i,j+1}\times(j+1) $$ 分别表示放弃当前标签，待配当前标签，放弃当前区间，当前区间选择一个待配标签。 ## E tag：**进位性质，缩状态数** $\text{observation 1.}$ $b_i$ 是 $a_{i-1} | a_i$ 的超集。 即我们至少先要把 $b_i$ 提升到最小的满足是 $a_{i-1}|a_i$ 超集的数。然后对于不在 $a_i$ 中的位，我们需要令 $b_i$ 或 $b_{i+1}$ 中至少一个在该位为 0。 对前缀子问题提要求的形式启发我们使用DP求解。有 naive 的做法：设 $f_{i,j}$ 表示 $i$ 填成 $j$ 前缀的最小花费。但是 $j$ 取值范围过大无法转移。 $\text{observation 2.}$（没想出来的）实际上每个 $b_i$ 取值的方案数很少。最优的取值一定是将低位不在 $a_{i-1}|a_i$ 中的若干个1变成0，并将高位某个0变成1。 于是设 $j$ 为这个变成1的高位，就可以开始DP了。 # CF 2136 div2. ## D *1700 红温了。鉴定为想完E以后思想枯竭了。 当位于横纵坐标都充分远的点时，绝对值可以直接打开。于是直接移到 $(X-\inf,Y+\inf)$ 和 $(X+\inf,Y+\inf)$，总共需要八次移动。绝对值打开以后只剩一个 $\min(\pm x_i - y_i)\mp X + Y$，于是可以得到 $Y\pm X$，进而解出 $X,Y

E *2000

鉴定为得出结论以后丝毫没有验证样例。

$\text{proof 1:}

充分性：假设环上有两个点 u,v，由于顺时针逆时针的点权异或和相等，故去除 u,v 后，环上的点权异或和应当是 0。验证一下发现是上面的方案是合理的。

必要性：一定可以选出一组 a_u = a_v，一组 a_u \neq a_v。此时 a_u \oplus a_v 不相同，必定不满足去除后剩余部分的异或和是 0。奇环的情况，若不取 0，因为去除 u,v 后有奇数个点所以异或和必定不为 0，矛盾。

会出问题的情况是两条返祖边拼出一个奇环。可以手玩一下两条返祖边相交或包含的情况，可以发现两个偶环是无法拼出奇环的。 于是做法就是考虑所有的返祖边 $(u,v)$，将 $u\rightarrow v$ 的路径上所有点缩起来。合并的时候检查两个集合的颜色是否冲突即可。对于一个奇环可以直接新建一个权值为 $0$ 的虚点加进去即可。 # CF 2133 div2. ## E *2500 ### 电波构造 $\text{observation 1.}$ 丙烷是没有同分异构体的。 人话：树上选3个点一定构成一条链。 于是猜想能否让四个相邻的点最多使用一次操作。直接考虑自底向上，若当前连通块大小 $\ge 4$ 就直接把当前点拆掉，否则向上合并。然后惊奇地发现这玩意儿对了。 ### 没对上电波……咋办 场上想的长剖。 ## F *3000(?) 感觉没有*3000啊。 以下先令 $e_i:=e_i-1$ 看着好看点 玩一玩，首先发现若中点最靠右的区间并不能更新右端点，那肯定是不优的。同时我们需要记录**中点最靠右的的区间是谁**，以决定当前区间是先选还是后选。可以先给出状态和暴力转移： 设 $f_i$ 表示中点最靠右的区间是 $[i-e_i,i+e_i]$，且 $[1,i+e_i]$ 全都被选上的最小代价。 当前区间后选：$f_i \leftarrow (f_j + 1)[i - e_i - 1 \le j+e_j < i]

当前区间先选：f_i \leftarrow (f_j + 1)[j<i-e_i\land j + e_j \ge i - e_i - 1]

对于第二种转移我们可以用类似扫描线的思想解决：在迭代到 i-e_i 时询问 [i-e_i-1,i+e_i-1] 即可。