首先，一个经典的结论是：对于树上任意一点，离它最远的点一定是直径的两个端点之一。对于直径外一点 \(x\)，设离 \(x\) 最近的直径上的点是点 \(y\)，当 \(x\) 向 \(y\) 靠近时，离 \(x\) 最远的点仍然是直径的两个端点，但最远距离减小，故取 \(y\) 优于 \(x\)。于是，我们选的第一个点肯定是在直径上。
设我们选的第一个点是 \(A\)，接下来证明 \(A\) 沿着直径扩展最佳。如下图，\(L,R\) 是直径的两个端点，\(E,G\) 分别是 \(D,F\) 向下延伸出去最远的点。若从 \(A\) 出发沿直径选了 \(B\)，答案是 \(\max(d_{LA},d_{AE},d_{BG},d_{BR})\)；若沿子树方向选了 \(D\)，答案是 \(\max(d_{LA},d_{DE},d_{AR},d_{AG})\)。依据直径的性质有 \(d_{BG} < d_{BR}\)，\(d_{AG}<d_{AR}\)，\(d_{AE} < d_{LA}\)，\(d_{DE} < d_{LA}\)，此时相当于比较 \(\max(d_{LA},d_{BR})\) 与 \(\max(d_{LA},d_{AR})\)，又 \(d_{AR} > d_{BR}\)，故选 \(B\) 相比选 \(D\) 更优。将 \(A,B\) 看成一个整体，同理可证明选 \(C\) 比选 \(F\) 要更优，以此类推......因此路径肯定是沿着直径方向一直扩展。

当 \(k\) 大于等于直径长度时，就选完整个直径。否则在直径上搞一个长为 \(k\) 的滑动窗口，窗口两侧延伸出去的最长距离可以预处理前缀后缀和计算，窗口内部子树的答案等同于区间最值。

时间复杂度 \(O(n\log n)\)，若用单调队列求极值就是 \(O(n)\)。

CF1969E. Unique Array

*2400 Code

对于一个数 \(a_i\)，设 \(a_i\) 上一个出现的位置是 \(\text{lst}_{a_i}\)，下一个出现的位置是 \(\text{nxt}_{a_i}\)，那么 \(a_i\) 在区间 \([l,r]\) 中唯一的充要条件是 \(l\in(\text{lst}_{a_i},i]\) 且 \(r\in [i,\text{nxt}_{a_i})\)。

考虑从左到右枚举线段的右端点 \(r\)，判断是否有不合法的左端点。

令 \(\text{llst}_{a_i}\) 是 \(a_i\) 的上一个的上一个的出现位置。当右端点移动到 \(i\) 时，\((\text{llst}_{a_i},\text{lst}_{a_i}]\) 这一段不能再作为合法的左端点了，我们将这个区间 \(-1\)。而 \(l\in (\text{lst}_{a_i},i]\) 是新增的合法左端点，我们将这个区间 \(+1\)。

如此一来，对于当前右端点 \(i\)，以 \(l\in[1,i]\) 为左端点的区间全部 unique 就等价于区间 \([1,i]\) 的最小值 \(>0\)。若不满足条件，我们就把 \(a_i\) 替换掉，并且贪心的想肯定是替换成一个序列里从没出现过的数。替换后，左端点就能存在于 \([1,i]\) 中的任何位置，于是我们将区间 \([1,i]+1\)，同时把答案 \(+1\)。

整个过程仅涉及区间加、区间极值，使用线段树维护。时间复杂度 \(O(n\log n)\)。

注意到随着 \(i\) 增加，\(\min(b_1,\ldots,b_i)\) 递减，\(\max(b_{i+1},\ldots,b_m)\) 也递减。这两项加起来要是定值，说明对于任意 epic 的序列，满足相加等于 \(k\) 的 \(\min(b_1,\ldots,b_i)\) 唯一，\(\max(b_{i+1},\ldots,b_m)\) 也唯一。我们把前缀 \(\min\) 这一项的值记为 \(x\)，后缀 \(\max\) 这一项自然是 \(k-x\)。对于满足该要求的序列，称之为 \(x\)-epic 序列，并将 \(\min(b_1,\ldots,b_i)=x\) 的 \(i\) 称为分割点。不难发现分割点一定构成一段连续的区间。

记 \(lmn_i\) 为 \(i\) 左侧第一个 \(\le a_i\) 的位置，\(lmx_i\) 为 \(i\) 左侧第一个 \(>a_i\) 的位置，\(rmx_i\) 为 \(i\) 右侧第一个 \(\ge a_i\) 的位置，\(rmn_i\) 为右侧第一个 \(< a_i\) 的位置。

依据第一段的分析，我们枚举 \(x\)，对每个 \(x\) 统计有多少 \(x\)-epic 的子数组。对于当前 \(a_i=x\)，若要 \(a_i\) 成为前缀最小值（为了计数不重复，这里指第一个前缀最小值），左端点可以是 \((lmn_i+1,i]\) 中的任意一个。再枚举满足 \(j >i\) 且 \(a_j=k-x\) 的 \(j\)，若要 \(a_j\) 成为后缀最大值（同理这里指最后一个后缀最大值），右端点可以是 \([j,rmx_i)\)。

不难发现，\(a_i,a_j\) 要分别作为最小前缀和最大后缀贡献答案，当且仅当区间 \((lmn_i,rmn_i)\) 和 \((lmx_j,rmx_j)\) 相交，此时 \([lmx_j,rmn_i]\) 内的任意一点均为分割点。若满足此条件，包含 \([i,j]\) 的任一子数组均 \(a_i\)-epic，贡献是 \((rmx_j-j)\times(i-lmn_i)\)。

可以使用树状数组或线段树快速统计贡献。时间复杂度 \(O(n\log n)\)。

CF2072G. I've Been Flipping Numbers for 300 Years and Calculated the Sum

*2200 Code

阈值分治。

当 \(p \le \sqrt{n}\) 时，暴力计算 \(\text{rev}(n,p)\)。时间复杂度 \(O(\sqrt{n})\)。
当 \(p>n\) 时，\(\text{rev}(n,p)=n\)。时间复杂度 \(O(1)\)。

只用考虑 \(\sqrt{n}<p\le n\) 时如何快速计算。

注意到 \(n\) 在 \(p\) 进制下最多只有两位，翻转后式子写出来是： \[ \begin{align} &\quad\ (n\bmod p)\cdot p+\left\lfloor\frac{n}{p}\right\rfloor\\ &=(n-\left\lfloor\frac{n}{p}\right\rfloor \cdot p)\cdot p+\left\lfloor\frac{n}{p}\right\rfloor\\ &=-\left\lfloor\frac{n}{p}\right\rfloor\cdot p^2+np+\left\lfloor\frac{n}{p}\right\rfloor \end{align} \] 数论分块枚举 \(\left\lfloor\dfrac{n}{p}\right\rfloor\) 的值，一段区间内 \(p^2\) 的和以及 \(p\) 的和可以用公式快速计算。

时间复杂度 \(O(t\sqrt{n})\)，\(t\) 是数据组数。

CF1839D. Ball Sorting

*2100 Code

考虑这么一种操作策略：选择原序列的任意一个上升子序列，称这个子序列里的元素为选定点。我们钦定选定点都不动，那么所需要 \(0\) 的最小个数就是极长非选定点连续段的个数。

容易发现枚举所有的上升子序列可以涵盖所有可能的最优策略。

另一个观察是对于非选定点，可以只通过 \(1\) 次移动就能移动到正确的位置上。

令 \(dp[i][j]\) 表示若 \(i\) 是一个选定点，\([1,i]\) 中有至多 \(j\) 个极长非选定点连续段，将 \([1,i]\) 排好序的最小代价。

枚举上升子序列的上一个元素（即上一个选定点），做出以下转移： \[ dp[i][j]=\min \begin{cases} dp[i][j - 1]\\ dp[i-1][j] &,\text{if }c[i-1]<c[i]\\ dp[k][j-1]+(i-k-1)&,\forall k\in[0,i-1),c[k]<c[i] \end{cases} \]

初态：\(dp[i][0]=\begin{cases}0&,\text{if }\{c\}\textbf{ 在 }[1,i] \textbf{ 单调增}\\ \text{inf}&,\text{otherwise}\end{cases}\)
答案：\(\min\begin{cases}dp[n][k]\\ dp[i][k-1]+(n-i)&,\forall i\in[1,n)\end{cases}\)

