消失的下雨天 我好想再淋一遍

同步在洛谷更新

题目难度应该不会很大

括号内的是 CF 难度，如果不是 CF 的题的话可能会根据体感难度来估算一个 CF 难度（

2026.03.11

天空仍灿烂 / 它爱着大海（周杰伦 花海）

001. CF1656F Parametric MST (*$\red{2600}$)

未看题解完成，用时 1hr 29min 18s。

注意到 $a_ia_j+t(a_i+a_j)=(a_i+t)(a_j+t)-t^2$（恭喜你你做完了这个题最难的一步）。最后的 $t^2$ 是容易省去的，于是问题可以转化为：

对于给定的 $t$ 值，你可以构造一棵 $n$ 个点的完全图，其中两点 $(i,j)$ 的边权是 $(a_i+t)(a_j+t)$，记 $f(t)$ 为按照上述步骤构造的图的 MST 边权之和，问 $f(t)$ 是否是有上界的。

先考虑对于给定的 $t$ 值怎么快速求出构造出完全图的 MST 大小。把所有点的点权 $a_i$ 按照从小到大的顺序排序，那么显然此时有 $a_1+t\le a_2+t\le\ldots\le a_n+t$。容易想到记 $p$ 是满足 $a_p+t\ge 0$ 的 $p$ 里最小的值，那么直接贪心的把 $a_p,a_{p+1},\ldots,a_n$ 都和 $a_1$ 连边，$a_2,a_3,\ldots,a_{p-1}$ 都和 $a_n$ 连边，容易证明该贪心策略一定可以得到最优解。

把这个式子写出来，即：

$$\sum\limits_{i=p}^na_1a_i+t\sum\limits_{i=p}^n(a_1+a_i)+\sum\limits_{i=2}^{p-1}a_na_i+t\sum\limits_{i=2}^{p-1}(a_n+a_i)$$

化简式子：

$$a_1\sum\limits_{i=1}^na_i+t(n-p+1)a_1+t\sum\limits_{i=p}^na_i+a_n\sum\limits_{i=2}^{p-1}a_i+t(p-2)a_n+t\sum\limits_{i=2}^{p-1}a_i$$

容易发现这个东西如果对 $t$ 已知 $p$ 那么可以预处理 $a$ 序列前缀和然后做到 $O(1)$ 计算答案。

但是问题是 $t$ 的取值范围是 $t\in\mathbb R$，显然无法枚举所有的实数 $t$ 来计算答案。考虑缩小最优解的 $t$ 的取值集合。这里注意到对 $t\in[a_i,a_{i+1}]$，$p$ 的取值都不会变化，而显然对同一个 $p$ 上面的式子是单峰的答案一定取在两个端点上，因此需要判定的 $t$ 的集合只有 $-a_1,-a_2,\ldots,-a_n$，而此时显然 $p$ 的值也是十分容易求出的。因此该算法时间复杂度优化到 $O(n)$ 可以通过该题。

最后剩下答案为 INF 的情况，直接带入 $t=\infin$ 和 $t=-\infin$ 即可简单判定（只需要看此时 $\infin$ 的项的系数是不是 $>0$ 的即可）。

该算法对于单组数据时间复杂度为 $O(n)$，可以轻松通过该题。

002. CF521D Shop (*$\red{2800}$)

未看题解完成，用时 34min 7s。

对一个位置而言赋值操作肯定最多进行一次，因此考虑直接贪心。注意到一定存在一个最优策略满足对每个位置，其执行的操作的顺序都是（赋值）-（加法）-（乘法），括号代表一个操作可有可无。证明可以简单 Exchange-Argument Trick 处理。

考虑先把所有的赋值操作对每个位置只保留赋值最大的操作，然后将其全部转化成加法操作，然后再把加法操作排序之后全部转化成乘法操作。乘法操作直接贪心选最大的 $m$ 个数执行操作即可。

总时间复杂度为 $O(n\log n)$ 可以轻松通过该题。

2026.03.12

一路不断失去 / 一生将不断见证 / 看过再多风景眼眸如初清澄（周深 亲爱的旅人啊）

003. CF852A Digits（*$\color{pink}{2500}$）

未看题解完成，用时 26min 18s。

有一个简单的贪心策略是直接把每个位置都拆开得到 $|s|$ 个长度为 $1$ 的数字然后直接加起来，但是这个贪心显然是错的。

考虑直接错上加错，以一定概率把两个长度为 $1$ 的数字合并起来（实测概率取 $\frac1{15}$ 可以通过）然后再加起来合并，就可以通过这题。

成功率不太会算，但是这一看就很不能卡 :)

004. 暂时不能公开

2026.03.13

好想再问一遍 / 你会等待还是离开（周杰伦 晴天）

005. P15653 [省选联考 2026] 星图 / starmap（*$3{\red{300}}$）

直接在原图上维护操作是困难的，套路的考虑在图的反图上执行操作，这样问题转化为要求执行操作使得最终图上边的数量最少。

光轨数量的最大值

为了方便计算，该部分的讨论都将在原图的补图上进行。

考虑从奇偶性的方向入手。注意到若一次恰好可以选择 $k$ 个点并对其执行操作，则 $k=2$ 需要单独讨论。当 $k>2$ 时：

• $k\equiv 0\pmod 4$，此时点的度数的奇偶性不会发生变化，但边的数量的奇偶性会发生变化，因此此时最少剩下的边的数量即为 $[2\nmid m]$。
• $k\equiv 1\pmod 4$，此时点的度数的奇偶性会发生变化，且边的数量的奇偶性也会发生变化。此时需要进一步分类讨论：
  • 若 $[2\mid m]=[2\mid\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2]$，则此时显然可以在不改变奇偶性的前提下把边数删到答案下界 $\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2$。
  • 否则：
    • 若图上所有点的度数都为偶数，则此时最小可以达到的答案是 $3$。
    • 若图上存在点的度数是奇数，则此时最小可以达到的答案为 $\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2+1$。
• $k\equiv 2\pmod 4$，此时点的度数的奇偶性不会发生变化，且边的数量的奇偶性也不会发生变化，因此此时最少剩下的边的数量即为 $0$。
• $k\equiv 3\pmod 4$，此时点的度数的奇偶性会发生变化，但边的数量的奇偶性不会发生变化。最后剩下的边一定是若干个奇数度数的点两两匹配，答案即为 $\frac{\sum\limits_{i=1}^n[2\nmid\deg_i]}2$。

而 $k=2$ 显然是简单的，必然可以在补图上删空所有的边。

最后用总数 $\frac{n(n-1)}2$ 减去上面得到的答案就可以得到最终结果。

构造流程

考虑先从特殊情况入手：

0x01 $k=2$

显然每次操作一条被连起来的边就可以删除该边。

0x02 $k=3$

此时操作形如每次反转一个三元环。容易想到先简单消去图上所有的环，得到一个森林。

然后对于森林上每一个非单独结点组成的树结构，均可以通过下面的操作让该树最终剩下恰好一条边：

• 选择三个点 $u,v,w$ 满足当前树上存在一条 $u\leftrightarrow v\leftrightarrow w$ 的链。
• 对 $u,v,w$ 三个点做一次操作，此时 $v$ 点脱离树结构成为单独点，$u,w$ 两点之间连了一条边。

容易发现这样恰好可以取到前面分析 $k=2$ 部分的答案下界，因此该构造方案可以证明为最优解。

---

剩下 $k>3$ 的情况。此时考虑先讨论如何构造出简单结构的操作：

0x11 长度为 $4$ 的环

考虑类比 P9841 的套路，通过调用若干次操作得到一个比较简单的操作形式。

考虑执行下面的 $4$ 次操作：

• Step $1$：$x_1,x_2,\ldots,x_{k-2},i,j$
• Step $2$：$x_1,x_2,\ldots,x_{k-2},j,k$
• Step $3$：$x_1,x_2,\ldots,x_{k-2},k,p$
• Step $4$：$x_1,x_2,\ldots,x_{k-2},p,i$

执行上面的 $4$ 次操作后，$x_1,x_2,\ldots,x_{k-2}$ 每个点都和 $x$ 内其余点边的关系发生了 $4$ 次反转（即没有发生变化），和 $i,j,k,p$ 四个点的边的关系发生了 $2$ 次反转（即没有发生变化）。而 $i\leftrightarrow j,j\leftrightarrow k,k\leftrightarrow p,p\leftrightarrow i$ 四条边则恰好被反转了一次（即发生了变化）。

0x12 长度为 $n$ 个点的环（$2\mid n$）

这里为了简化操作，定义一个长度为 $n$ 的点的环形如：

• 对于任意整数 $i$ 满足 $1\le i<n$，$i,i+1$ 两点之间都有一条边。
• $1,n$ 两点间有一条边。

考虑分类讨论，考虑下面的策略：

• 选择 $1,2,3,4$ 四个点执行 $K_4$ 的操作，这样 $2,3$ 两个点可以单独脱离环，然后 $1,4$ 两个点会多出一条连边，得到形如 $1-4-5-6-\ldots-n-1$ 的环。这个操作可以每次从环上单独分离出两个点。
• 重复执行上述操作直到环上点数量 $\le 4$ 为止。

此时因为 $2\mid n$ 所以最终会获得一个长度为 $4$ 的环，直接执行一次上面给出的操作就可以把所有点全部分离，最终剩余 $0$ 条边。

0x13 $u\leftrightarrow v\leftrightarrow w$ 的链（$2\mid k$）

目标是在图中反转 $u\leftrightarrow v,v\leftrightarrow w$ 两条边。考虑先执行下面的操作：

• Step $1$：$x_1,x_2,\ldots,x_{k-2},u,v$
• Step $2$：$x_1,x_2,\ldots,x_{k-2},v,w$

此时 $u\leftrightarrow v,v\leftrightarrow w$ 两条边都被反转了，但是此时还额外反转了 $u\leftrightarrow x_i,v\leftrightarrow x_i$（$1\le i\le k-2$）这两类边。问题转为再反转一次 $u\leftrightarrow x_i,v\leftrightarrow x_i$ 的边。

此时通过 $2\mid k$ 可以推导出 $2\mid k-2$。因此考虑把 $k-2$ 个点分成 $\frac k2-1$ 组，第 $i$ 组点是 $(x_{2i-1},x_{2i})$。然后考虑使用一开始的“长度为 $4$ 的环”操作，第 $i$ 次操作反转 $(u,x_{2i}-1,v,x_{2i})$ 四个点组成的四元环，这样每条多余的边都恰好被反转了一次。最终被反转的边就是 $u\leftrightarrow v$ 和 $v\leftrightarrow w$。