时间复杂度 \(O(n^3)\)。

CF1839E. Decreasing Game

*2400 Code

结论：后手必胜当且仅当 \(\{a\}\) 能被划分为元素和相等的两部分。

充分性：设划分成的两部分为 \(A,B\)，后手必胜的策略如下。若先手选择了 \(A\) 中的元素，后手就选择 \(B\) 中的元素；否则后手选择 \(A\) 中的元素。如此操作后 \(A,B\) 两部分的元素和都减少了 \(d\)，因此任何时刻 \(A,B\) 两部分元素和相等。于是若先手还能继续游戏（即选择了一个 \(a_i>0\) 的 \(i\)），后手也一定能从另一部分里找到一个 \(j\neq i\) 使得 \(a_j>0\)。
必要性：若初始 \(\{a\}\) 不能划分为元素和相等的两部分，则能够证明后续每一轮操作后 \(\{a\}\) 仍旧不能划分为元素和相等的两部分。
- 设某一轮中两人选择了 \(a_i,a_j\)，不妨令 \(a_i\le a_j\)。假设操作前 \(\{a\}\) 不能被划分为了总和相等的两部分而操作结束后可以，令操作结束后 \(a_j-a_i\) 所在的那部分其它数的和为 \(s_1\)，另一部分总和为 \(s_2\)，则 \(s_1+(a_j-a_i)=s_2\)。移项得 \(s_1+a_j=s_2+a_i\)，矛盾。
于是，先手无论怎么抉择最后的局面都一定是只剩一个非零数或两个不同的非零数，必胜。

最后的问题是如何找出这个划分，这等价于找一个和为 \(\dfrac{\sum a_i}{2}\) 的子序列，是一个经典的背包问题。

时间复杂度 \(O(n^3)\)。

abc394g. Dense Buildings

Code

对于一组询问 \((x_1,y_1,z_1,x_2,y_2,z_2)\)，如果我们找到一条路径连通 \((x_1,y_1)\) 与 \((x_2,y_2)\) 且路径上最低的楼房高 \(h\)。那么：

若 \(h< \min(z_1,z_2)\)，则垂直方向上我们要 \(z_1\to h\) 再 \(h\to z_2\)，写成式子是 \(z_1+z_2-2h\)。
若 \(h \ge \min(z_1,z_2)\)，答案是 \(|z_1-z_2|\)。

为了让答案最小，我们肯定是找最大的 \(h\)。

对于相邻的楼房，连边，边权是较低的楼房的高度。

问题转化为有若干组询问，每次询问两个点，需要找出两点间的一条简单路径，让路径上所有边的边权最小值最大（最大瓶颈路）。

这是个经典的问题（NOIP 货车运输），做法是 kruskal 重构树或者在最大生成树上倍增。

CF1982D. Beauty of the mountains

*1700 Code

把有雪的格子称为 \(0\) 格子，没雪的格子称为 \(1\) 格子。

先计算出初始 \(1\) 格子的高度和与 \(0\) 格子的高度和的差值，记作 \(s\)。

对于每一个 \(k\times k\) 的矩形，我们可以用二维前缀和快速计算出对这个矩形整体 \(+1\) 对 "\(1\) 格子的高度和与 \(0\) 格子的高度和的差值" 的贡献，把这个贡献记作 \(c_i\)。

问题转化为给定序列 \(\{c\}\)，求以下不定方程是否有解。 \[ c_1x_1+c_2x_2+\ldots+c_mx_m=s \] 根据裴蜀定理，有解当且仅当 \(\gcd(c_1,c_2,\ldots,c_m)\mid s\)。

时间复杂度 \(O(nm\log k)\)。

CF1848C. Vika and Price Tags

*1800 Code

\(\tiny{不是哥们，我怎么又卡 \text{ div2C }了，呜哇呜哇呜}\)

考虑单独一组 \((a_i,b_i)\)，设终态是 \((0,x)\)，那么有循环： \[ (0,x)\to (x,x)\to (x,0)\to(0,x) \] 因此设当前 \((a_i,b_i)\) 最少需要 \(d_i\) 次操作达成 \(a_i=0\)，那么 Yes 当且仅当 \(\forall i,j\in [1,n]\)，\(d_i\equiv d_j\pmod {3}\)。

接下来的任务是对每一组 \((a,b)\) 求出相应的 \(d\)。

考虑辗转相除的过程，当 \(a<b\) 时，令 \(b=ka+p\)， \(p\in[0,a)\)，状态变化如下：

\[ (a,ka+p)\to(ka+p, (k-1)a+p)\to((k-1)a+p,a)\to(a,(k-2)a+p) \]

发现在三轮操作后，\(k\) 减少了 \(2\)。又因为我们只关心 \(d\bmod 3\) 后的结果，于是 \((a,ka+p)\) 和 \((a,(k-2)a+p)\) 是等价的。进一步，奇偶性相同的 \(k\) 都可以看作等价。我们仅取 \(k=0/1\) 讨论即可。

\(k=1\) 时，有 \((a,a+p)\to(a+p,p)\to(p,a)\)。
\(k=0\) 时，就是 \((a,p)\)。

故以下递归成立： \[ d(a,ka+p)\to \begin{cases}2+d(p,a)&,k \textbf{ 为奇数}\\ d(a,p) &, k\textbf{ 为偶数}\end{cases} \] 当 \(a\ge b\) 时，同理取 \(a=kb+p\)，\(p\in[0,b)\)，则：

\[ (kb+p,b)\to (b, (k-1)b+p)\to ((k-1)b+p, (k-2)b+p)\to ((k-2)b+p,b) \]

\(k=1\) 时，有 \((b+p,b)\to(b,p)\)。
\(k=0\) 时，就是 \((p,b)\)。

故以下递归成立： \[ d(kb+p,b)\to \begin{cases}1+d(b,p)&,k \textbf{ 为奇数}\\ d(p,b) &, k\textbf{ 为偶数}\end{cases} \] 边界情况：\(d(0,*)=0\)，\(d(*,0)=1\)。

递归层数同辗转相除。时间复杂度 \(O(n\log w)\)，\(w\) 为值域。

CF1848D. Vika and Bonuses

*2200 Code

按 \(t=s\bmod 10\) 分类讨论。

若 \(t=0\)，操作二没有作用，答案是 \(sk\)。
若 \(t=5\)，最多进行一次操作二，答案是 \(\max(sk,(s+5)(k-1))\)。
若 \(t=2,4,6,8\)，注意到末尾有循环 \(2\to4\to 8\to6\to2\)。每一轮循环 \(s\) 增加 \(20\)，枚举循环完整进行的次数 \(x\)，贡献为 \((s+20x)(k-4x)\)，这是一个二次函数，可以 \(O(1)\) 求最大值。于是我们枚举最终 \(s\) 末尾是 \(2,4,6,8\) 的情况，对每种情况分别求答案再取 \(\max\)。
若 \(t=1,3,7,9\)，执行一次操作后就和上一种情况等同了。

时间复杂度 \(O(1)\)。

CF1848F. Vika and Wiki

*2400 Code

令 \(f_{i,j}\) 表示进行 \(i\) 次操作后 \(a_j\) 的值。

\[ \begin{align} &f_0=\{a\} \\ &f_{1,i}=f_{0,i}\oplus f_{0,i+1}\\ &f_{2,i}=f_{1,i}\oplus f_{1,i+1}=(f_{0,i}\oplus f_{0,i+1})\oplus(f_{0,i+1}\oplus f_{0,i+2})=f_{0,i}\oplus f_{0,i+2}\\ &f_{3,i}=f_{2,i}\oplus f_{2,i+1}=(f_{0,i}\oplus f_{0,i+2})\oplus (f_{0,i+1}\oplus f_{0,i+3})\\ &f_{4,i}=f_{3,i}\oplus f_{3,i+1}=(f_{0,i}\oplus f_{0,i+1}\oplus f_{0,i+2}\oplus f_{0,i+3})\oplus (f_{0,i+1}\oplus f_{0,i+2}\oplus f_{0,i+3}\oplus f_{0,i+4})=f_{0,i}\oplus f_{0,i+4}\\ \end{align} \]

非常 amazing 啊经过大力找规律，得到的结论是进行 \(2^k,k\in N^+\) 次操作后，\(f_{2^k,i}=f_{0,i}\oplus f_{0,(i+2^k)\bmod n}\)。