0x14 $(u,v),(u,w),(v,w),(i,j),(i,k),(j,k)$ 六条边（两个 $K_3$）

考虑执行下面的操作：

• Step $1$：$x_1,x_2,\ldots,x_{k-2},u,v$
• Step $2$：$x_1,x_2,\ldots,x_{k-2},u,w$
• Step $3$：$x_1,x_2,\ldots,x_{k-2},v,w$

此时 $u\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w$ 三条边均被反转。但是同时 $x_i\leftrightarrow x_j$（$1\le i<j\le n$）这条边也被反转了。但是注意到现在想要构造的操作其实可以看作是两个 $K_3$ 拼凑起来，现在 $u\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w$ 这三条边已经得到了一个 $K_3$，而反转具有自反性，因此可以考虑再将上面的操作执行一次得到第二个 $K_3$ 并消去所有额外的边：

• Step $4$：$x_1,x_2,\ldots,x_{k-2},i,j$
• Step $5$：$x_1,x_2,\ldots,x_{k-2},i,k$
• Step $6$：$x_1,x_2,\ldots,x_{k-2},j,k$

此时所有 $x_i\leftrightarrow x_j$（$1\le i<j\le n$）都又一次被反转了，因此两个反转操作被抵消掉。而此时 $i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k$ 三条边则同样被反转一次。因此最后 $u\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w,i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k$ 这六条边恰好分别被反转一次，其余边均未被反转，也就是反转了两个 $K_3$ 形态的子图。

注意到此时有 $k-2$ 个辅助点，加上 $6$ 个需要反转操作的点一共需要使用 $k-2+4=k+4$ 个点，因此只有 $k+4\le n$ 即 $k\le n-4$ 时才可以使用该操作。

0x15 $(u,v),(u,w),(v,w),(w,i),(w,j),(i,j)$ 六条边

和 0x14 部分本质相同，此时只需要 $k\le n-3$ 就可以执行该操作。

其实这个地方是可以和 $k$ 的取值无关的！其实利用 0x11 中给出的反转四元环操作就可以生成出该操作：

• Step $1$：用 0x11 给出的操作反转 $u,v,i,j$ 四个点组成的四元环。
• Step $2$：用 0x11 给出的操作反转 $u,w,v,i$ 四个点组成的四元环。

容易发现此时恰好反转了 $u\leftrightarrow v,v\leftrightarrow w,u\leftrightarrow w,w\leftrightarrow i,w\leftrightarrow j,i\leftrightarrow j$ 六条边。

该结构的最大优势是处理 $2\nmid k$ 的情况。

解决原问题

0x21 把原图化为特殊形态

前面已经特判掉了 $k\le 3$ 的情况，因此本部分只需要解决 $k>3$ 即可。

此时考虑先从图中找出三个关键点 $i,j,k$，并对图进行一些操作，使得图上所有二元组 $(x,y)$ 若满足不存在 $x\leftrightarrow y$ 的边，则这样的二元组 $(x,y)$ 必然还满足下面两条之一：

• $x=i,y=j$ 或 $x=j,y=i$
• $x=k$ 或 $y=k$

下面考虑如何执行操作可以得到这种图。考虑执行下面的操作：

• 对于每两个点 $x,y$ 满足 $x\neq i,x\neq j,y\neq i,y\neq j,x\neq y$，若图上当前没有连接 $x,y$ 两个点的边，则考虑继续分类讨论（$1$）：
  • 若图上存在点 $z$ 满足 $z\neq a,z\neq b,z\neq x,z\neq y$ 且 $x$ 和 $z$ 之间不存在边相连，则反转 $z,x,y,i$ 四个点组成的四元环。
  • 否则，若图上存在点 $z$ 满足 $z\neq a,z\neq b,z\neq x,z\neq y$ 且 $y$ 和 $z$ 不存在边相连，则反转 $x,y,z,i$ 四个点组成的四元环。
  • 否则，直接反转 $x,y,i,j$ 四个点组成的四元环。
• 对于每个点 $x$ 满足 $x\neq i,x\neq j,x\neq k$，考虑分类讨论 $x$ 和 $i,j$ 两点的连边关系（$2$）：
  • 若 $x$ 和 $i,j$ 两点都连了边，则不进行任何处理。
  • 否则，若 $x$ 和 $i,j$ 两点都没有连边，则对 $i,x,j,k$ 四个点执行一次 0x11 给出的操作即可。
  • 否则，若 $x$ 和 $i$ 没有连边，则对 $i,x,k,j$ 四个点执行一次 0x11 给出的操作即可。
  • 否则（即只有 $x$ 和 $j$ 没有连边），则对 $j,x,k,i$ 四个点执行一次 0x11 给出的操作即可。

现在理性的分析一下上面给出的流程都干了什么事。这里为了方便描述，将上述流程分为 $1,2$ 两个部分分别处理。

对于流程 $1$ 而言：每一次都把端点不为 $x,y$ 的不存在的边连接，并删除了对应的以 $x,y$ 为端点的边。在该流程结束后对于所有不存在连边的 $x,y$ 都有 $i=x$ 或 $i=y$ 或 $j=x$ 或 $j=y$。

对于流程 $2$ 而言：对于原来可能存在的不存在的边 $(x,i),(x,j)$ 进行一次包含其的四元环操作后，$(x,i),(x,j)$ 之间的边会被连上，而被删除的边一定形如 $(x,k),(i,j),(i,k),(j,k)$ 中的一类。

此时显然可以达成该部分想要达成的目标。

---

考虑回到问题的开始。在这片题解的最初通过对 $k\bmod 4$ 的值分类讨论得到了答案的上界，下面考虑继续对 $k\bmod 4$ 的值分类讨论并给出最终的构造方案（顺便也证明可以取到答案上界）。

0x22 $k\equiv 2\pmod 4$

从最简单的情况入手讨论。

此时既没有边数量奇偶性的约束条件，也没有点度数的奇偶性约束条件。

这里先考虑没有被连的边的数量是偶数的情况。

考虑在 0x21 部分中找出三个关键点 $i,j,k$ 后，先将 $i,j$ 两个点连起来（直接用 0x13 操作反转 $i\leftrightarrow j,j\leftrightarrow k$ 两条边即可）。

此时所有二元组 $(x,y)$ 满足 $x,y$ 之间没有边相连当且仅当 $x=k$ 或 $y=k$。因为此时没有连的边的数量是偶数所以直接给所有没有连的边另一端点两两分组匹配然后用 0x13 操作反转两条边即可。

而如果没有被连的边的数量是奇数，则在 0x21 修改图的形态之前，直接随便选 $k$ 个点执行一次操作即可（容易发现 0x21 部分不会修改边的数量的奇偶性）。

0x23 $k\equiv 0\pmod 4$

其实和 0x22 没有本质区别？

把 0x22 里第一步调整没有被连的边的奇偶性那一步删掉，后面的部分完全是一样的。

0x24 $k\equiv 3\pmod 4$

这里先考虑没有被连的边的数量是偶数的情况。

考虑在 0x21 部分中找出三个关键点 $i,j,k$ 后，先将 $i,j$ 两个点连起来（直接用 0x13 操作反转 $i\leftrightarrow j,j\leftrightarrow k$ 两条边即可）。

此时所有二元组 $(x,y)$ 满足 $x,y$ 之间没有边相连当且仅当 $x=k$ 或 $y=k$。因为此时没有连的边的数量是偶数所以直接给所有没有连的边另一端点两两分组匹配然后用 0x13 操作反转两条边即可。

但是此时仍然没有达到答案的下界，需要进一步进行操作：

• 若存在四个点 $x,y,z,w$ 满足 $x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow k,w\leftrightarrow k$ 四条边都不在图中存在，那么用前面 0x15 的操作反转 $k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,k\leftrightarrow w,x\leftrightarrow y,z\leftrightarrow w$ 这六条边。
• 此时，若 $x,y$ 两点还满足 $x\leftrightarrow k,y\leftrightarrow k$ 两条边都不存在，且 $i,j,k$ 三个点得到的三条边只有不超过一条边存在，那么用前面 0x15 的操作反转 $k\leftrightarrow i,k\leftrightarrow j,k\leftrightarrow x,k\leftrightarrow y,i\leftrightarrow j,x\leftrightarrow y$ 这六条边即可。

这一步操作可以尽可能的减少图上任意一点 $x$ 和选出的关键点 $k$ 之间不存在边的 $x$ 的数目。但是此时出现了两端点都不是 $k$ 的边不存在的情况，因此还需要再打一次补丁。考虑观察此时图的性质，容易发现此时图上边的数量一定为偶数条，且用上述方法两端点都不为 $k$ 的不存在的边的数量一定是偶数。因此考虑再执行下面的操作：

• 若对于图上的结点 $x$，$i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,x\leftrightarrow k$ 四条边都没有连，那么考虑找出 $x,i,j,k$ 之外的任意一点 $y$。
• 此时考虑用操作 0x15 来反转 $i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,k\leftrightarrow x,k\leftrightarrow y,x\leftrightarrow y$ 六条边（即补齐 $i,j,k$ 三角形上的边以及一条 $k$ 连向外部的边）。
• 若此时 $i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,x\leftrightarrow y$ 四条边都没有连，则用操作 0x15 来反转 $i\leftrightarrow j,i\leftrightarrow k,j\leftrightarrow k,k\leftrightarrow x,k\leftrightarrow y,x\leftrightarrow y$ 六条边（即补齐 $i,j,k$ 三角形上的边以及一条在 $i,j,k$ 以外的边）。
• 此时再找出点 $w$ 满足 $w\neq i,w\neq j,w\neq k,w\neq x,w\neq y$，则若此时 $i\leftrightarrow k,x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow k$ 四条边都没有连，则用操作 0x15 来反转 $i\leftrightarrow k,i\leftrightarrow x,k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,y\leftrightarrow z$ 六条边（即补齐 $i,k$ 两点之间的边以及 $k$ 外面挂着的三条缺失的边）。
• 若此时 $j\leftrightarrow k,x\leftrightarrow k,y\leftrightarrow k,z\leftrightarrow k$ 四条边都没有连，则用操作 0x15 来反转 $j\leftrightarrow k,j\leftrightarrow x,k\leftrightarrow x,k\leftrightarrow y,k\leftrightarrow z,y\leftrightarrow z$ 六条边（即补齐 $j,k$ 两点之间的边以及 $k$ 外面挂着的三条缺失的边）。

此时图上只有 $i\leftrightarrow j$ 的边，以及 $k$ 点连向除了 $i,j,k$ 以外的若干点 $x$ 的边不存在。因此考虑再打第三层补丁：

• 如果 $i\leftrightarrow j,j\leftrightarrow k,k\leftrightarrow v$ 都缺边，那么直接反转 $i,j,k,v$ 组成的四元环即可。
• 如果 $i\leftrightarrow j,i\leftrightarrow k,k\leftrightarrow v$ 都缺边，那么直接反转 $j,i,k,v$ 组成的四元环即可。

可以证明此时图的边数一定达到了上界。

---

而对于奇数的情况，同样的，考虑在 0x21 部分中找出三个关键点 $i,j,k$ 后，先将 $i,j$ 两个点连起来（直接用 0x13 操作反转 $i\leftrightarrow j,j\leftrightarrow k$ 两条边即可）。

0x25 $k\equiv 1\pmod 4$

其实和 $k\equiv 3\pmod 4$ 的情况也差不多，同样也是少了一个选前 $k$ 个点反转的操作。这里就不展开讨论了。

2026.03.14

你为寻找或是告别耗尽一生 / 也足够让人心动（周深 亲爱的旅人啊）

006. CF1734F Zeros and Ones（*$\color{pink}{2500}$）

首先有一个经典结论是 Thue-Morse 序列的第 $i$ 项的值就是 $\operatorname{parity}(i)$。因此题目中给出的询问操作其实就是问 $\sum\limits_{i=0}^{m-1}\operatorname{parity}(i\oplus(i+n))$。

记 $S(m,n)=\sum\limits_{i=0}^{m-1}\text{parity}(i\oplus(i+n))$。考虑到有 $\text{parity}(2x)=1-\text{parity}(2x+1)=\text{parity}(x)$。因此考虑按照 $n,m$ 的奇偶性分别讨论计算答案：

• $2\mid n$：记 $n=2k,m=2q+r$（$r\in\lbrace0,1\rbrace$），则有 $S(m,2k)=2S(q,k)+r\text{parity}(q\oplus(q+k))$。
• $2\nmid n$：记 $n=2k+1,m=2q+r$（$r\in\lbrace 0,1\rbrace$），则有 $S(m,2k+1)=2q-S(q,k)-S(q,k+1)+r(1-\text{parity}(q\oplus(q+k)))$。

边界条件是 $S(0,n)=S(m,0)=0$，记忆化搜索就可以做到 $O(\log^2n)$ 处理单组数据。

007. CF1626F A Random Code Problem（*$\color{red}{2800}$）

注意到位置和位置之间是相互独立的，因此考虑对每个位置分别计算其期望值。设 $f_{i,j}$ 表示当前处理的数值为 $i$，进行了 $j$ 次操作的不同方案数。转移形如：

• $f_{i,j+1}\leftarrow (n-1)f_{i,j}$
• $f_{i-i\bmod(j+1),j+1}\leftarrow f_{i,j}$

直接转移时间复杂度为 $O(kV)$，考虑进一步优化。注意到用题目中给出的操作，若对 $x$ 进行操作，则 $\frac x{\text{lcm}(1,2,\ldots,k-1)}$ 的值在整个操作过程中一定不会发生变化。因此考虑初始把所有 $a_i$ 都对 $\text{lcm}(1,2,\ldots,k-1)$ 取模，此时值域 $V$ 变为 $\text{lcm}(1,2,\ldots,k-1)$，$O(kV)$ 的时间复杂度（简单卡常后）就可以通过该题。

至于这里为什么是 $k-1$ 而不是 $k$，你会发现最后一次操作（即 $i=k$ 时）$a$ 数组的变化未被统计到 ans 内，所以不需要考虑。

008. CF1679F Formalism for Formalism（*$\color{red}{2600}$）

题意可以转化为：有多少个数不能通过题目中给出的操作使得自己的值变得比最开始更小。

然后考虑如果前一位填了 $x$，而且前面部分全都是合法的，那么后一位可以填哪些数字。假设这里填写了数字 $y$，则：

• 如果 $x,y$ 之间不能互相交换，那么很显然可以填写 $y$。
• 如果 $x,y$ 之间可以互相交换，且 $x>y$，那么很显然不能填写 $y$。
• 否则考虑交换 $x,y$ 两个位置后，$y$ 可能可以和 $x$ 之前的数继续发生交换，因此 $y$ 能填写当且仅当在 $x$ 的位置填写 $y$ 合法。

然后就可以 dp 了。设 $f_{i,j}$ 表示当前考虑了 $i$ 集合，上一次可以填写的数的集合是 $j$，有多少个合法的前缀数。转移直接枚举下一个位置填的是什么数字即可。最终时间复杂度为 $O(n\omega2^\omega)$，其中 $\omega=10$。

009. CF1623E Middle Duplication（*$\color{pink}2500$）

因为字典序比较遵循贪心原则，所以考虑直接按中序遍历来贪心处理，即一个点被复制后优先处理其左子树。

此时容易想到下面的贪心流程：

• 对于当前访问到的结点 $u$：
  • 递归访问其左子树 $l_u$。
  • 若 $l_u$ 需要被复制，则 $u$ 也同样需要被复制。
  • 否则，若 $u$ 复制后可以让答案更优，则 $u$ 同样需要被复制。
  • 若 $u$ 被复制，则递归访访问其右子树 $r_u$。

容易证明该算法的正确性。直接模拟上述流程可做到时间复杂度 $O(n)$ 解决问题。

2026.03.15

因为我刚好遇见你 / 留下足迹才美丽 / 风吹花落泪如雨 / 因为不想分离 / 因为刚好遇见你 / 留下十年的期许 / 如果再相遇 / 我想我会记得你（李玉刚 刚好遇见你）

010. CF1598F RBS（*$\color{pink}{2400}$）

好困难/ll

套路的把左括号看作是 $1$，右括号看作是 $-1$。则显然 $i$ 位置的前缀是 RBS 的充要条件是：

• 不存在 $1\le j\le i$ 满足 $j$ 位置的前缀和 $<0$。
• $i$ 位置的前缀和为 $0$。

考虑直接状压 dp，设 $f_{i,j}$ 表示当前处理了 $i$ 集合内的字符串，当前的前缀最小值是 $j$，最多有多少个 RBS 前缀。转移随便处理点东西就可以做到 $O(n2^n)$ 转移。

011. [AGC050A] AtCoder Jumper（*$\color{yellow}{2300}$）

十分 adhoc 的题目。考虑直接让 $i$ 点连 $2i$ 和 $2i+1$（以 $n$ 为单位循环标号），此时 $i$ 点走 $10$ 条边之后可以走到 $[1024i,1024i+1024)$ 范围内的点，显然覆盖了 $1\sim n$ 内的所有点。

直接模拟上述流程可以做到时间复杂度 $O(n)$ 处理问题。

012. CF1614D1 Divan and Kostomuksha (hard version) / CF1614D2 Divan and Kostomuksha (hard version)（*$\color{orange}{2100}$ / *$\color{pink}{2400}$）

先考虑 D1 怎么做。容易想到记 $buc_i$ 表示 $a$ 序列中有多少个数是 $i$ 的倍数（可以写一个埃筛 $O(n\log n)$ 求出），然后记 $f_i$ 表示当前序列的 $\gcd$ 为 $i$，所有前缀的 $\gcd$ 的和最大是多少。看上去没有记录当前选择了多少个数不好处理，但是注意到处理 $f_i$ 的时候把所有 $i$ 的倍数加到序列里的贡献都是 $i$ 且不会对序列的 $\gcd$ 产生影响，而再往后加的话序列的 $\gcd$ 值一定会变小，加入 $i$ 对答案的贡献也同样会减小，因此计算 $f_i$ 的时候一定需要把所有 $i$ 的倍数全都加入到序列里。

因此可以想到初始条件为 $f_i=i\times buc_i$，转移方程为 $f_i\leftarrow f_{ij}+i(buc_i-buc_{ij})$（$buc_i-buc_{ij}$ 即为当前为 $i$ 的倍数且没有被加入到序列中的元素的数量）。转移的时候枚举 $i$ 的倍数可以做到 $O(V\log V)$，能够通过 D1。

此时注意到转移时一个决策 $i\leftarrow ij$ 可能成为不可被替代的最优解当且仅当 $j$ 是质数，因此考虑先筛出 $1\sim V$ 内所有的质数然后转移的时候只转移质数 $j$ 的 dp 值。而处理 $buc$ 数组时可以套用 Dirichlet 前缀和的技巧做到 $O(V\log\log V)$ 计算。因此总时间复杂度为 $O(V\log\log V)$，简单卡常即可通过 D2。

2026.03.16

泛红的双眼 / 对你的爱怎么遮掩
再靠近多些 / 望着你的背影默念
敏感又热烈 / 只想霸占你的世界
我可以付出一切代价

（王澳楠 请和这样的我恋爱吧）

013. CF1582G Kuzya and Homework（*$\color{red}{2600}$）

考虑把每个数都分解质因数来统计。枚举右端点 $r$，然后维护一个栈 $stk$ 表示当前有哪些左端点是合法的，$S_i$ 表示若只考虑质因数为 $i$ 的部分有哪些左端点是合法的。则此时若 $i$ 位置对应的字符是 *，直接把 $i$ 加入 $S_j$ 和 $stk$ 中即可，否则在 $S_j$ 和 $stk$ 中把 $i$ 对应的质因数抵消掉。统计结束后栈 $stk$ 内的元素数量即为右端点为 $r$ 的合法区间数量。

线性筛出 $\text{spf}_i$ 表示 $i$ 的最小质因数可以做到 $O(n\log V)$ 时间复杂度解决问题。

014. P3644 [APIO2015] 巴邻旁之桥（*$\color{pink}{2400}$）

注意到 $k\in\lbrace 1,2\rbrace$（现在你已经做完了这个题最难的地方），因此猜测是直接分两类讨论。

$k=1$

可以把问题转化为：找到最小的 $x$ 使得 $\sum\limits_{i=1}^n|a_i-x|+\sum\limits_{i=1}^n|b_i-x|$ 的值最小。这是经典的贪心模型，直接把 $a_i,b_i$ 合并到一个数组 $c$ 中然后升序排序，取 $x=c_n$ 即为最优解。证明直接调整法即可。

$k=2$

类比 $k=1$ 的做法，必然是建两座桥然后左半部分的走坐标的桥，右半部分的走右边的桥，因此容易想到枚举中间的分界点 $p$ 然后对两侧分别做 $k=1$ 的处理，可以简单维护有序数组做到 $O(n^2)$ 求解问题。