题目又保证 \(n\) 是 \(2\) 的幂，故 \(n\) 次操作后 \(\{a\}\) 一定全 \(0\)，没有无解的情况。

接着，又观察到若 \(\{a\}\) 已经全 \(0\)，再操作肯定也是全 \(0\)，换句话说答案可以二分。

设二分出的答案是 \(x\)，预处理对于 \(k\in[0,\log n]\)，操作 \(2^k\) 次后的数组，枚举 \(x\) 的每一位大力操作即可。

更聪明的做法是倍增，令 \(i=\frac{n}{2},\frac{n}{4},\frac{n}{8},\ldots\) ，对每个 \(i\) 先令 \(\{b\}=\{a\}\)，在 \(\{b\}\) 上操作 \(i\) 次，若操作后 \(\{b\}\) 不全为 \(0\)，说明答案比 \(i\) 大，此时将答案累加上 \(i\) 并把 \(\{b\}\) 赋值给 \(\{a\}\)。

时间复杂度前者 \(O(n\log^2 n)\)，后者 \(O(n\log n)\)。

CF2070E. Game with Binary String

*2200 Code

后手为了让 \(0\) 尽可能少，一定是拿取相邻的一个 \(1\) 和一个 \(0\)。又因为序列是循环的，故若序列中存在至少一个 \(1\) 和一个 \(0\)，就肯定有相邻的 \(10\) 或者 \(01\)。

我们将这个游戏做一个转化：先手不必拿取相邻的两个 \(0\)，而是序列中的任意两个 \(0\)；同时后手也不必拿取相邻的 \(1\) 和 \(0\)，而是序列中的任何一个 \(1\) 以及任何一个 \(0\)（若没有 \(0\) 就是任意两个 \(1\)）。

此时，在一个完整回合中，总计三个 \(0\) 和一个 \(1\) 被取走，我们不难想到按序列长度\(\bmod 4\) 进行分类。记我们研究的序列长为 \(m\)，用 \(c_{0/1}\) 代表序列中 \(0/1\) 的数量，手玩后得到如下结论。

若 \(m\bmod 4=0\)，先手赢得游戏当且仅当 \(c_0\ge 3c_1+1\)。
若 \(m\bmod 4=1\)，先手赢得游戏当且仅当 \(c_0\ge 3c_1+2\)。
若 \(m\bmod 4=2\)，先手赢得游戏当且仅当 \(c_0\ge 3c_1+2\)。
若 \(m\bmod 4=3\)，先手赢得游戏当且仅当 \(c_0\ge 3c_1-1\)。

其中 \(c_0\ge 3c_1+k_i\) 这个 \(k_i\) 并不唯一，如果你推出来其它的数值，也是对的。

接下来，可以断言：这个必胜条件对于原游戏仍然成立。

这看起来很违反直觉，因为后手虽然在原游戏中仍然能找到 \(0,1\) 相邻，但先手不一定能找到两个相邻的 \(0\)。

我们将这个 Claim 做一个等价转化：如果原问题（移除相邻字符）与转化后的游戏（移除任意位置字符）的胜负结果一致，那么当原问题中先手无法操作时，转化后的游戏中先手也一定会输。

而先手无法操作时，序列一定形如 \(0101\cdots0101\)，即 \(c_1\ge c_0\)，这个条件和上述四个先手必胜条件都相悖，因此先手必败。证毕。

原问题转化为求满足上述四个条件之一的子串有多少个。我们将序列中的 \(1\) 看作 \(-3\)，\(0\) 看作 \(1\) 求前缀和，条件 \(c_0\ge 3c_1+k_i\) 便等价于区间和 \(\ge k_i\)。

对\(\bmod 4\) 相同的下标维护一个树状数组，每次到这四个树状数组里统计贡献。

时间复杂度 \(O(n\log n)\)。

CF1895C. Torn Lucky Ticket

*1400 Code

上手直接蟒就容易写成一坨的题。（至少我是这样QAQ

这里给出一种优雅的解法。以下默认 0-index。

把数字看成字符串，记 \(f(i,j)\) 代表第 \(i\) 位到第 \(j\) 位之间数位的和。

遍历每个串，设当前串长为 \(m\)，\(\forall i\in[0,m)\)，将二元组 \(\{f(0,i)-f(i+1,m-1),(i+1)-(m-i-1)\}\) 记录进一个 std::map 中。

枚举每个串作为拼接左侧，能与它拼起来构成 pair 的字符串数等价于二元组 \(\{f(0,m-1),m\}\) 和 \(\{-f(0,m-1),-m\}\) 的数目和。

容易发现一个字符串既能做左侧合法拼接又能做右侧合法拼接的情况被规避掉了，计数不重不漏。

时间复杂度 \(O(n\log n)\)。

CF1895D. XOR Construction

*1900 Code

设 \(s_i=a_1\oplus a_2\oplus \cdots \oplus a_i\)。

则 \(\forall i>1\)，\(b_i=b_{i-1}\oplus a_{i-1}=b_{i-2}\oplus a_{i-2}\oplus a_{i-1}=\cdots=b_1\oplus s_{i-1}\)。

要让 \(b_i<n\)，就是让 \(\max\limits_{i\in[1,n]}(b_1\oplus s_{i-1})<n\)。

枚举 \(b_1\)，用 trie 找到这个异或最大值，看它是否 \(<n\)。

因为单次判断是 \(\log\) 级别的，从 \(0\) 到 \(n-1\) 暴力枚举就好。

时间复杂度 \(O(n\log w)\)，\(w\) 是值域。

CF1894D. Neutral Tonality

*1700 Code

依据 Dilworth 定理，\(\{b\}\) 一定是排成降序最优，此时插进 \(\{a\}\) 中最多让 LIS 长度 \(+1\)。

我们只需尝试构造一种插入方式使得 LIS 长度尽可能不变。

贪心地想，对于当前 \(a_i\)，可以将最小值 \(\ge a_i\) 的一段下降序列插入到 \(a_i\) 的前面，此时 LIS 长度一定不会增加。

维护一个双指针即可。

时间复杂度 \(O(n\log n)\)。

CF1894E. Freedom of Choice

*2000 Code

设 \(L=\sum\limits_{i=1}^{m} l_i\)，\(R =\sum\limits_{i=1}^{m} r_i\)，\(N=\sum\limits_{i=1}^{m}n_i\)。

断言：当 \(R-L+1>N\) 时，答案为 \(0\)。

根据 anti-beauty 的定义，一个 \(|X|\) 对应一个 \(a_i\)，而 \(a_i\) 一共有 \(N\le 10^5\) 种取值。当 \(|X|\) 有 \(R-L+1>N\) 种取值时，由抽屉原理，一定存在一个 \(|X|\) 没有 \(a_i\) 与之对应，此时答案为 \(0\)。

否则我们可以 \(O(N)\) 枚举 \(|X|\in [L,R]\)，对于每一个 multiset，策略一定是 "若能不拿 \(|X|\) 就不拿"。

具体地，初始化计数器 \(cnt=0\)。对于当前 multiset，除了 \(|X|\) 之外所有 \(a_i\) 的 \(c_i\) 之和为 \(s\)，若 \(s<l_i\)，则有 \(l_i-s\) 个 \(|X|\) 是必须要拿的，令 \(cnt\leftarrow cnt+l_i-s\) 且 \(s\leftarrow l_i\)；否则 \(s=\min(s,r_i)\)。将每个 multiset 的 \(s\) 求和，设为 \(S\)。

若 \(S\ge |X|\)，说明我们只需支付必要的 \(cnt\) 个 \(|X|\) 就能满足要求，当前 \(|X|\) 的答案就是 \(cnt\)；否则，我们还需在 \(cnt\) 的基础上支付额外的 \(|X|-S\)。

当然，我们不能对每个 \(|X|\in[L,R]\) 都枚举所有 \(m\) 个 multisets。我们用一个 std::map<int, set<int>> 预处理出 \(|X|\) 存在于哪些 multiset 中。此外还需要记录在每个 multiset 中 \(|X|\) 的 \(c_i\) 是多少。

时间复杂度 \(O(N\log N)\)。

CF2028D. Alice's Adventures in Cards

*2000 Code

Alice 能从第 \(i\) 列移动到第 \(j\ (j>i)\) 列当且仅当 \(\exists k\in\{0,1,2\}\)，\(a[k][j]<a[k][i]\)。

考虑从后向前枚举 \(i\)，维护 \(dp[i]\) 表示 Alice 能否从第 \(i\) 列经过一系列移动到达第 \(n\) 列。

为方便转移，令 \(\text{minp}[k]\) 代表第 \(k\) 行的当前后缀中 \(dp=1\) 且值最小的元素的下标，那么 \(dp[i]=1\) 当且仅当 \(\exists k\in \{0,1,2\}\)，\(a[k][\text{minp}[k]]<a[k][i]\)。

同时若 \(dp[i]=1\)，就 check 一下每一行的 \(\text{minp}\) 能不能更新。

时间复杂度 \(O(n)\)。

CF2028E. Alice's Adventures in the Rabbit Hole

*2300 Code

令 \(f_x\) 表示点 \(x\) 的答案，由题 \(f_{1}=1\)，\(f_{leaf}=0\)。

每次轮到 Alice 操作肯定是向根节点走，轮到皇后操作肯定是前往距当前节点最近的叶子。

设当前研究的点为 \(x\)，点 \(y\) 是 \(x\) 的儿子且在 \(x\) 的所有儿子中离叶子最近，则： \[ f_x=\frac{1}{2}(f_{fa}+f_y) \] 尝试待定系数，设 \(f_x=k_xf_{fa}+b_x\)，代入。

\[ \begin{align} f_x={\color{Red}k_x}f_{fa}+\color{Green}{b_x}&=\frac{1}{2}(f_{fa}+f_y)\\ &=\dfrac{1}{2}(f_{fa}+k_yf_x+b_y)\\ &=\frac{1}{2}(f_{fa}+k_y(k_xf_{fa}+b_x)+b_y)\\ &=\frac{1}{2}((k_xk_y+1)f_{fa}+k_yb_x+b_y)\\ &={\color{Red}\frac{1}{2}(k_xk_y+1)}f_{fa}+{\color{Green}\frac{1}{2}(k_yb_x+b_y)} \end{align} \]

标红的两项对应相等，标绿的两项对应相等，解得： \[ k_x=\frac{1}{2-k_y}\qquad b_x=\frac{b_y}{2-k_y} \] 又因叶子节点有 \(k_{leaf}=b_{leaf}=0\)，根据 \(b_x\) 递推式易知对于任意节点 \(b_x\) 均为 \(0\)。

用一遍 dfs 至下而上求出每个节点的 \(k_x\)，再 dfs 一遍即可求出 \(f_x\)。

时间复杂度 \(O(n)\)。

CF1820E. The Fox and the Complete Tree Traversal

*2400 Code

萌萌性质题。手玩之后做出如下 Claim。

能找到一个符合要求的回路当且仅当整棵树是一个毛毛虫（由一条主链和长度不超过 \(1\) 的支链组成的结构）。而整棵树是毛毛虫时，直径显然可以充当主链。

换句话说，Yes 当且仅当这棵树由直径和接在直径上的若干单点组成。

令 \(dp[x]\) 代表 \(x\) 的子树中以 \(x\) 为毛毛虫的头的最大毛毛虫大小。转移是朴素的，最后只需判断这棵树的最大毛毛虫大小是否等于 \(n\)。如果你不熟悉可以看一下 \(\to\) Link。

最后是构造方案。如下图构造即可（\(x,y\) 是直径端点），其实就是看这个点在直径序列上下标的奇偶性。

时间复杂度 \(O(n)\)。

CF1982E. Number of k-good subarrays

*2300 Code

设 \(f(x,y)\) 代表 \(n=x,k=y\) 时的答案，考虑分治： \[ f(n,k)\to f(m,k),f(n-m,k-1) \] 其中 \(m=\text{bit}\underline{}\text{floor}(n)\)。后一部分相当于把最 \(n\) 最高位的 \(1\) 拿掉，所以是 \(k-1\)。

分治的时候对当前 \((n,k)\) 返回一个三元组 \((l,r,ans)\)，分别代表最大的 \(l\) 满足 \([0,l)\) 是 k-good 的，最小的 \(r\) 满足 \([n-r,n)\) 是 k-good 的，以及当前状态的答案。

合并的时候类似线段树维护前后缀，分情况讨论即可。

时间复杂度 \(O(t\log^2 n)\)，其中一个 \(\log\) 来自 std::map 的记忆化。

CF1797E. Li Hua and Array

*2300 Code

将值域内的所有 \(x\) 与 \(\varphi(x)\) 连边（\(\varphi(x)\) 是 \(x\) 的父亲），构成一棵深度为 \(O(\log w)\) 的树，根是 \(1\)。

操作 \(1\) 相当于让一段区间内的点同时跳向父亲，操作 \(2\) 相当于求一段区间内的点的深度和，以及一段区间内所有点的 LCA 的深度。

对于操作 \(1\)，因为树高是 \(\log\) 级别，所以可以暴跳。若一个点跳到了 \(1\)，它后面就不再跳了，故用双向链表维护非 \(1\) 的节点。这样所有的操作 \(1\) 复杂度之和不超过 \(O(n\log w)\)。

对于操作 \(2\)，因为我们采取暴跳，所以深度和是好维护的，每跳一步就用线段树对深度进行单点修改。最多修改 \(O(n\log w)\) 次，故复杂度为 \(O(n\log n\log w)\)。

最后一个问题就是如何快速求若干点的 LCA，有结论：

一堆点的 LCA 等同于 "dfs 序最小点" 和 "dfs 序最大点" 的 LCA。

还是用线段树维护一段区间里最小 dfn 和最大 dfn，这样就是单 \(\log\) 的。

编码时要注意并不需要倍增求 LCA，暴跳求 LCA 就行了，因为空间限制不允许你倍增。

时间复杂度 \(O(w+n\log n\log w+m\log n)\)，\(w\) 是值域。

CF1974G. Money Buys Less Happiness Now

*2000 Code

非常经典的反悔贪心。契机是每次换取的幸福值是一样的，你只关心得到了多少，而不关心来自哪次交易。

用一个大根堆存储已经进行完交易的 \(c_i\)，每次没钱时就把堆顶弹出来。

时间复杂度 \(O(m\log m)\)。

CF1797F. Li Hua and Path

*3000 Code

这篇题解将会用到 Kruskal 点权多叉重构树。推荐前往 Link 了解，如果你未曾接触过。

我们将树上的一对 pair \((u,v)\) 分成三类，\(A\) 类满足 \(u\) 是 \(u\to v\) 上的最小点，\(B\) 类满足 \(v\) 是 \(u\to v\) 上的最大点，\(C\) 类则同时满足 \(u\) 是最小点且 \(v\) 是最大点。简单容斥，答案是 \(|A|+|B|-2|C|\)。

先考虑 \(A\) 类路径的个数怎么求。求 \(A\) 类本质上是对每一个点 \(i\)，找从 \(i\) 出发只经过编号大于等于 \(i\) 的点能到达的点集大小。我们按点权从大到小的顺序建出原树的 Kruskal 点权多叉重构树（后文称为 \(A\) 树），此时这棵树满足小根堆的性质，对于其上任意一点 \(x\)，从 \(x\) 出发能到达的点全在 \(x\) 的子树中。因此 \(|A|=\sum\limits_{i=1}^{n}(sz_i-1)\)。\(sz_i\) 代表重构树上点 \(i\) 的子树大小。

同理 \(B\) 类路径就是按点权从小到大建树（称为 \(B\) 树），这棵树满足大根堆的性质。

接着考虑 \(C\) 类路径。一个 pair \((u,v)\) 满足 \(C\) 类当且仅当 \(u\) 在 \(A\) 树上是 \(v\) 的祖先，且 \(u\) 在 \(B\) 树上是 \(v\) 的子孙。容易将这个问题转化为子树加，利用树状数组维护。

最后考虑那 \(m\) 次操作。注意到我们加的点的编号递增，这能引申出一系列良好的性质。

设新加的点编号为 \(x\)，则 \(x\) 在 \(A\) 树上一定是叶子，在 \(B\) 树上一定是根。进一步，\(x\) 对 \(A\) 类的贡献就是它的深度（对每个祖先贡献 \(1\) 的子树大小），对 \(B\) 类的贡献就是加进去的时候整个 \(B\) 树的大小（即 \(x-1\)）。对于 \(C\) 类，因为 \(x\) 编号最大，只能作为 pair 的第二维，\((u,x)\) 是 \(C\) 类当且仅当 \(u\) 在 \(A\) 树上是 \(x\) 的祖先，且在 \(B\) 树上是 \(x\) 的子孙。换句话说 \(C\) 类贡献与 \(A\) 类相同，是 \(x\) 的深度。