考虑优化时间复杂度。考虑记 $F(p)$ 为分界点为 $p$ 时的答案，但是 $F(p)$ 看上去没有单调单峰等性质。一个想法是直接对 $F(p)$ 跑模拟退火（我不知道这个能不能过）。注意到其实不需要真的维护两个有序数组，只需要得知两个数组的中位数值即可，因此考虑从左到右扫描所有本质不同的位置 $p$ 然后对两个集合做单点插入 / 单点删除操作，并分别维护两个集合的中位数以及 $\sum\limits_{i=1}^n|a_i-x|$ 的值（已知元素数量和数组中位数值后这个是容易维护的）。用对顶堆来维护即可做到 $O(n\log n)$ 通过该题。

015. CF1097G Vladislav and a Great Legend（*$3\color{red}{000}$）

$f(S)^k$ 看上去不太好维护，考虑经典套路斯特林反演：

$$n^k=\sum\limits_{i=0}^k S_2(k,i)\binom nii!$$

于是题目给出的式子可以化为：

$$\sum\limits_{i=0}^ki!S_2(k,i)\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}i$$

问题在于对每个 $i$ 快速计算 $\displaystyle\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}i$ 的值。

考虑这个东西的组合意义，容易发现对每个 $i$，其答案可以看作是在 $S$ 集合内点组成的虚树的点集上选 $i$ 条边的方案数。

设 $f_{i,j}$ 表示当前处理了 $i$ 为根的子树内有 $j$ 条虚树的边的方案数，转移类似于树上背包合并，时间复杂度为 $O(nk)$。统计答案的时候套路的在深度最低的结点上统计即可。实现起来细节比较多。

016. CF1592F2 Alice and Recoloring 2（*$\color{red}{2800}$）

一眼看上去这题十分神秘不可做，因此考虑逐步挖掘其性质。

性质：有用的操作其实只有 $1,4$ 两种。

证明：

对于 $2$ 操作：则可以先用一次 $1$ 操作操作掉整个左侧，然后再把不包含于她的左上角操作。这样花费的代价为 $2$，优于 $1$ 次 $2$ 操作的 $3$ 代价。$4$ 操作同理，用 $1$ 操作操作掉整个上侧然后容斥把不包含于她的左上角操作，花费的代价为 $2$，优于 $1$ 次 $3$ 操作花费的 $4$ 代价。

---

然后发现一次操作操作的是一个矩阵，看上去很麻烦，要将其变为对单点做操作。因此考虑对矩阵做二阶差分。这里重定义颜色之间的按位异或：

• 相同颜色异或，得到的颜色为 $\texttt{W}$。
• 不同颜色异或，得到的颜色为 $\texttt{B}$。

考虑将其转化为实际的数字意义，即 $\texttt{W}$ 代表 $0$，$\texttt{B}$ 代表 $1$。此时令这个差分的二维数组为 $a$，则考虑一次操作会对新的二维数组 $a$ 做怎样的修改。

• 对于一次 $1$ 操作 $(x,y)$，则只有 $(x,y)$ 一个点会取反。
• 对于一次 $4$ 操作 $(x,y)$，那么 $(x-1,y-1)$，$(x-1,m)$，$(n,y-1)$，$(n,m)$ 四个点都会被取反。

看上去一次 $4$ 操作修改的位置更多，性质或许也会更强一些？于是对其做分析。考虑同时对在同一行上的两个坐标 $(x,y_1)$ 和 $(x,y_2)$ 做一次 $4$ 操作，则此时 $(x,y_1),(n,y_1),(x,y_2),(n,y_2)$ 四个格子被取反了一次，而 $(x,m),(n,m)$ 被取反了两次（等于没变）。一共取反了 $4$ 个格子，和做 $4$ 次 $1$ 操作效果等价，花费均为 $4$。因此其实这种情况可以规避开较为复杂的 $4$ 操作去使用较为简单的 $1$ 操作替代。同一列上的两个坐标 $(x_1,y)$ 和 $(x_2,y)$ 的情况也同理。换句话说：$4$ 操作操作的任意两个位置横纵坐标必须都不相同。

可以通过类似的手段分析，得到另一个性质更为强大的结论：使用 $4$ 操作对 $(x,y)$ 做操作比用 $1$ 操作严格好，当且仅当 $(x,y),(x,m),(n,y)$ 三个格子的值都为 $1$。证明类似于上面一个步骤，如果这三个格子中存在一个格子不为 $1$ 则需要容斥一次翻转操作，即执行两次翻转，花费的代价为 $4$。而若用 $1$ 操作则只需要不超过 $3$ 的代价就可以达成目标。

分析了这么一大通，那么这个题有应该如何解决呢？考虑到（忘了哪个题）的套路，建一张二分图，把横坐标建在图的左侧，纵坐标建在图的右侧。那么做一次可能合法 $4$ 操作 $(x,y)$ 就是把左侧点 $x$ 向右侧点 $y$ 连一条边。用匈牙利算法对该图跑最大匹配，或者建立源汇用 Dinic 算法求解其网络最大流均可。时间复杂度为 $O(n^3)$ 或 $O(n^{2.5})$（$n,m$ 同阶），而且远远跑不满，所以可以通过。

017. [ARC127E] Priority Queue（*$\color{red}{2600}$）

注意到操作的是一个集合，也就是加入元素的顺序不会影响答案。因此直接钦定的加入元素时不会被删除的数和会被删除的树都是从小到大加入的，因此删除操作一定是删除最近一个加入的未被删除的的元素。

因为需要保证每次删除的数都比前面的数要大，而因为前面钦定了删除一个数，这个数必须是上一次操作刚加入的。而又因为两组序列都必须是单调递增的，因此若当前是第 $i$ 个要被删除的数，前面已经有 $j$ 个数一定不会被删除，则第 $i$ 个被删除的数的值必须严格大于 $j$。

因此考虑 dp。设 $f_{i,j}$ 表示第 $i$ 次删除操作，删除的序列最大值为 $j$，不同集合的数量。则显然有初始条件 $f_{0,0}=1$。转移枚举上一个被删除的数 $j$ 可以做到 $O(n^3)$。注意到限制条件保证了 dp 的合法状态是连续的一段，因此使用前缀和优化可以做到 $O(n^2)$ 解决问题。

2026.03.17

日记本线条随回忆见笑 / 付出我的一切却装成笑话编造 / 咽下的时光怨当初年少 / 爱没有尾声恨没有前兆

（因你而在的梦 椰蓉面包）

018. CF2204G Grid Path（*$\color{red}{2700}$）

容易想到设 $f_{k,i,j}$ 表示当前处理了前 $k$ 行的染色情况，第 $k$ 行恰好染色了 $[i,j]$ 区间内的所有格子，方案数是多少。然后注意到这个东西的转移可以用矩阵乘法优化，做到 $O(m^6\log n)$ 时间复杂度求解。

考虑继续优化。注意到关键性质：对于具有可减性的信息，$[l,r]$ 区间的信息可以被表示为 $[0,r]+[l,m-1]-[0,m-1]$。此时所有区间都形如 $[0,m-1]$ 整体的前后缀，可以用 $2m$ 个区间来表示所有区间。转移直接枚举前后缀区间然后再枚举要转移的区间 $[l,r]$ 将 $[l,r]$ 拆分成三个前后缀区间后分别按系数转移即可，同样可以用矩阵乘法优化。此时算法的时间复杂度被优化到 $O(m^3\log n)$，简单卡常后可以通过该题。

019. CF1622F Quadratic Set（*$\color{red}{2900}$）

考虑先随便构造出一个比较大的二次集。

众所周知阶乘可以被拆成若干个数的乘法的形式，因此考虑对每个数拆贡献，得到 $\prod\limits_{i=1}^ni!=\prod\limits_{i=1}^ni^{n-i+1}$。此时考虑对每个 $i$ 把平方项都拆掉。注意到 $n$ 的奇偶性会影响剩下的 $i$ 的取值，因此考虑对 $n$ 的奇偶性分类讨论：

若 $2\mid n$：此时 $\prod\limits_{i=1}^ni^{n-i+1}=2^{\frac n2}\frac n2![\prod\limits_{i=1}^{\frac n2}(2i-1)!]^2$。此时若 $4\mid n$ 则在集合中删去 $\frac n2$ 元素即可，否则（即 $n\equiv 2\pmod 4$）则在集合中删去 $2,\frac n2$ 两个元素即可。

$2\nmid n$ 时阶乘的前缀积没有这么好的性质，但是注意到此时并不需要要求删除的元素数量尽量少只需要随便找一个比较紧的下界，因此考虑直接把 $n$ 从集合中删去，此时转化为 $2\mid n$ 的情况。

于是可以得到关键结论：最优的删除策略一定不会删除超过 $3$ 个元素。

因此考虑枚举删除的元素的数量。容易发现删除 $0,1$ 个元素是容易判断的，因此此时只需要处理删除两个元素是否可行。

注意到平方这个操作看上去十分像异或，即两个质因数可以相互抵消。因此容易想到经典 trick XOR Hash，给每个质因子赋一个权值，然后预处理出 $h_i$ 表示 $i$ 的所有质因子的权值的 XOR 值。此时一个集合 $S$ 是合法的当且仅当 $\bigoplus\limits_{i\in S}h(i)=0$，因此直接把所有的 $h(i)$ 扔到 map 里然后随便维护就可以 $O(n\log n)$ 判断是否存在合法解。

020. CF1620F Bipartite Array（*$\color{red}{2800}$）

注意到若存在三元组 $(i,j,k)$ 满足 $i<j<k$ 且 $a_i>a_j>a_k$，则此时 $i,j,k$ 三个点在无向图上构成一个三元环，此时无向图一定不是二分图。若不存在任何一组这样的 $(i,j,k)$ 则此时图上不存在环，一定是二分图。

因此数组 $a$ 是二分的 的充要条件 即为序列的最长下降子序列长度不超过 $2$。此时直接 dp 可以做到 $O(n^3)$ 时间复杂度解决问题。

考虑使用 Dilworth 定理，若一个序列的最长下降子序列长度为 $d$，则其最少可以被划分为 $d$ 个不下降子序列（若数组元素互不相同则可以被划分为 $d$ 个上升子序列）。因此序列的最长下降子序列长度不超过 $2$ 一条件可以被转化为 $a$ 可以被划分为两个上升子序列。

此时可以设 $f_{k,i,j,0/1,0/1}$ 表示当前处理了前 $k$ 个元素，其中第一个上升子序列最后一个元素位置是 $i$，第二个上升子序列最后一个元素位置是 $j$，$a_i$ 没有取反 / 取反，$a_j$ 没有取反 / 取反是否存在这样的序列。看上去时间复杂度仍然为 $O(n^3)$。此时考虑用染色的 trick，有 $\max(i,j)=k$，因此此时只处理 $i,j$ 两个维度可以做到 $O(n^2)$。然后套路的判定性问题把一维信息压到答案里变成最优化问题可以做到 $O(n)$ 解决。

2026.03.18

我吹过你吹过的晚风
那我们算不算 相拥
可如梦初醒般的两手空空
心也空
我吹过你吹过的晚风
是否看过同样 风景
像扰乱时差留在错位时空
终是空 是空

（艾辰 错位时空）

021. CF1613F Tree Coloring（*$\color{red}{2600}$）

考虑直接容斥计算。记有至少 $i$ 个点不满足条件的答案为 $f_i$，则容斥可得最后的答案即为 $\sum\limits_{i=0}^n(-1)^if_i$。而因为点和点的权值互不相同，因此一个点最多只有一个儿子可以不合法。此时套路的把每个点写成一个多项式的形式那么就可以得到 $f_i=[x^i](|\text{son}_i|x+1)(n-i)!$（可以看作是，先钦定 $i$ 个点一定不合法，剩下的 $n-i$ 个点的值随便填），分治 NTT 把多项式乘起来即可做到 $O(n\log^2n)$ 求解答案。

022. CF1612G Max Sum Array（*$\color{pink}{2500}$）

容易发现原式的值即为：$\sum\limits_{i=1}^m\sum\limits_{j=1}^{c_i}(2j-c_i-1)x_{i,j}$，其中 $x_{i,j}$ 表示值为 $i$ 的第 $j$ 个数的位置，要求所有 $x_{i,j}$ 恰好不重不漏的取完 $1\sim\sum\limits_{i=1}^mc_i$ 内的所有整数。此时容易想到直接贪心，把所有位置按照对应的系数 $2j-c_i-1$ 从大到小排序然后依次对应从大到小 $\sum\limits_{i=1}^mc_i\sim 1$ 内的所有数，容易证明这个贪心策略最优。

第二问也是容易的，发现为了保证上式的值最大，肯定不会交换两个系数不同的数的 $x_{i,j}$ 的值，因此直接求出每个数都出现了几次然后把出现次数的阶乘乘起来即可。

但是直接模拟上述流程时间复杂度为 $O(\sum c_i)$（排序可以写桶排优化到 $O(n+V)$），无法通过。注意到值域很小，所以直接差分加前缀和求出每个系数的出现次数，然后在值域上双指针扫描即可将时间复杂度优化到 $O(n)$。

2026.03.19

夏天的风我永远记得
清清楚楚地说你爱我
我看见你酷酷的笑容
也有腼腆的时候
夏天的风正暖暖吹过
穿过头发穿过耳朵
你和我的夏天风轻轻说着

（温岚 夏天的风）

023. CF1379E Inverse Genealogy（*$\color{red}{2800}$）

容易发现 $n$ 为偶数的时候一定无解。而 $n$ 为奇数时，特判 $n=1$，最多可以构造 $\frac{n-3}2$ 个不平衡点，构造方案就直接构造一条链然后给每个点再插一个儿子得到一个毛毛虫树即可。即：$i,i+1$ 点的子女结点为 $i-2$ 结点。

因此考虑在 $k$ 取在上界以内的时候先构造一个 $2k+3$ 个点有 $k$ 个不平衡点的树，然后把最底下的一个有 $3$ 个结点的子树扩建成一个完全二叉树。此时最多会新增一个不平衡点。这个时候把编号为 $1,3$ 两个点的部分扔掉（此时减少了一个不平衡点）然后把这两个点放在一个不会改变不平衡点数量的地方即可。

corner case 是 $n=9,k=2$。此时不存在合法解，$k<2$ 的特殊情况需要单独处理。

024. CF1830D Mex Tree（*$\color{red}{2800}$）

因为 $01$ 序列的 $\text{mex}$ 值只有 $0,1,2$ 三种不同取值，所以考虑然后 dp：设 $f_{i,j,0/1}$ 表示当前处理了 $i$ 点为根的子树内的信息，$i$ 所对应的同色连通块的大小为 $j$，$i$ 点写的数字是 $0/1$，答案最少减少了多少。那么显然有下面的转移：

• $f_{u,i,0}\leftarrow \min(f_{v,j,1}+f_{u,i,0},f_{v,i-j,0}+f_{u,j,0}+ij-i^2)$
• $f_{u,i,1}\leftarrow \min(f_{v,j,0}+f_{u,i,1},f_{v,i-j,1}+f_{u,j,1}+2(ij-i^2))$

直接转移看上去时间复杂度为 $O(n^3)$，但可以考虑这样的一个策略：直接对树做黑白染色，容易证明该贪心策略答案减少的数量即为 $n+\sum\limits_{i=1}^n[col_i=1]\le 2n$ 也就是 $O(n)$ 级别的，而 dp 转移过程中枚举的同色连通块大小 $j$ 对答案的减小是 $O(j^2)$ 级别的，因此枚举的连通块大小只需要到 $O(\sqrt n)$ 级别即可。

剩下部分的转移其实可以看作是一个树上背包的形式，枚举连通块大小只枚举到子树大小即可保证时间复杂度为 $O(n\sqrt n)$，可以通过该题。

2026.03.20

如果在噩梦中睁眼 直面着残忍的世界
风拨动了谁的心弦 留恋却来不及告别
如果结局仅剩惨烈 无惧在逆风中破茧
就算那羽翼被撕裂 重回到十九层深渊

（张韶涵 破茧）

025. CF1545C AquaMoon and Permutations（*$\color{red}{2800}$）

很神秘的题，首先可以证明必然存在合法解。考虑到若某一列上一个数字只出现了一次，那么为了保证最后得到的矩阵是一个拉丁方，这个位置对应的一行排列必须被选择。此时其余和当前被选中排列有至少一位相同的排列都必须被删除。

因为前 $n$ 行的矩阵恰好构成了一个拉丁方，因此通过上面的方式删除一个位置必然一次至少删除两行的排列。此时每一列上的数字都至少出现了两次，根据鸽巢原理可知每一列的数字都必须恰好出现两次才能满足条件。此时对于剩下的排列（只保留未删除的数字），不论是你选出来的矩阵还是剩下未被选的矩阵都是一个拉丁方。

此时考虑套路的对关系建图，考虑对每一列上出现的两个相同值的行编号连双向边，可以证明得到的图一定是二分图。因为一条边连接的两行不能同时被选择，因此对二分图的每个连通块，选择行的方案数都是 $2$。因此设二分图有 $k$ 个连通块，答案即为 $2^k$。

直接按照上述过程模拟时间复杂度为 $O(n^3)$，感觉应该可以用 ds 优化到 $O(n^2\log n)$ 但是没啥必要（

注意到本题只需要计数二分图内连通块的数量即可求出答案，因此实际写的时候可以不显式建出二分图，直接每次删掉一个排列然后再删掉所有和当前排列有关联的排列即可。

026. CF1404D Game of Pairs（*$\color{red}{2800}$）

考虑先写个暴力 dfs 程序打表，可以发现下面的关键结论：

• 若 $n$ 是偶数，则先手必胜。
• 若 $n$ 是奇数，则后手必胜。

下面考虑证明结论：

$2\mid n$

打表可以发现先手把 $i,i+n$ 两个元素分为一组，此时后手无论在第 $i$ 组里选择 $i$ 还是 $i+n$，其在对 $n$ 取模意义下都相当于是增加了 $i$。而 $\sum\limits_{i=0}^{n-1}i=\frac{n(n-1)}2=\frac{n^2-n}2\not\equiv 0\pmod n$，因此模 $2n$ 显然也无法整除，也就是无论后手怎么操作，先手都是必胜。

$2\nmid n$

可能是一个不太一样的角度？考虑到 $2n$ 个数中 $\bmod\ n$ 值为 $0,1,2,\ldots,n-1$ 的数都恰好有 $2$ 个，因此一旦后手存在一种方案恰好选取了 $\bmod\ n$ 值为 $0,1,2,\ldots,n-1$ 的数各一个，则这些数的和 $\bmod\ n$ 一定为 $0$。又因为此时所有数的和 $\bmod\ 2n$ 的值一定为 $n$，因此若这样的方案 $\bmod\ 2n$ 的值为 $n$，则选剩下所有没被选的数即可使得和 $\bmod\ 2n$ 的值为 $0$。

然后考虑证明无论先手怎么给元素分组，后手都可以给出一个这样的策略：

设当前组两个元素的值为 $(i,j)$，则：

• 若 $i\equiv j\pmod n$，则选哪一个元素都不会影响 $\bmod\ n$ 的值，直接忽略。
• 否则，给每一组的元素 $\bmod\ n$ 的值之间连一条边，则图一定由若干个不相交的简单环组成。考虑找到连接 $i\bmod n$ 和 $j\bmod n$ 两个元素的值，则顺着这个环绕一圈每一次选择相同方向的端点一定能恰好取遍环上所有 $\bmod\ n$ 的值。

因此可以证明此时后手一定存在一组恰好取完值 $\bmod\ n$ 后为 $0,1,2,\ldots,n-1$ 的方案，此时后手一定可以胜利。

027. CF850D Tournament Construction（*$\color{red}2800$）

感觉知道 Landau 定理之后就很简单（）

前置知识

Landau 定理：一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$ 是竞赛图每点出度从小到大排列的序列，当且仅当下面两个条件同时满足：

• $\sum\limits_{i=1}^n a_i=\frac{n(n-1)}2$
• $\sum\limits_{i=1}^j a_i\ge\frac{j(j-1)}2$（$1\le j\le n$）

题解

对 $n$ 个点的竞赛图，记 $\deg_i$ 表示 $i$ 点的出度大小，则图上边的数量即为 $\sum\limits_{i=1}^n\deg_i=\frac{n(n-1)}2$。因为题目的数据范围中保证了图上边的总数量不超过 $30n$，解不等式可得 $n\le 61$ 一定可以满足条件。

因此考虑直接 dp：设 $f_{i,j,k}$ 表示当前处理到了 $i$ 号点，当前点的数量为 $j$，边的数量为 $k$，是否合法。转移直接枚举 $i$ 号点增加的边的数量即可，构造方案在 dp 过程中记录转移路径然后利用 Landau 定理随便构造即可。

总时间复杂度为 $O(n^5)$，但是跑不满所以可以通过。

028. P15555 [CCPC 2025 哈尔滨站] 比赛（*$3\color{red}{400}$）

难度评的比较高主要是因为 KTT 这个 ds 太冷门了（）oi wiki 上甚至都没有介绍（）

很牛的题。这个 $k$ 的限制看上去就很不舒服，考虑先处理 $k=1$ 的情况。