时间复杂度 \(O(n\log n)\)。

abc396g. Flip Row or Col

Code

对于一行来说，如果这一行有 \(c\) 个 \(1\)，我们肯定是调整至 \(\min(c,W-c)\) 个 \(1\)。

记 \(B_i\) 代表第 \(i\) 行对应的十进制数，枚举每一列是否翻转，答案是： \[ \min_{X=0}^{2^W-1}\sum_{i=0}^{H-1}\min(\text{popcount}(B_i\oplus X),W-\text{popcount}(B_i\oplus X)) \] 对于枚举的每一种列状态，时间复杂度不允许我们再枚举每一行，我们考虑对把 \(\text{popcount}(B_i\oplus X)\) 相同的 \(i\) 一起统计。

令 \(dp[X][c]\) 代表满足 \(\text{popcount}(B_i\oplus X)=c\) 的 \(i\) 的数量，枚举 \(X,c\) 以及 \(j\in[0,W)\to\) 从状态 \(X\oplus 2^j\) 转移过来。

答案是 \(\min\limits_{X=0}^{2^W-1}\sum\limits_{c=0}^{W}dp[X][c]\cdot\min(c,W-c)\)。时间复杂度 \(O(W^22^W)\)。

CF2029E. Common Generator

*2100 Code

Claim 1. \(2\) 能生成所有的合数。

首先，\(2\) 的倍数显然可以合成。否则假设当前合数为 \(x\)，\(x\) 一定可以表示成 \(x=pq\)，其中 \(p\) 是 \(x\) 的最小质因数且 \(p\ge 3,q>1\)。又 \(pq\) 可以由 \((p-1)q\) 合成，而 \(p-1\) 是偶数，偶数可以由 \(2\) 生成，故 \(x=pq\) 可以由 \(2\) 生成。

Claim 2. 质数只能由它自己生成。（显然，不证了）

至此我们扫一遍 \(\{a\}\)，若没有质数，答案是 \(2\)；若有不同的质数，无解。

否则设唯一质数为 \(p\)，我们只用考虑 \(p\) 能否生成 \(\{a\}\) 中剩下的所有数。

Claim 3. \(p\) 能生成偶数 \(x\) 当且仅当 \(x\ge 2p\)。

因为 \(p\) 第一步只能变成 \(2p\)，\(2p\) 又是偶数。之后一直 \(+2\) 得到所有 \(\ge 2p\) 的偶数。

Claim4. \(p\) 能生成奇合数 \(x\) 当且仅当 \(x-\text{minp}_x\ge 2p\)，其中 \(\text{minp}_x\) 是 \(x\) 的最小质因数。

\(x-\text{minp}_x\) 是最大的 \(< x\) 的偶数。若 \(x-\text{minp}_x < 2p\)，即最大的能生成 \(x\) 的偶数都无法生成，自然无解。

素数和最小质因数都能线性筛，这样每组数据就是线性的。

时间复杂度 \(O(w+n)\)，\(w\) 是值域。

arc194c. Cost to Flip

Code

用二元组 \((x,y)\) 代表状态 \(A_i=x,B_i=y\)。首先 \((0,1)\) 和 \((1, 0)\) 是无可避免的，\((0,0)\) 不用动，\((1,1)\) 既可以选择不动也可以选择 \(1\to 0\) 再 \(0\to 1\)。

依据贪心原则，满足状态 \((1, 0)\) 的列肯定是按 \(c_i\) 从大到小进行操作，满足状态 \((0,1)\) 的列肯定是按 \(c_i\) 从小到大进行操作。此外，对于状态 \((1, 1)\)，也一定存在一个阈值 \(W\)，使得 \(C_i\le W\) 的列选择不动，\(C_i>W\) 的列选择 \(1\to 0\) 再 \(0\to 1\)。

我们考虑从小到大枚举这个阈值，列出式子并观察增量有何变化。

所有 \((1,1)\) 选择不动时，有： \[ ans=\sum_{p=1}^{X}(p-1)C_{ip}+\sum_{p=1}^{Y}pC_{jp}+(X+Y)\sum_{p=1}^{Z}C_{kp} \] 其中 \(C_{i1}\ge C_{i2}\ge C_{i3}\ge \ldots\ge C_{iX}\) 代表满足状态 \((1,0)\) 的 \(C\)，\(C_{j1}\ge C_{j2}\ge C_{j3}\ge \ldots\ge C_{jY}\) 代表满足状态 \((0, 1)\) 的 \(C\)，\(C_{k1},C_{k2},\ldots,C_{kZ}\) 则代表满足状态 \((1, 1)\) 的 \(C\)。

选中一个状态 \((1,1)\) 进行操作时，设对应的 \(C\) 为 \(C_x\)，最后一项会变成 \((X+Y+2)\left(\sum C_{kp}-C_x\right)\)。

对于前面两项，拿第一项举例。操作前： \[ 0\cdot C_{i1}+1\cdot C_{i2}+2\cdot C_{i3}+3\cdot C_{i4}+ 4\cdot C_{i5}+5\cdot C_{i6} \] 将 \(C_x\) 插入后： \[ 0\cdot C_{i1}+1\cdot C_{i2}+2\cdot C_{i3}+{\color{Green}3\cdot C_{x}}+{\color{Red}4}\cdot C_{i4}+ {\color{Red}5}\cdot C_{i5}+{\color{Red}6}\cdot C_{i6} \] 插入的位置可以二分出来，增量则是一段后缀。

但这并不意味着需要动态维护后缀和，因为我们插入的 \(C_x\) 递减，每次插入的位置一定在之前的 \(C_x\) 之后。

时间复杂度 \(O(n\log n)\)。

arc194d. Reverse Brackets

Code

建出括号树（包括虚根），一次操作相当于选定一个点 \(x\)（设 \(x\) 的儿子按原序列顺序依次是 \(y_1,y_2,y_3,\ldots\)），接着选定一个区间 \([l,r]\)，将 \(y_l,y_{l+1},\ldots,y_r\) 连带它们的子树翻转。

不难发现如此操作能任意排列一个点的儿子。

接着就是数树的形态了。我们把同构的两棵子树用相同的数字表示，对于一个点来说，将以它所有儿子为根的子树代表的数字排成序列，方案数相当于重排这个序列能得到的本质不同的序列数量。

使用树哈希容易做到 \(O(n\log n)\) 或 \(O(n)\)。

CF2071F. Towering Arrays

*2700 Code

题外话：时限 6s，拼尽全力卡常喜提 5999ms。上面代码放的是没有刻意卡常的版本，clone 下来跑了 7s。

二分答案，设二分出的答案是 \(p\)，我们就要找到最长的 \(p-towering\) 序列的长度 \(m\)，判断是否 \(n-m\le k\)。

考虑遍历序列上的每一个位置 \(i\)，check \(a_i\) 是否能作为 \(p-towering\) 序列的最高点。此时 \(a_i\) 两侧延伸出去的长度独立，我们可以只考虑一边，然后把序列 reverse 做另一边。

现在的问题是对于每一个 \(i\)，求序列 \(a_1\sim a_i\) 中以 \(a_i\) 结尾的最长的子序列 \(\{s\}\)，满足 \(s\) 最后一个元素 \(\ge p\)，倒数第二个元素 \(\ge p-1\)，倒数第三个元素 \(\ge p-2\)，\(\ldots\)

结论：若 \(a_{i}\ge p\)，对于任意满足 \(j<i\) 且 \(a_j\ge p\) 的 \(j\)，序列 \(a_1\sim a_i\) 构造出的 \(\{s\}\) 一定完全包含序列 \(a_1\sim a_{j}\) 构造出的 \(\{s\}\) 中的元素。换句话说随着 \(i\) 增加，我们一定只是在 \(\{s\}\) 的末尾添加元素。

当我们把 \(a_i\) 加进 \(\{s\}\) 后，\(\{s\}\) 中倒数第 \(i\) 个元素要求 \(\ge p-i+1\)，而在原来的 \(\{s\}\) 中倒数第 \(i-1\) 个元素满足 \(\ge p-i+2\)。故得证。

一个使用线段树维护 \(\{s\}\) 最长长度的流程是：