此时 $O(nq)$ 的暴力是容易的。考虑对每次询问直接暴力 dp 处理，dp 限制内部考虑贪心，显然对于位置 $i$ 而言，在保证合法的情况下 $x_i$ 的值越小越好。因此设 $f_i$ 表示当前处理了 $L_i\sim i$ 的人，$x_i$ 的值最小是多少。显然有初始条件 $f_{L_i} = l_{L_i}$，转移方程 $f_i=\max(f_{i-1}+d,l_i)$。此时合法的充要条件即为 $\forall i\in[L_i,R_i]\cap\mathbb N,f_i\le r_i$。

因为每次询问会单独给出一个 $d$ 所以上面的 dp 无法直接上 ddp 维护。因此考虑套路的展开 dp 方程式，得到：$f_i=\max\limits_{j=L}^i\max(l_j+d(i-j))$，因此可行性条件可以看作是对每个 $i\in[L,R]$ 都有 $\forall j\in[L,i),l_j+d(i-j)\le r_j$，移项可得有 $\max\limits_{j=L}^{i-1}(l_j+d(i-j)-r_j)\le 0$，套路的分离参数把 $i,j$ 的项分开考虑得到 $\max\limits_{j=L}^{i-1}[(l_j-jd)-(r_i-id)]\le 0$。为了让里面这个东西的值最大，容易想到在左侧取一个 $j$ 满足 $l_j-jd$ 的值最大，右侧取一个 $i$ 满足 $r_i-id$ 的值最小（显然需要满足 $L\le j<i\le R$）。

考虑用一个黑盒 ds 来维护上面的信息，在该黑盒的每个结点上维护信息 $mx$ 表示在该区间上的所有 $i$ 中 $l_i-id$ 的最大值，$mi$ 表示在该区间上的所有 $i$ 中 $r_i-id$ 的最小值，$df$ 表示在该区间上所有 $i$ 的 $(l_j-jd)-(r_i-id)$ 的最大值。先不管这个 $d$ 怎么处理考虑先合并信息，那么假设此时要合并的结点左右儿子分别为 $L,R$ 两个结点，$mx,mi$ 是容易的直接取对应的 $\max$ / $\min$ 值即可，而 $df$ 则可以直接从左右儿子继承，或在 $L$ 中取 $\max$，在 $R$ 中取 $\min$，即：$df=\max(L.df,R.df,L.mx-R.mi)$。

此时考虑 $d$ 的信息怎么处理，这个东西可以看作是每次操作会先对区间的 $i$ 位置值对应增加 $id$，操作结束时刻对区间的 $i$ 位置值对应减少 $id$，也就是每次区间加 / 减一个一次函数。注意到一次操作内只有给定的询问区间 $[L,R]$ 内的数才会被考虑到其余的数都不会被考虑到，因此直接把区间加减一次函数看作是对整体做操作。然后考虑到问题没有强制在线因此考虑 P5073 的套路把所有的 $d$ 离线下来从小到大排序，此时相邻两次 $d$ 的询问可以看作是整体加斜率为两个 $d$ 的差（这个值一定 $\ge 0$）截距为 $0$ 的一次函数，因此直接上 KTT 大力维护即可（注：为了保持 KTT 的结构这里需要把最小值取反，维护最小值相反数的最大值）。

然后容易发现 $k$ 这个信息是好处理的，很显然把 $L_i,L_i+1,\ldots,R_i$ 这些人按顺序依次分配到 $1,2,3,\ldots,k,1,2,3,\ldots,k,1,\ldots$ 队内就一定是最优的，证明简单调整法即可。

总时间复杂度为 $O(nk\log^3n)$ 瓶颈在于维护 KTT。但是众所周知 KTT 十分跑不满，实际运行下来也就 $O(nk\log^2n)$ 级别，因此可以通过该题。

2026.03.21

前路漫漫 总有绕不过的弯
人生太短 悲欢自渡皆是伤
这熙攘的人潮 谁不迷惘
谁不是 在崩溃的边缘 苦求着希望
想要用魔法 解开生活的惆怅
谁不是奔跑在黑暗中 追寻微弱的光
也曾轻言过失败 也曾被冷眼相待
在最平庸的日子里 频繁受伤害

（王小帅 天真的橡皮）

029. P15502 [ICPC 2025 APC] Book Sorting（*$\color{red}{2900}$）

容易证明一定存在一个最优形态，满足存在两个位置 $1\le l\le r\le n$，使得执行的操作形如：

• 把 $l-1,l-2,\ldots,1$ 这些书按顺序移动到最左侧。
• 把 $r+1,r+2,\ldots,n$ 这些书按顺序移动到最右侧。
• $l\sim r$ 范围内的书全部相邻项交换排序。

因此贡献即为：$n-1-(r-l)+\text{inv}(a_l,a_{l+1},\ldots,a_r)$ 也就是最大化 $(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)$ 的值，其中 $\text{inv}(seq)$ 表示 $seq$ 序列的逆序对的数量。

（注：这里的 $a$ 是 $p$ 的逆排列，即 $a_{p_i}=i$）。

考虑固定右端点 $r$，记 $S_r$ 集合内存储了所有左端点 $l$ 满足 $1\le l\le r$ 且对于所有位置 $j\in(l,r]$，都有 $(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)>(r-j)-\text{inv}(a_j,a_{j+1},\ldots,a_r)$。

此时把 $S_r$ 按照左端点 $l$ 的位置从大到小排序（下标从 $1$ 开始），则有一个关键结论：$(r-S_{r,j})-\text{inv}(a_{S_{r,j}},a_{S_{r,j}+1},\ldots,a_r)=j-1$。为了方便，后面记 $(r-l)-\text{inv}(a_l,a_{l+1},\ldots,a_r)$ 的值为 $f(l,r)$。下面给出该结论的证明：

:::success[证明]
要证明的结论为：$f(S_{r,j},r)=j-1$。

套路的考虑对临项做差，得到 $f(i,r)-f(i+1,r)=1-g_i$，其中 $g_i$ 的值为 $[i+1,r]$ 中比 $a_i$ 小的元素的数量。因为 $g_i\ge 0$ 所以显然有 $f(i,r)\le f(i+1,r)+1$。

因为 $S_{r,*}$ 集合内只有对应 $f$ 值严格变大的位置，因此一定有 $f(S_{r,j},r)=f(S_{r,j-1},r)+1$。而又因为有 $f(S_{r,1}=r,r)=0$，因此 $f(S_{r,j},r)=j-1$，命题得证。
:::

因此最大化 $(r-l)-\text{inv}(a_l,a_{l+1},\ldots a_r)$ 即 $f(l,r)$ 的最大值其实就是 $\max\limits_{1\le r\le n}(|S_r|-1)$，因此只需要对每个右端点 $r$ 求出 $|S_r|$ 的值即可。

直接求 $S_r$ 是困难的，因此可以想到通过 $S_r$ 递推出 $S_{r+1}$。显然此时有 $f(r+1,r+1)=0$。若不考虑逆序对的影响则有 $f(l,r+1)=f(l,r)+1$，但是若有 $a_l>a_{r+1}$ 则 $f(1,r+1),f(2,r+1),\ldots,f(l,r+1)$ 都会受到这组逆序对的影响，导致这些 $f$ 值全部减去 $1$。

考虑维护该事件对 $S_{r+1}$ 的影响。因为在考虑逆序对影响之前有 $f(S_{r,j})=j-1$，现在对左端点 $p\in[1,l]$ 的 $p$ 对应的 $f$ 值减少 $1$，找出最大的位置 $q$ 满足 $q$ 是集合中最大的满足 $S_{r,q}\le l$ 的位置，则此时 $S_{r,1},S_{r,2},\ldots,S_{r,q-1}$ 对应的 $f$ 值不会变化，$S_{r,q},S_{r,q+1},\ldots$ 对应的 $f$ 值都会减少 $1$。因此此时只有 $S_{r,q}$ 一个位置对应的 $f$ 值不再是前缀 $\max$ 位置，在集合中二分出这个位置并将其删除即可。

容易想到用 set 来维护这个结构，每次从 $S_r$ 扩展到 $S_{r+1}$ 只需要先在集合加入 $f(r+1,r+1)$ 的影响，然后再二分出 $q$ 的位置并将 $S_{r,q}$ 从集合中删除。显然该算法流程的时间复杂度为 $O(n\log n)$，可以通过该题。

030. [ABC450G] Random Subtraction（*$\color{pink}{2400}$）

可以证明，$n>2$ 时答案一定只和 $\sum\limits_{i=1}^na_i,\sum\limits_{i=1}^na_i^2$ 有关。下面给出上述结论的证明：

::::success[证明]{open}

:::success[结论]{open}
$E[x^2]$ 一定是关于 $a_1,a_2,\ldots,a_n$ 的二次式。
:::

:::success[证明]
操作形如选择两个数 $a,b$，把这两个数删除然后再加入 $a-b$ 这个元素。因为这是一个线性操作，因此 $x$ 一定是 $a_1,a_2,\ldots,a_n$ 的一个线性组合。

因此 $x^2$ 是关于 $a_1,a_2,\ldots,a_n$ 的二次式，根据期望的线性性可知 $E[x^2]$ 同样也是二次式。
:::

因此考虑把 $E[x^2]$ 用二次式的形式表示出来，即 $\sum\limits_{i=1}^n\alpha_iA_i^2+\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j]\beta_{i,j}A_iA_j$。

但是注意到 $E[x^2]$ 的值不能因为交换 $A$ 数组中的两个位置就导致其值发生变化，因此必须有：$\alpha_1=\alpha_2=\ldots=\alpha_n,\beta_{1,2}=\beta_{1,3}=\beta_{1,4}=\ldots=\beta_{n,n-1}$。也即 $E[x^2]$ 可以表示为 $\alpha\sum\limits_{i=1}^nA_i^2+\beta\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j]A_iA_j$。

此时记 $s_1=\sum\limits_{i=1}^nA_i,s_2=\sum\limits_{i=1}^nA_i^2$
，把上式所有含 $A$ 的项都用 $s_1,s_2$ 表示，得到：$E[x^2]=\alpha s_2+\beta(s_1^2-s_2)$。
::::

此时可以直接写个暴力然后把 $\alpha,\beta$ 的值打表求出来，下面给出一个正常推导的做法。

先给数组 $A$ 代入特值，令 $A_1=A_2=\ldots=A_{n-1}=0,A_n=t$，则显然有 $E[x^2]=t^2,s_1=t,s_2=t^2$，代入前面给出的式子得到 $E[x^2]=t^2=\alpha t^2$，因此必然有 $\alpha=1$。