按顺序扫描序列，对于当前 \(i\)，给线段树上第 \(i\) 个位置赋值 \(p-a_i\)。
找到 \(1\sim i\) 中最后一个值 \(\le0\) 的位置，设下标为 \(t\)。将 \(a_t\) 加进 \(\{s\}\) 中，并给线段树上 \(1\sim t\) 这段前缀 \(-1\)。（多一个元素自然前面的元素限制 \(-1\)）
将位置 \(t\) 设为 \(+\infty\)。（保证已经选中的之后不再选中）
重复步骤 \(2,3\) 直到找不到值 \(\le 0\) 的位置。此时 \(\{s\}\) 中元素个数即为当前 \(i\) 的答案。

时间复杂度 \(O(n\log n\log w)\)，\(w\) 是值域。

CF2074G. Game With Triangles: Season 2

*2100 Code

区间 dp。拆环成链，记 \(dp[L][R]\) 为区间 \([L,R]\) 的答案。

从小到大枚举长度，对于当前 \([L,R]\)，枚举 \(k\in[L+1,R-1]\) 让 \(L,k,R\) 成为三角形的三个顶点。 \[ dp[L][R]=\max_{k\in(L,R)}(dp[L+1][k-1]+dp[k+1][R-1]+a_L\cdot a_k\cdot a_R) \] 别忘了还有区间 dp 的定义式： \[ dp[L][R]=\max_{k\in[L,R)}(dp[L][k]+dp[k+1][R]) \] 时间复杂度 \(O(n^3)\)。

CF1994D. Funny Game

*1900 Code

我们只关心连哪些边，而不关心连边的顺序。

按 \(x\) 从大到小考虑，我们每次将选出的两个点用并查集连起来，这样每次操作后连通块个数 \(-1\)。

第一次操作，要找到两个点 \(u,v\) 满足 \(|a_u-a_v|=n-1\)，换个写法就是 \(a_u\equiv a_v\pmod{n-1}\)。此时图上有 \(n\) 个连通块，从每个连通块里任选一个点，就是 \(n\) 个点。根据鸽笼原理，这 \(n\) 个点里一定存在一对 \(u,v\) 满足 \(a_u\equiv a_v\pmod{n-1}\)。

第二次操作，要找到两个点 \(u,v\) 满足 \(a_u\equiv a_v\pmod{n-2}\)。此时图上有 \(n-1\) 个连通块，从每个连通块里任选一个点，就是 \(n-1\) 个点。根据鸽笼原理，这 \(n-1\) 个点里也一定存在一对 \(u,v\) 满足 \(a_u\equiv a_v\pmod{n-2}\)。

第三次操作，\(\ldots\)

综上，本题一定有解，按照上述流程构造一个即可。

时间复杂度 \(O(n^2)\)。

CF1994F. Stardew Valley

*2500 Code

把有 NPC 的边称为 \(1\) 边，否则称为 \(0\) 边。

我们要找到一条经过每条 \(1\) 边恰好一次的回路。可以将该问题转化为选择一些 \(0\) 边删掉，使得图中所有点的度均为偶数，这样我们只用跑一遍欧拉回路就行。

当我们删除一条边时，如果两个端点原来都是奇度点，那么图中奇度点个数 \(-2\)；如果两个端点原来度数一奇一偶，那么图中奇度点个数不变。

于是，建出一个只有 \(0\) 边的图，YES 的充要条件就是对于图中每个连通分量，奇度点个数均为偶数。

一个较好的实现是：对每个连通分量 dfs，在 dfs 生成树上至下而上贪心地删边，若删到根后根是奇度点，就是 NO。这样删哪条边也顺便记录了。

时间复杂度 \(O(n)\)。

CF2049F. MEX OR Mania

*2700 Code

由 \(\text{mex} \le \text{max}+1\le \text{or}+1\)，题目条件成立当且仅当这两个不等号同时取等。

\(\text{mex}=\max +1\) 当且仅当序列包含了 \(0\sim \max\) 中的所有数，\(\text{or}=\max\) 当且仅当序列中的数在二进制下是 \(\max\) 的子集。同时取等意味着这个序列包含了 \(0\sim 2^k-1\) 中的所有数，\(k\in N\)。

我们不妨枚举每个 \(k\)，判断是否存在一段区间包含了 \(0\sim 2^k-1\) 中的所有数，且不包含 \(\ge 2^k\) 的数。

在不考虑修改的情况下，我们可以把 \(<2^k\) 的数用并查集连在一起，然后用一个 unordered_map 维护这个连通块不同的数的个数。若不同的数的个数恰好是 \(2^k\)，就说明这个连通块是符合条件的。

接下来我们面临 \(q\) 次单点加，当区间里的一个数超出了 \(2^k-1\)，这个区间就会分成两个子区间，这是不好处理的。

于是考虑离线，倒着操作序列，变成单点减。我们依旧是对每个 \(k\) 维护一个并查集，将 \(< 2^k\) 的数连在一起，这样每次只用考虑是否可以将被操作的位置的两端合并成一个大区间。若可以，就启发式合并，将小的那一段区间 unordered_map 记录的信息合并到大的那一段区间来。

时间复杂度 \(O(n\log^2 n)\)。

CF2078G. Another Folding Strip

*2700 Code

两个格子通过折叠能一上一下挨着当且仅当这两个格子的下标之差为奇数。

换句话说，一次操作相当于选择一组下标序列 \(i_1,i_2,i_3,\ldots\)，其中 \(\forall k > 0\)，\(i_{k}\) 与 \(i_{k+1}\) 奇偶性不同，然后使这些位置上的值 \(+1\)。

倒着考虑，每次让一组下标序列对应位置上的值 \(-1\)，问将 \(\{a\}\) 变成全 \(0\) 序列的最小操作次数。

对序列进行黑白染色：\(\forall i\in[1,n]\)，令 \(b_i=(-1)^ia_i\)。

令一次操作后的 \(\{b\}\) 为 \(\{b'\}\)，一个很强的性质是对于 \(1\sim n\) 上任意一个区间 \([l,r]\)，有 \(\left|\sum\limits_{i=l}^{r}b'_i-\sum\limits_{i=l}^{r}b_i\right| \le 1\)。

这意味着若 \(\{b\}\) 上存在一个和为 \(k\) 的子段，那么这个子段至少要进行 \(|k|\) 次操作才能变为全 \(0\)。

故 \(f(a_1a_2\ldots a_n)\) 的下界是 \(\max\limits_{1\le l\le r\le n}\left|\sum\limits_{i=l}^{r}b_i\right|\)。事实上能够证明该下界可达，具体见官方题解。（毕竟下标序列的选择条件是相当宽松的，退一步写一个 \(O(n^2)\) 检验样例也很容易，这里就不证了）

令 \(pre_i=\sum\limits_{j=1}^{i}b_j\)，式子变成 \(\max\limits_{1\le l\le r\le n}\left|pre_r-pre_{l-1}\right|\)，即 \(\{pre\}\) 的极差。

原问题转化为求 \(\{b\}\) 所有连续子序列的极差之和。枚举一个数作为极大值/极小值占领的区间，单调栈或线段树均可做。

时间复杂度 \(O(n\log n)\) 或 \(O(n)\)。

CF2082F. MST in Modulo Graph

*2600 Code

对每一个 \(p_i\)，枚举 \(k=p_i,2p_i,3p_i,\ldots\)，再二分出第一个 \(\ge k\) 的 \(p_j\)。将这对 \((i,j)\) 放进候选表里。

此时对于 \(p_i\) 来说，\(p_j\bmod p_i\) 最小的 \(p_j\) 一定在候选表中。

最终我们会有 \(O(n\log n)\) 条候选边（调和级数效应）。用这些边跑最小生成树即可。

时间复杂度 \(O(n\log^2 n)\)。

CF2075D. Equalization

*2000 Code

每次操作相当于将二进制下的 \(x\) 或 \(y\) 右移一定位数。

假若我们确定了最优答案中 \(x\) 右移了 \(k_1\) 位，\(y\) 右移了 \(k_2\) 位，该如何计算最小操作次数？

将一次花费 \(2^k\) 的操作看作一个物品，这个物品的体积是 \(k\)，价值是 \(2^k\)，且每个物品至多被选一次。

也就是说这是一个 \(01\) 背包问题，而且是两个背包，容量分别为 \(k_1\) 与 \(k_2\)。

令 \(dp[i][j]\) 为两个背包分别塞了 \(i\) 体积和 \(j\) 体积东西时的选取物品的最小价值。

初态：\(dp[i][j]=\begin{cases}0&,i=0\cap j=0\\ \infty &,\text{otherwise}\end{cases}\)
转移：\(dp[i][j]=\min\limits_{1\le k\le 60}\begin{cases}dp[i-k][j]+2^k &,k\le i\\ dp[i][j-k]+2^k &,k\le j\end{cases}\)
答案：\(dp[k_1][k_2]\)。

但事实上 \(k_1\) 和 \(k_2\) 并不能贪心地确定。

正确的做法是枚举所有 "\(x\) 右移 \(k_1\) 位 \(=\) \(y\) 右移 \(k_2\) 位" 的 \(k_1\) 与 \(k_2\)。

时间复杂度 \(O(\log^3w)-O(\log^2 w)\)，\(w\) 为值域。

CF1808D. Petya, Petya, Petr, and Palindromes

*2100 Code

正难则反，用总和减去相等数对造成的贡献得到答案。

所有长为 \(k\) 的子串的 palindromicity 之和为 \(\lfloor\frac{k}{2}\rfloor(n-k+1)\)。

考虑满足 \(a_i=a_j\) 的一对 \((i,j)(i<j)\)，这对 \((i,j)\) 能造成 \(1\) 的贡献当且仅当：

\(i\bmod 2=j\bmod 2\)；
\(j-i+1\le k\)；
\(i-\frac{k-(j-i+1)}{2}\ge 1\)；
\(j+\frac{k-(j-i+1)}{2}\le n\)。

解得 \(j\in [\max(i+1,k+1-i),\min(n,i+k-1,2n-k-i+1)]\)。

将 \(\{a\}\) 按照下标奇偶分成两个数组。对每个数组 \(\{b\}\)，枚举 \(i\)，二分出上述区间里有多少个 \(j\) 满足 \(b_i=b_j\)，计入贡献。

时间复杂度 \(O(n\log n)\)。

CF1808E1/E2. Minibuses on Venus

*2200 Code（E1）

*2500 Code（E2）

将 \(n\) 个数位看成一个长为 \(n\) 的数列 \(\{a\}\)，每个元素的取值是 \([0,k)\)。

一个数列满足条件当且仅当 \(\exists i\in[1,n]\)，\(a_i\equiv a_1+a_2+\ldots+a_{i-1}+a_{i+1}+\ldots a_n\pmod{k}\)。

令 \(S=\sum\limits_{i=1}^{n}a_i\)，则改写为 \(a_i\equiv S-a_i\pmod {k}\)，也就是 \(2a_i\equiv S\pmod {k}\)。

容斥，用总方案数 \(k^n\) 减去 \(\forall i\in[1,n]\)，\(2a_i\not\equiv S\pmod {k}\) 的 \(\{a\}\) 的数量。

当我们每次往 \(\{a\}\) 里添一个数时，\(S\) 会动态变化。但\(\bmod k\) 下 \(S\) 只有 \(k\) 种取值，所以我们可以枚举 \(S\)。

对于一个固定的 \(S\)，满足条件的序列数量可以用动态规划求解。

令 \(dp_{i,j}\) 表示已经填了前 \(i\) 个数，这 \(i\) 个数和为 \(j\) 的方案数。

初态：\(dp_{0,0}=1\)；
转移：\(\forall x\in [0,k),\forall j\in[0,k),2x\not\equiv S\pmod {k}\)，\(dp_{i,(j+x)\bmod k}=dp_{i,(j+x)\bmod{k}}+dp_{i-1,j}\)；
答案：\(dp_{n,S}\)。

时间复杂度 \(O(nk^3)\)，可以通过 E1。

这个转移看起来就很矩阵，于是令矩阵 \(A_{i,(i+j)\bmod k}=[2j\not\equiv S\pmod{k}]\)，则： \[ [dp_{i,0},dp_{i,1},\cdots,dp_{i,k-1}]\times A=[dp_{i+1,0},dp_{i+1, 1},\cdots,dp_{i+1,k-1}] \]

初态：\(dp_0=[1,0,0,\cdots,0]\)；
答案：\(dp_{0}\times A^{n}\) 的第 \(S\) 项。

矩阵快速幂是 \(O(k^3\log n)\)，加上枚举 \(S\)，就是 \(O(k^4\log n)\) ，并不能通过 E2。Code

但注意到 \(A\) 是一个循环矩阵（每一行都是上一行的循环右移），这意味着我们可以把 \(dp_{i,0}\sim dp_{i,k-1}\) 看成多项式的系数，用循环卷积去优化它。

具体地，定义多项式 \(f_i(x) = dp_{i,0}\cdot x^0+dp_{i,1}\cdot x^1+\cdots+dp_{i,k-1}\cdot x^{k-1}\)。

转移多项式 \(G(x)\) 取 \(A\) 的第一行，也就是 \([x^i]G(x)=[2i\not\equiv S\pmod{k}]\)。

答案即 \([x^S](f_0\times G^n(x))\)。

时间复杂度 \(O(k^3\log n)\)，如果会 FFT 能做到 \(O(k^2\log n)\)。能吗？反正我不会QAQ。

abc397g. Maximize Distance

Code

二分答案，设二分出的答案是 \(d\)，那么需要判定让 \(1\to n\) 的最短路为 \(d\) 的最小操作次数是否 \(\le K\)。

当 \(d=1\) 时，问题等价于选定一个最小边集，使得任何一条从 \(1\to n\) 的路径都无可避免地经过这个边集中的边。换句话说，边集中的边将原图分割成了两部分，即最小割。

当 \(d>1\) 时，我们能通过建模将问题转化为一个分层图的最小割。

上图是 \(d=1\) 的情况，标注出的数字代表流量。考虑同样的图，但 \(d=3\)：

这只是一个分层图的框架，当我们需要让 \(1\to n\) 的最短路为 \(3\) 时，会出现一些问题。

左图是我们期望的：分层图的每一层都选定了一些边，且每一层选定的边都组成了原图的一个最小割。把它们割掉，原图不连通，这样一个 \(d\) 层的分层图的最小割就是让 \(1\to n\) 的最短路为 \(d\) 的最小操作次数。但能这么做的前提是每一层选定的边集互不相同，右图中我们只选定了三条边就能让图不连通，显然不合法。

解决方案是对于每一条存在于原图中的边 \((u,v)\)，\(\forall i\in[1,d)\)，从第 \(i\) 层的 \(u\) 向第 \(i+1\) 层的 \(v\) 连边。这样选中不同层的同一条边就没有了意义。

时间复杂度 \(O(\text{maxflow}(n^2,mn+n^2)\log n)\)。

CF2035E. Monster

*2300 Code

假设我们总共使用了 \(a\) 次操作 \(1\)，\(b\) 次操作 \(2\)。

贪心地想，最优策略一定是 "提升 \(k\) 次攻击力，打一次"，"提升 \(k\) 次攻击力，打一次"，\(\ldots\)，如此反复 \(c=\min(\left\lfloor\frac{a}{k}\right\rfloor,b)\) 次，再将剩下的 \(a\bmod k\) 次攻击力提升用完，打 \(b-c\) 次怪物。

等差数列求和，造成的总伤害 \(\text{damage}(a,b)=\frac{c(c+1)}{2}k+a(b-c)\)，总代价 \(\text{cost}(a,b)=ax+by\)。

发现当 \(a\) 固定时，\(\text{damage}(a,b)\) 随着 \(b\) 增加单调不降；当 \(b\) 固定时，\(\text{damage}(a,b)\) 随着 \(a\) 增加单调不降。

于是可以枚举 \(a\)，二分出使得 \(\text{damage}(a,b)\ge z\) 的最小 \(b\)；或者枚举 \(b\)，二分出使得 \(\text{damage}(a,b)\ge z\) 的最小 \(a\)。

但 \(a,b\) 太大不能枚举，根据你对算法竞赛的了解这时候肯定从哪里推导出一个神秘的不等式然后把 \(a\) 或 \(b\) 的上界缩小。恭喜你猜对了。（实际上你可以根据时限和数据组数试一个刚好不会超时的上界）

证明：\(\min(a,b)\le \sqrt{2z}\)。

当 \(k=1\) 时，攻击间隔最短，最低效。此时 \(c=\min(\left\lfloor\frac{a}{k}\right\rfloor)=\min(a,b)\)，而当你提升一次攻击力就打一次的时候，最后一次操作不是攻击肯定没有意义，所以 \(a\le b\)，故 \(c=a\)。
此时 \(\text{damage}(a,b)\ge \frac{a(a+1)}{2}+a(b-a)=\frac{a(2b-a+1)}{2}\ge \frac{a(2b-b+1)}{2}>\frac{ab}{2}\)。
当 \(\text{damage}(a,b)\) 取到 \(z\) 时，有 \(z>\frac{ab}{2}\)，即 \(ab<2z\)，\(\min(a,b)\le \sqrt{2z}\)，得证。

时间复杂度 \(O(\sqrt{z}\log z)\)。

CF2085C. Serval and The Formula

*1600 Code

\((x + k)+(y+k)=(x+k)\oplus(y+k)\) 等价于 \((x+k)\& (y+k)=0\)。

注意到 \(2^p\) 和任何 \(<2^p\) 的数按位与的结果都是 \(0\)。

故考虑把 \(x+k\) 和 \(y+k\) 中较大的那个构造成 \(2^p\) 的形式。

若 \(x=y\)，无解；否则不妨取 \(p=59\)，答案是 \(2^{59}-\max(x,y)\)。

时间复杂度 \(O(1)\)。

CF2085D. Serval and Kaitenzushi Buffet

*2000 Code

你选的第 \(i\) 个数的下标 \(p_i\) 一定满足 \(p_i\le n-i(k+1)+1\)。

按顺序遍历，每到一个这样的节点就从前缀里选一个还没被选的最大的数计入答案。

优先队列或线段树均可，时间复杂度 \(O(n\log n)\)。

CF2085E. Serval and Modulo

*2200 Code

最为关键的观察：\(\sum a-\sum b\) 是 \(k\) 的倍数。（因为 \(\forall i\in[1,n]\)， \(b_i\) 都由 \(a_i\) 减去若干个 \(k\) 得到）

枚举 \(\sum a-\sum b\) 的所有因数暴力 check，复杂度是可以接受的。

时间复杂度 \(O(n\cdot \sigma(\sum a_i)+\sqrt{\sum a_i})\)。

CF2090D. Simple Permutation

*1700 Code

\(1\sim n\) 内的素数都没有 \(\left\lfloor\frac{n}{3}\right\rfloor-1\) 这么多，所以一个素数肯定被用了不只一次。

考虑形如 \(p,p-1,p+1,p-2,p+2,\cdots\) 的结构，此时前缀和出现了 \(p,3p,5p,\cdots\)，它们除以 \(i\) 恰好都是 \(p\)。

为了让这个结构尽可能长，取 \(p\) 为最靠近 \(\frac{n}{2}\) 的素数即可。

时间复杂度 \(O(n)\)。

CF1654E. Arithmetic Operations

*2300 Code

考虑求出最多不需要修改的位置个数 \(cnt\)，答案就是 \(n-cnt\)。

设 \(\forall i\in [1,n]\)，\(b_i=a_i-i\cdot d\)。当公差 \(d\) 确定时，\(\{b\}\) 中众数的出现次数就是对应的 \(cnt\)。

阈值分治，设 \(B\) 为阈值。当 \(-B \le d \le B\) 时，直接枚举 \(d\)，扫一遍求众数，这部分是 \(O(nB)\)。

当 \(d< -B\) 或 \(d>B\) 时，若存在两个位置 \(i,j\) 不会被修改，那么 \(|i-j|\le \frac{W}{B}\)。

枚举左端点 \(i\)，右端点扫描 \([i+1,i+\frac{W}{B}]\)，若 \(j-i\mid a_j-a_i\)，那么 \(\dfrac{a_j-a_i}{j-i}\) 就是一个可能的公差。

把所有可能的公差都 \(O(n)\) check 一遍，是不能够接受的。

合理的做法是用一个桶对当前左端点 \(i\) 统计公差 \(\dfrac{a_j-a_i}{j-i}\) 的众数的出现次数，设为 \(tot\)，那么 \(cnt=tot+1\)。

时间复杂度 \(O(n(B+\frac{W}{B}))\)，显然 \(B\) 取 \(\sqrt{W}\) 最优。

CF1809F. Traveling in Berland

*2500 Code

\(b_i=1\) 的点是特殊的，因为总是可以假定我们在到达一个 \(b_i=1\) 的点时油量恰好为 \(0\)。（否则不如把剩余的油换到这个加油站来加）

定义 \(c(i,j)\) 代表从点 \(i\) 行驶到点 \(j\) 的最小代价，满足 \(b_i=1/2\) 但 \(b_j=1\)，且 \(b_{i+1}\sim b_{j-1}=2\)。（换句话说 \(b_j\) 是 \(i\to j\) 方向上最近的油价为 \(1\) 的点）

令 \(d=dis(i,j)\)，则： \[ c(i,j)=\begin{cases} 2d&,b_i=2\\ d&,b_i=1\cap d\le k\\ 2d-k&,b_i=1\cap d>k \end{cases} \] 这意味着从一个 \(b_i=1/2\) 的点到下一个 \(b_i=1\) 的点的代价是可以快速计算的。

破环成链。令 \(\text{nxt}[i][j]\) 代表点 \(i\) 的下 \(2^j\) 个油价为 \(1\) 点的编号，\(f[i][j]\) 代表点 \(i\) 到下 \(2^j\) 个油价为 \(1\) 的点的代价，倍增。

最后还要加上 "终点背后最近的 \(b_i=1\) 的点到终点的距离"。

时间复杂度 \(O(n\log n)\)。

CF1700C. Helping the Nature

*1700 Code

设差分数组 \(b_i=a_i-a_{i-1}\)。三种操作分别对应：

\(b_1\leftarrow b_1-1\) ，\(b_{i+1}\leftarrow b_{i+1}+1\) 。
\(b_{i}\leftarrow b_i-1\)。
\(b_1\leftarrow b_1+1\)。

题目转化为求最小的操作次数使得 \(\forall i\in [1,n]\)，\(b_i=0\)。

先考虑将 \(b_2\sim b_n\) 变成 \(0\)。涉及到 \(b_i,i\in [2,n]\) 的操作只有前两条，操作一能让一个 \(b_i\) 加一，操作二能让一个 \(b_i\) 减一。于是这部分的代价是 \(\sum\limits_{i=2}^{n}b_i\)。

再考虑将 \(b_1\) 变成 \(0\)。注意到操作二 \(i\) 取 \(1\) 时就是 "\(b_1\leftarrow b_1-1\)"，配合操作三，这部分的代价就是 \(|b_1|\)。

时间复杂度 \(O(n)\)。

CF1981C. Turtle and an Incomplete Sequence

*1800 Code

特判：初态不满足要求或全是 \(-1\)。

设左数/右数第一个不为 \(-1\) 的位置分别为 \(i,j\)，则 \(a_1\sim a_i\) 和 \(a_j\sim a_n\) 是好填的，反复 \(\times 2,\div 2\) 即可。

接下来问题转化为：给定长为 \(m\) 的数组 \(\{b\}\)，其中 \(b_1 \neq -1\)，\(b_m\neq -1\)，\(\forall i\in(1,m)\)，\(b_i=-1\)，求一个合法的填数。

不难发现固定了 \(b_i\)，那么 \(b_{i+1}\) 只有 \(\div 2\) 下取整，\(\times2\) 和 \(\times 2+1\) 三种选择，这相当于在标号满二叉树上向父亲/左儿子/右儿子走一步。于是问题变成了在满二叉树上找一条从 \(b_1\) 到 \(b_m\) 且长 \(m-1\) 的路径。

求出 \(b_1\) 和 \(b_m\) 在满二叉树上的 LCA，计算出 \(b_1,b_m\) 之间的简单路径长度 \(len\)（这里 \(len\) 是路径上除了 \(b_1,b_m\) 外点的数目）。那么若 \((m-2)<len\) 或 \(m-2 \not\equiv len\pmod{2}\)，就无解。

否则构造方式就是从两边分别跳父亲，中间的一段反复 \(\times 2,\div 2\) 补齐。

求 LCA 可以暴跳，时间复杂度 \(O(n\log w)\)，\(w\) 是值域。

Competitive Programming > Diary

#ICPC #Atcoder #Codeforces

【题解】三月训练日记

https://kisuraop.github.io/posts/5dc05f53.html

作者

KisuraOP

发布于

2025年2月23日

许可协议

【题解】2025 UESTCPC 初赛上一篇

【题解】2025 UESTC 寒假集训下一篇