考虑记 $b_i$ 表示 $n=i$ 时上式 $\beta$ 的值，则 $E[x^2]=s_2+b_n(s_1^2-s_2)$。此时考虑若在某次操作中选择了 $i,j$ 两个位置，$s_2$ 的值会减少 $2A_iA_j$。因为 $E[A_iA_j]=\frac{s_1^2-s_2}{n(n-1)}$，所以有 $E[s_2]=s_2-\frac{2(s_1^2-s_2)}{n(n-1)}$。

$s_1^2-s_2$ 的值会增加 $2A_iA_j+4A_j^2-4A_js_1$，对其每项分别计算期望，得到：$E[A_j]=\frac{s_1}n,E[A_j^2]=\frac{s_2}n,E[A_iA_j]=\frac{s_1^2-s_2}{n(n-1)}$，因此有 $E[s_1^2-s_2]=s_1^2-s_2-4s_1\times\frac{s_1}n+4\times\frac{s_2}n+\frac{2(s_1^2-s_2)}{n(n-1)}$，化简可得 $E[s_1^2-s_2]=\frac{(n-2)(n-3)(s_1^2-s_2)}{n(n-1)}$。

记 $f_n(A)$ 为长度为 $n$ 的 $A$ 序列最后得到 $x^2$ 的期望值，则有 $f_1(A)=A_1^2,f_2(A)=(A_1-A_2)^2,f_n(A)=E[f_{n-1}(A')]$，其中 $A'$ 是 $A$ 序列进行一次操作后得到的序列，把 $E[x^2]$ 代入上式可得 $f_n(A)=E[s_2+b_{n-1}(s_1^2-s_2)]=s_2-\frac{2(s_1^2-s_2)}{n(n-1)}+b_{n-1}\frac{(n-2)(n-3)(s_1^2-s_2)}{n(n-1)}$。又因为 $f_n(A)=s_2+b_n(s_1^2-s_2)$，联立两个 $f_n(A)$ 的关系式可得 $b_n=-\frac2{n(n-1)}+\frac{(n-2)(n-3)b_{n-1}}{n(n-1)}$。线性求出前缀的逆元然后模拟上述过程可以做到 $O(n)$ 求解答案。

:::success[能不能 $O(1)$ 求出 $b_n$ 的值？]
先观察样例可以发现答案形如 $\frac23$ 加上一个数，然后再结合暴力打表，可以猜想 $n\ge 3$ 时有 $b_n=-\frac2{3(n-1)}$，然后简单数学归纳证明即可。
:::

:::warning[注意]
特判 $n\le 2$ 的时候一定要记得给答案平方！！！
:::

2026.03.22

那时候手心余温刚好
晚风很温柔有你陪就足够
时间是个小偷
无情盗走你我之间的所有
未留温暖又平凡的以后
你说分开也能相守
不过一个人把回忆保留
却还记得你的笑容

（yihuik苡慧 银河与星斗）

031. CF1579G Minimal Coverage（*$\color{orange}{2100}$）

有两个端点比较难受，所以考虑转化问题，找到最小的 $m$ 使得存在一个起点 $t\in [0,m]$ 使得每一步 $+a_i$ 或 $p-a_i$ 后值都在 $[0,m]$ 范围内。

显然 $m$ 是有单调性的，所以考虑二分 $m$ 的值，判定是否合法容易简单想到 $O(nm)$ 暴力背包 dp。此时总时间复杂度为 $O(nV\log V)$，其中 $V=\sum\limits_{i=1}^n a_i=O(n^2)$，即总时间复杂度为 $O(n^3\log n)$。

考虑优化。容易发现 dp 转移的形式就是对一个 $01$ 序列整体左移整体右移然后再按位与把序列框在 $[0,m]$ 范围内。因此容易想到用 bitset 简单优化做到 $O(\frac{n^3\log n}\omega)$ 求解。

但是这个时候还是过不去。考虑进一步优化，注意到答案的上界不会超过 $2\max a_i$。证明的话考虑若一个数大于 $\max a_i$ 那么下一个直接减 $a_i$ 一定不会使得上界超过 $2\max a_i$。把二分的上界改设为 $2\max a_i$ 可以做到总时间复杂度 $O(\frac{n^2\log n}\omega)$ 可以通过该题。

032. CF1768E Partial Sorting（*$\color{yellow}{2300}$）

感觉比较像 sale（？但是要简单一些

可以证明对于任意一个排列都最多只需要三次操作使得排列变得满足条件。因此考虑分别计数需要 $0,1,2,3$ 次操作可以排序的排列数量：

• 需要 $0$ 次操作的排列数量：显然答案就是 $1$。
• 需要 $1$ 次操作的排列数量：显然这次操作只能把前 $2n$ 个数排序或把后 $2n$ 个数排序，因此需要不超过 $1$ 次操作的排列数量可以被表示为前 $n$ 个数正好是 $1,2,3,\ldots,n$ 或后 $n$ 个数正好是 $2n+1,2n+2,\ldots,3n$ 的排列数量，简单容斥可得答案为 $2(2n)!-n!$。
• 需要 $2$ 次操作的排列数量：显然此时排列要么 $1\sim n$ 元素在前 $2n$ 个位置，要么 $2n****im 3n$ 元素在后 $2n$ 个位置。对于需要不超过 $2$ 次操作的排列数量，若假设两个条件互斥，则显然答案可以被计数为 $2(2n)!n!\binom{2n}n$。然后考虑容斥，计数同时满足前面给出的两个条件的排列数目。容易想到枚举出现在中间区间里数的情况。这里枚举 $i$ 表示恰好有 $i$ 个数值在 $[n+1,2n]$ 范围内出现在序列的前 $n$ 个位置。那么可以这样计数：
  • 前 $n$ 个位置里有 $i$ 个数字在 $[1,n]$ 范围内，方案数是 $n!\binom ni$。
  • 中 $n$ 个位置里有 $n-i$ 个数在 $[1,n]$ 范围内，方案数是 $n!\binom ni$。
  • 后 $n$ 个位置里有 $i$ 个数在 $[n+1,3n]$ 范围内，方案数是 $n!\binom{2n-i}n$。
• 直接乘法原理乘起来计数即可。
• 需要 $3$ 次操作的排列数量：直接用排列数量 $(3n)!$ 减去需要 $0,1,2$ 次操作的排列数量即可。

该算法总时间复杂度为 $O(n)$，可以通过该题。

2026.03.23

世界赠予我虫鸣 也赠予我雷霆
赠我弯弯一枚月 也赠予我晚星
赠我一场病 又慢慢痊愈摇风铃
赠我一场空 又渐渐填满真感情

（王菲 世界赠予我的）

033. AT_arc122_d [ARC122D] XOR Game（*$\color{pink}{2400}$）

感觉是比较套路的题？注意到问题可以转化为把 $2n$ 个数分成 $n$ 个二元组，使得每个二元组内两个数的异或的最大值最小。套路的从二进制的高位开始向低位考虑：

• 若当前位上有偶数个数二进制表示为 $1$，则显然可以贪心的两两分组使得 $1$ 和 $1$ 分组 $0$ 和 $0$ 分组，因此直接按二进制 $0,1$ 分为两组然后分别递归处理即可。
• 若当前位上有奇数个数二进制表示为 $1$，则必然需要找恰好一组数使得其中一个数二进制表示为 $1$，另一个数二进制表示为 $0$。直接贪心的找出一组异或最小的数，可以证明这个贪心策略正确。用 01-Trie 维护信息，时间复杂度为 $O(n\log V)$ 可以通过该题。

034. P6009 [USACO20JAN] Non-Decreasing Subsequences P（*$\color{red}{2600}$）

【模板】猫树分治。对于当前的分治区间 $[l,r]$ 而言：

• 若 $l=r$，则直接处理即可。
• 否则，记区间的中点为 $M$，则先分别递归处理 $[l,M]$ 和 $[M+1,r]$ 两个区间内的答案，然后套路的记 $f_{i,j}$ 表示 $[i,M]$ 区间内最后一个元素是 $j$ 的不下降子序列的数量，$g_{i,p}$ 表示 $[M+1,i]$ 区间内第一个元素是 $p$ 的不下降子序列的数量，转移直接枚举 $j,p$ 然后合并 $f,g$ 两个数组的 dp 信息即可。

总时间复杂度为 $O(nk^2\log n)$，可以通过该题。

2026.03.24

Ho baby 情话多说一点
想我就多看一眼
表现多一点点
让我能真的看见
Oh bye 少说一点
想陪你不只一天
多一点
让我心甘情愿
爱你[比心]

（王心凌 爱你）

035. Wikipedia（*$\color{red}{2600}$）

考虑套路的转化可行条件。容易发现题目给出的条件等价于：一个序列 $q$ 是合法的当且仅当删除 $q$ 序列的 $n$ 后得到的序列 $t$ 从后往前操作可以把升序排列变为 $p$。因此答案就是 $n$ 乘以能够得到排列 $p$ 的序列 $t$ 的数量。

更确切的说：记 $s_i$ 表示当前操作交换 $a_i,a_{i+1}$ 两个数，则对于长度为 $n-1$ 的排列 $t$，操作过程可以看作是：从排列 $1,2,3,\ldots,n$ 开始按顺序执行操作 $s_{t_1},s_{t_2},\ldots,s_{t_n-1}$ 并最终得到 $p$ 排列。最后答案额外乘以 $n$。

注意到若 $|i-j|>1$，则 $s_i$ 和 $s_j$ 两个操作调换顺序不会影响最后得到的排列。考虑记 $d_i$：若 $d_i=1$ 则表示 $i$ 在 $t$ 中出现在 $i+1$ 的前面，否则（$d_i=0$）表示 $i$ 在 $t$ 中出现在 $i+1$ 的后面。此时考虑把 $1,2,3,\ldots,n-1$ 看作是图上的若干结点，则若 $d_i=1$ 则连一条 $i\to i+1$ 的边，否则连一条 $i+1\to i$ 的边。则此时 $t$ 正好是这张有向图的一个拓扑序。

记 $S_1,S_2$ 两个集合为：$S_1=\lbrace i+1\mid d_i=1\rbrace,S_2=\lbrace i+1\mid d_i=0\rbrace$。则最终得到的置换 $p$ 一定存在一个循环分解形如 $1,S_1,n,S_2$ 的形式，且 $S_1$ 一定是升序排列的，$S_2$ 一定是降序排列的。

此时套路的记 $\pi$ 为 $t$ 的逆排列，则 $d$ 的限制条件形如：

• $d_i=1$：$\pi_i<\pi_{i+1}$
• $d_i=0$：$\pi_i>\pi_{i+1}$

问题变为计数有多少个长度为 $n-1$ 的排列满足上述 $d$ 对 $\pi$ 的限制。因此考虑套路的 dp：设 $f_{i,j}$ 表示当前处理了排列的前 $i$ 个元素，满足 $d$ 的前 $i-1$ 个限制，且最后一个数是这 $i$ 个数里第 $j$ 小的元素。则转移枚举下一个数的排名可以做到 $O(n^3)$。注意到转移的是一段连续的区间因此使用前缀和维护，时间复杂度优化到 $O(n^2)$ 可以通过该题。

036. AT_agc071_c [AGC071C] Orientable as Desired（*$3\color{red}{200}$）

:::info[结论 $1$]
若无向图 $G$ 是一棵树，则一定不存在这样的一个数组 $X$ 满足题目中给出的条件。
:::

:::warning[提示 $1$]
试着给树定根，然后自底向上递归处理度数信息？
:::

::::success[证明结论 $1$]
考虑先给树随便定一个根。此时很显然叶子结点可以满足条件。

:::info[结论 $1.1$]
翻转一个结点 $u$ 子树内所有边以及 $u$ 和其父结点的边的方向不会影响 $u$ 子树内除 $u$ 结点以外的所有点的合法性。
:::

:::warning[提示 $1.1$]
考虑 $u$ 子树内的结点入度和出度会怎么变化？
:::

:::success[证明 $1.1$]
翻转一个结点 $u$ 子树内所有的边后，对于 $u$ 子树内一点 $v$，若满足 $v\neq u$ 则 $v$ 点操作前后一定是恰好交换了入度和出度的值。
:::

而对于非叶子结点的限制，考虑先递归处理其所有子结点 $v$ 的子树条件，使得对于所有 $v$ 都是满足条件的。

考虑先给每个子结点 $v$ 的子树以及 $u\leftarrow v$ 的边随便定向使得 $v$ 子树内所有结点的信息都是合法的。此时若 $u$ 结点不合法，根据结论 $1.1$ 可知此时翻转 $v$ 子树内所有的边以及 $u\leftarrow v$ 的边不会导致 $v$ 子树内任意一个点不再满足度数条件，而这样会导致 $u$ 的入度和出度发生 $\pm 1$ 或 $\mp 1$ 的变化。容易发现必然存在一个调整方案使得 $u$ 满足其度数条件。
::::

:::info[结论 $2$]
若图 $G$ 不是二分图，则必然存在一个数组 $X$ 满足题目给出的条件。
:::

:::warning[提示 $2$]
试着构造一个特殊的 $X$ 数组？
:::

:::success[证明结论 $2$]
构造 $X_1=X_2=\ldots=X_n=0$。则此时要求一个点的入度或出度中至少有一个为 $0$。

也就是对于一个结点 $u$，要么和其相邻的边全都是从 $u$ 出发的，要么和其相邻的边全都是到达 $u$ 的。

考虑按照这个条件把所有点 $u$ 分为两类点：若 $u$ 点相邻的所有边均从 $u$ 出发，则称其为 $1$ 类点，否则称其为 $2$ 类点。

则根据两类点的定义可知，一条边定向后只可以是从 $1$ 类点连向 $2$ 类点的边，即在原图上只能存在连接$1$ 类点和 $2$ 类点的边，不能存在一条边连接的两个点类别相同。因此若要存在一个定向方案满足条件，则图必须是一张二分图。

因此对非二分图，构造 $X_1=0,X_2=0,\ldots,X_n=0$ 就一定不满足题目中给出的度数条件。
:::

:::warning[提示 $3$]
是否只需要研究一类特殊的 $X$ 数组就可以正确求解问题？
:::

:::info[结论 $3$]
只需要研究形如 $X_i=k,X_j=0(\forall j,j\neq i)$ 的数组 $X$ 即可。
:::

:::::success[证明结论 $3$]
先考虑若一个序列 $X$ 中只有一个位置 $X_i$ 的值可以不为 $0$，定向后得到的有向图会形如什么样。容易想到这张图除了 $i$ 结点以外，每个结点要么和其相邻的所有边都从她出发，要么和其相邻的所有点都连向她。

::::warning[提示 $3.1$]
如果翻转树上两个点 $u,v$ 的简单路径上所有边的方向，那么点度数的信息会发生怎样的变化？
::::

::::success[提示 $3.1$ 的答案]
容易发现若 $u$ 到 $v$ 路径上的点按照顺序可以写作为 $u,x_1,x_2,\ldots,x_p,v$，则 $x_1,x_2,\ldots,x_p$ 点的入度和出度都不会发生变化。而 $u,v$ 两点的入度要么增加 $1$ 要么减少 $1$，出度则刚好相反。
::::

考虑对于一个不合法的序列 $X$，记位置 $v_1,v_2,\ldots,v_k$ 满足 $X_{v_i}\neq 0$，则考虑每次选择两个非零点 $v_i,v_j$ 然后通过提示 $3.1$ 中给出的操作把 $v_i$ 上度数不为 $0$ 的部分转移到 $v_j$ 上即可。且因为这个转移操作只需要把 $i\to j$ 路径上所有边的方向翻转，因此设得到的新序列 $Y$，则 $X$ 不合法的充要条件即为 $Y$ 不合法，反之同理。
:::::

（这里只讨论 $G$ 是二分图且不是树的情况）此时特判掉 $X$ 序列全 $0$ 的特殊情况，则对于给定的图 $G$，考虑固定 $p$ 点，满足 $X_p\neq 0$。此时考虑在图 $G$ 中删除 $p$ 点以及所有一端为 $p$ 点的边，则此时：

:::info[结论 $4$]
二分图删除一个结点和该结点相邻的边后，得到的新图仍然是一张二分图。
:::

:::info[结论 $5$]
若一张二分图中所有结点对应的 $X$ 值都为 $0$，则确定一个点的入度为 $0$ / 出度为 $0$ 后，一定可以确定整个连通块内每个点入度为 $0$ / 出度为 $0$。
:::

:::success[证明结论 $5$]
确定二分图连通块内一个点入度为 $0$ / 出度为 $0$ 后，一定可以通过二分图染色的方式，使得同色的点一定同时满足入度为 $0$ / 出度为 $0$。而二分图染色确定一个点的颜色后一定可以唯一确定该点所在连通块内其余点的颜色。因此此时染色方案一定唯一，可以唯一确定。
:::

:::info[结论 $6$]
$p$ 点向同一个连通块内连的边的方向一定全部相同，即：要么全都是从 $p$ 出发，要么全都是连向 $p$ 点。
:::

:::success[证明结论 $6$]
考虑到二分图删掉若干点后仍然会得到一个二分图，而且二分图一定不存在任何奇环，而除了 $p$ 点以外的所有点都要么全是从 $p$ 出发的边，要么边全都连向 $p$ 点。考虑到前面提到过二分图染色后颜色相同的点必须全都是从 $p$ 点出发的边或者全都是连向 $p$ 点的边，因此 $p$ 点向同一个连通块内连的边的方向必然全都相同。
:::

此时考虑记 $p$ 点删除后各个连通块内和 $p$ 点有边相连的点的数量分别为 $a_1,a_2,\ldots,a_m$，则问题可以被转化为可重集合 $\lbrace a_1,a_2,\ldots,a_m\rbrace$ 中是否对于任意一个整数 $v\in[0,\sum a_i]$ 都存在一个子集 $T\subseteq S$ 满足 $\sum\limits_{i\in T}i=v$。此时考虑 P15253 Raining Mex 的经典结论：

:::info[结论 $7$]
可重集合 $\lbrace a_1,a_2,\ldots,a_m\rbrace$ 中对任意一个整数 $v\in[0,\sum a_i]$ 都存在一个子集 $T\subseteq S$ 满足 $\sum\limits_{i\in T}i=v$，当且仅当把 $a$ 数组内元素升序排序后，对任意 $i$ 都有 $\sum\limits_{j=1}^{i-1}a_j\ge a_i-1$。
:::

::::success[证明结论 $7$]
首先把 $a$ 数组内元素升序排序。此时考虑套路的数学归纳，若当前处理的一段前缀内元素恰好可以凑出 $0\sim x$ 的值，当前要加入的元素值为 $y$，则：若 $x\ge y-1$，则很显然此时可以凑出的元素的值为 $0\sim x+y$，否则此时无法凑出值在 $x****im y-1$ 的元素。但是为什么在某个时刻出现无法凑出的值，后面就再也无法凑出这些值了呢？

:::info[结论 $7.1$]
对于一个升序排列长度为 $n$ 的数组 $a$，若在某个时刻能够凑出的值不是一段连续的区间，则在之后无论怎么插入元素都不会使得能凑出的值是一段连续的区间。
:::

:::success[证明结论 $7.1$]
考虑第一次出现不是一段连续区间前，能凑出值为 $0\sim x$ 的元素，插入了元素 $y$，则必有 $x<y-1$。此时无法凑出值为 $x+1$ 的元素。而在后面加入的所有元素其值都不会小于 $y$，更不会小于 $x+1$，自然也无法凑出值为 $x+1$ 的元素。而显然能凑出元素的上界就是当前所有元素的和，而这个和显然是严格大于 $x+1$ 的。
:::

因此可以证明前面给出的条件就是充要条件。
::::

于是得到了一个时间复杂度为 $O(n^2)$ 的做法：特判掉二分图和树的情况，然后考虑枚举点 $p$ 作为序列 $X$ 中唯一的非零点，求出删除点 $p$ 后每个连通块和点 $p$ 有边相连的点的数量 $a_i$，排序（这里排序可以使用桶排）后通过结论 $7$ 判断点 $p$ 是否合法即可。显然输出 No 当且仅当对于每个 $p\in [1,n]$，$a_i$ 都可以凑出值在 $0\sim \sum a_i$ 内的元素。

考虑进一步优化该算法的时间复杂度。考虑若一个点 $p$ 不是原图的割点，则原图删掉点 $p$ 和与其相邻的所有边后仍然得到一张二分图，且图仍然是连通的。此时 $p$ 点相邻的所有点，每个点相邻的边的方向都必须是相同的，且做二分图染色后这些和 $p$ 相邻的点的颜色必然是相同的，因此这些点和 $p$ 点之间的边方向必须全部指向 $p$ 或者全部从 $p$ 出发，也就是此时因为 $a_p\neq 0$ 所以只能有 $a_p=\deg(p)$，这个情况是平凡的，无需通过上面的方法讨论。因此直接在图上求出所有的割点然后把这些点依次设为 $p$ 直接枚举和 $p$ 点相邻的每条边即可。总时间复杂度为 $O(n+m\log m)$，可以通过该题。