task12

[TOC]

1. CF1799F - Halve and Subtract [E]

题面

给定长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，你可以进行两种操作：

• 选择一个 $i$，令 $a_i\leftarrow\lceil\frac{a_i}2\rceil$
• 选择一个 $i$，令 $a_i\leftarrow\max(a_i-b,0)$

其中第一种操作只能进行 $k_1$ 次，第二种操作只能进行 $k_2$ 次，任意一个元素最多进行一次一操作和一次二操作

求操作完后 $\sum a$ 的最小值

$1\le n\le5000,1\le b\le10^9,0\le k_1,k_2\le n$

题解

Sol

考虑分析一些性质：设一个元素进行两种操作的状态为 $11/01/10/00$，那么我们将所有数从大到小排序，那么可以得到 $11$ 一定在 $01$ 前面，类似地经过一些讨论可以得到最优解一定满足 $11\rightarrow10\rightarrow01\rightarrow00$

枚举 $11$ 和 $10$ 段的长度，复杂度 $O(n^2)$

---

2. QOJ8526 - Polygon II [E]

题面

有 $n$ 个线段，第 $i$ 条线段长度是在 $(0,2^{a_i})$ 之间的随机实数，求这些线段能组成 $n$ 边形的方案数

$3\le n\le1000,0\le a_i\le50$

题解

Sol

注意到无法组成 $n$ 边形条件其实就是最大值大于等于其余的和

考虑 $a_i$ 全相等怎么做。

注意到 $P(\sum_{i=1}^{n-1}x_i\le x_n)=P(\sum_{i=1}^n x_i\le 2^{a_n})$，那么我们就相当于需要计算 $n$ 个 $(0,1)$ 内随机的变量和 $\le j$ 的概率，设其为 $A_j$

这是一个 $n$ 维体的体积，并且这很类似一个有上界的插板，因此我们考虑容斥有多少 $x_i<1$ 被满足

那么我们需要计算的就是 $x_i>0,\sum x_i<j$ 的体积，这个就是做 $n$ 次积分，也就是 $\frac1{n!}j^n$

考虑原问题，我们要计算的就是对所有 $y$，$P(\sum _{i=1}^nx_i\le 2^y)$

注意到 $(0,2^{a_i})$ 内随机可以视作 $(0,1)$ 内随机一个实数，加上每一位在 $\{0,1\}$ 内随机一个整数，那么就可以考虑数位 dp，设 $dp_{i,j}$ 表示我们已经决策了 $(0,1)$ 和前 $i-1$ 位的选法，向前进了 $j$ 位

转移是容易做到 $O(n^2a)$ 的，初值 $dp_{0,i}\leftarrow A_i-A_{i-1}$

复杂度 $O(n^2a)$

---

3. CTT2020 - 术树数 [E]

题面

给定常数 $k,m$，初始有一个只有 $1$ 号点的图，$q$ 次操作，每次操作为以下三种中的一个：

• 1 x v，加入一个新的点，连向 $x$ 点，边权为 $v$
• 2 x y v，加入一条连接 $x,y$ 的边，边权为 $v$
• 3 x y，查询 $x$ 到 $y$ 路径上权值的 $k$ 进制异或和的最小值（可以多次经过一条边，权值计算多次）

$k$ 进制异或和定义为 $k$ 进制不进位加法，数的值域为 $k^m$

$1\le q\le2\times10^5,k\ge2,k^m\le5\times10^7$

题解

Sol

线性基。

首先，注意到 $k$ 为奇数的时候答案是 $0$

否则，我们可以说明直接用每条边异或 $2$ 两次，和所有包含一条非树边的环的值，一定能表示出所有环，剩下的用常规操作处理即可

那么问题在于如何建线性基。

由于 $k$ 可能是合数，所以应该考虑辗转相除来两行互消，但是这样还有一个问题，就是我们贪心的过程中可能有不止一种选择当前行倍率的方案数

考虑先直接将其暴力插入线性基，然后进行一个线性基的“修复”操作，具体地，我们遍历从上到下遍历每一行，然后乘最小的倍率让代表位置变为 $0$，将剩下的部分插入线性基

复杂度 $O(q\log n+qm^2\log n)$

---

4. CEOI2022 - Abracadabra [S]

题面

有 $n$ 张牌，编号为 $[1,n]$，保证 $n$ 是偶数

定义如下操作为一次洗牌：

• 将牌分为两堆 $[1,n/2]$ 和 $[n/2+1,n]$，然后将这两堆归并起来（每次将两堆的开头较小的 push 到新序列中）

$q$ 次询问，一次询问给定一个 $t,x$，询问 $t$ 次洗牌后，第 $x$ 位置的牌是什么

$2\le n\le2\times10^5,1\le q\le10^6$

题解

Sol

手模一下，会发现我们可以将一个 $a_i$ 和后面一段极长的 $<a_i$ 的段缩在一起，那么操作就是对段排序

注意到每次洗牌会增加一些段（被 $n/2$ 切开的），而由于段一开始是排好序的，所以唯一需要重新考虑的只有新切出来这些段，那么用平衡树维护段，$O(\text{段数}\times\log n)$ 的复杂度将这些段插入到应该去的位置，就可以维护处一次洗牌操作

段不会合并，所以产生段最多发生 $O(n)$ 次，而一次操作如果不产生段，就没有对序列产生改变，因此我们只需要模拟 $O(n)$ 次操作，并且最多会切 $O(n)$ 次段

复杂度 $O((n+q)\log n)$

---

5. CEOI2022 - Homework [S]

题面

给定一个若干个嵌套 min 和 max 的表达式，如 max(min(?,?),min(?,?))

设问号数为 $n$，求将这些问号填入 $1\sim n$ 的排列的值之后，最后的表达式值有多少种可能

$1\le n\le10^6$

题解

Sol

一个直观的想法是所有可能的答案是输入数的一个排名区间，归纳证明是容易的

那么直接模拟即可。

复杂度 $O(n)$

---

6. CEOI2022 - Prize [S]

题面

交互题。

给定两棵 $n$ 个点的树 $T_1,T_2$，边有边权，但是你不知道，你只知道树的结构

然后给定一个常数 $k$，你需要选择 $\{1,2,\cdots,n\}$ 的一个大小为 $k$ 的子集 $S$

你选择 $S$ 之后，你可以向交互库提出不超过 $k-1$ 次询问，每次询问给出有序二元组 $(a,b)$，交互库会回答有序二元组 $(d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b))$，其中 $l_1,l_2$ 为对应树上 $a,b$ 的 $\text{LCA}$，$d_1,d_2$ 表示对应树上的距离

询问过后，交互库会向你提出 $q$ 次询问，每次询问给定 $(a,b)$，你需要回答 $(d_1(a,b),d_2(a,b))$

$n\le10^6,2\le k\le10^5,1\le q\le10^5$

题解

Sol

注意到我们关心的实际上是这 $k$ 个点虚树的每条边权

虚树最多有 $2k-2$ 条边，而我们 $k-1$ 次询问在一棵树上最多得到 $2k-2$ 条信息，所以这个限制是相当紧的

如果要得到一棵树上的 $2k-2$ 条信息，我们直接按 dfs 序询问所有点对即可，但是想将两棵树上的凑在一起非常困难

我们还没有使用选定 $k$ 个点这个条件，在 $T_1$ 上选定一个连通块，然后按 $T_2$ 的 dfn 序询问即可得到所有信息

复杂度 $O(n+k\log n)$

---

7. CEOI2022 - Measure [S]

题面

数轴上有 $n$ 个人，坐标分别为 $x_1,x_2,\cdots,x_n$

有一个常数 $D$，定义一个局面的代价为，如果想让这些人两两距离 $\ge D$，所有人需要移动的距离的最大值的最小值

$q$ 次操作，每次加入一个新的人，并给定他的坐标，在所有操作前及每次操作后，输出当前的代价

$1\le n,q\le2\times10^5$

题解

Sol

首先考虑二分，设阈值为 $M$，那么从 $i=1,2,\cdots,n$ 依次考虑，每个人一定在距离上一个人 $\ge D$ 的情况下尽可能向左走，最后的位置就是 $pos_i=\max(pos_{i-1}+D,x_i-M)$，也就是 $pos_i=\max_j(x_j-M+D(i-j))$，如果有任意 $pos_i>x_i+M$ 就失败了，也就是 $x_j-M+D(i-j)>x_i+M$，移项得 $x_j-Dj>x_i-Di+2M$，也就是说 $M\le\frac{x_j-Dj-(x_i-Di)}2$

直接用平衡树维护最大极差即可，复杂度 $O((n+q)\log n)$

---

8. CEOI2022 - Parking [S]

题面

有一个 $n$ 个大小为 $2$ 的栈，初始有一些元素，保证每种元素恰好出现两次，你可以进行如下操作：

• 取出一个栈顶的元素，然后放进另一个栈中，需要保证栈的大小不超过 $2$，且若栈中有元素则与操作的元素颜色相同

你需要使用最少的操作将每种元素都处在同一个栈中，或返回无解

$1\le n\le2\times10^5$

题解

Sol

首先将明显能合并的直接并掉，显然不会变劣

考虑什么时候无解：如果有任意多栈那么显然问题是有解的，因此无解相当于求最小使用的栈的数量

如果我们在一个元素的两个栈之间连边，按照这两个元素在栈顶的数量分为 $0/1/2$ 边

如果一个环全是 $1$ 边，那么我们可以用一个额外栈将这个环全排好

如果有一个栈只有一个元素，那么我们也可以用一个额外栈将这条链排好

否则每个环都有至少一个 $0$ 和 $2$ 边，如果只有一个 $0$ 边，那么我们也可以用一个额外栈将这个环排好

如果有至少两个 $0$ 边，那么我们可以用两个额外栈将这个环排好

模拟即可

复杂度 $O(n)$

---

9. CEOI2023 - A Light Inconvenience [E]

题面

交互题。

有一个栈，初始栈里有一个人，他手中拿着一个亮着的火把

交互库会向你提出 $q$ 次要求，要求为以下两种中的一个：

• leave(u)，表示从栈中弹出最后的 $u$ 个人
• join(u)，表示在栈中的末尾插入 $u$ 个人，这些人的火把都是灭的

每次要求之后，你需要给出一个 $t$，表示对每个火把亮着的人 $i$，他会将 $[i+1,i+t-1]$ 的人的火把都点亮，这些事件同时发生，新点亮的不会去点亮别人

然后，你需要选择一些人，将他们的火把熄灭

执行完这些操作之后，你需要保证此时栈末尾的人的火把是亮着的

你需要保证你给的 $t$ 小于等于交互库这次要求的 $u$，以及执行熄灭操作之后亮着的火把不超过 $150$ 个

$q\le50000$，任意时刻栈的大小 $\le10^{17}$

题解

Sol

join 操作之后我们显然可以让最右边的人是亮着的，考虑 leave 操作

注意到我们能满足任意操作的充要条件是任意熄灭段的长度 $\le$ 其到最右边的距离

考虑保留的时候我们直接贪心的取，从右边开始，每次保留能让条件满足的最靠左的火把，可以证明这样两段之后一定翻倍，因此最多保留 $2\log$ 个火把

---

10. CEOI2023 - Brought Down the Grading Server? [E] ⭐

题面

给定一个 $n\times S$ 的矩阵，保证 $S$ 是 $2$ 的整数次幂

你需要重排矩阵的每一行，使得对于任意数 $c$，$c$ 在矩阵每一列出现次数的极差 $\le1$，保证有解

$1\le n\times S\le5\times10^5$

题解

Sol

$S$ 是 $2$ 的次幂已经明示分治了，并且我们可以猜测题目一定有解

对于一种数，我们可以将它拆成若干整 $S$ 的颜色，和一个不足 $S$ 的颜色，不足 $S$ 的颜色在分治的时候两边分的都不超过 $\frac S2$ 即可，整 $S$ 的颜色两边都恰好分 $\frac S2$，这样两边构造出来的解一定是原题的解

考虑 $S=2$ 的情况，我们可以在相当于要同一个颜色的两个数要分属两边，那么我们对每一行的两个数建边，这就是定向问题，每一个二度点必须恰好有一个入度和出度

扩展到 $S=2^k$ 的问题的话，我们钦定每行第 $2i-1$ 个和第 $2i$ 个数分属两边，在它们之间建边，然后要求所有 $S$ 度点入度等于出度，跑欧拉回路即可

复杂度 $O(nS\log S)$

---

11. CF2018E - Complex Segments [E] ✔️

题面

定义一个区间集合 $S$ 是复杂的，当且仅当其可以被划分成若干子集，使得这些子集的大小相等，并且两个区间相交当且仅当它们处于同一个子集

给定 $n$ 个区间 $[l_i,r_i]$，求这 $n$ 个区间最大的复杂子集的大小

$1\le n\le3\times10^5,1\le l_i\le r_i\le2n$，13s

题解

Sol

考虑枚举子集的大小 $k$，然后求我们最多能划分出来多少个子集，一种贪心是按 $r$ 然后每次将区间覆盖上，如果存在一个位置被覆盖了超过 $k$ 次就选出一个段

直接用线段树维护可以得到 $O(n^2\log n)$ 的做法

优化 1

设 $res_k$ 表示子集大小为 $k$ 时的段数，那么注意到一些事情就是 $k\times res_k\le n$，并且 $res_k\ge res_{k+1}$

这意味着 $res_k$ 最多只有 $O(\sqrt n)$ 段，那么我们运行一个分治：在 $[l,r]$ 时候计算出 $res_{mid}$，如果等于 $res_l$ 或 $res_r$ 就把对应的一边跳过，否则暴力递归

可以分析出来，我们这样最多会进行 $O(\sqrt n)$ 次 $res$ 的计算

为了分析方便，我们设 $n=2^w$

那么考虑块长为 $2^d$ 的层，一共有 $2^{w-d}$ 个块，第 $2^{(w-d)/2}$ 块之后的 $k$ 都满足 $k\ge 2^{(w+d)/2}$，也就是说 $res_k\le 2^{(w-d)/2}$，那么这一层最多会访问到 $O(2^{(w-d)/2})$ 个块

对所有 $d$ 求和可以得到量级是 $O(2^{\frac w2})$ 的，也就是 $O(\sqrt n)$

优化 2

考虑求一次 $res$ 的过程，我们实际上可以做到更优的复杂度

注意到我们需要进行的操作有每次将一个 $[i,r]$ 加 $1$，然后求全局的最大值

分析一下，只有后缀最大值将来可能有用，所以我们不妨对于 $j=1,2,\cdots,k$，存下最后一个 $\ge j$ 的位置，那么给 $[i,r]$ 加 $1$ 时，我们需要做的就是将 $i$ 前面第一个后缀最大值删除（被后面的顶替了）

这个可以用并查集实现，复杂度 $O(n\alpha(n))$

将两个优化同时使用，复杂度 $O(n\sqrt n\alpha(n))$

---

12. CF2018F - Speedbreaker Counting [E/K] ⭐

题面

考虑一个问题 D1B：

• 数轴上有 $n$ 个城市 $1,2,\cdots,n$

  第一个时刻，你可以选择一个城市然后占领它，称这个城市为你的起始城市

  接下来的每一个时刻，你可以选择一个和你占领的城市相邻的城市，然后占领它

  第 $i$ 个城市有一个限制 $a_i$，表示这个城市必须在第 $a_i$ 个时刻及之前被占领

  求有多少起始城市可以满足条件

给定 $n$，对于 $k=0,1,\cdots,n$，求有多少 $a_1,a_2,\cdots,a_n$，使得问题 D1B 的答案为 $k$，答案对给定质数 $p$ 取模

$1\le n\le3000$

bonus：$1\le n\le2\times10^5$

题解

Sol

被爆了，火大。

F3 ( $n\le3000$ )

钦定一种策略：从外向里，如果左边当前能删就删左边，否则删右边

首先不确定起始点，进行这个策略，如果有解，那么每个点有一个删除时刻

设此时最后被删除的点为 $s$，那么 $s$ 就是一个合法的起始点，接下来我们考虑把起始点换到某个 $us$ 的情况是对称的），那么考虑 $u$ 被删除的时刻，设删之前的区间为 $[u,r]$，那么：

• 如果从 $u$ 直接开始向右走能走完 $[u,r]$，那么 $u$ 一定合法，因为 $s$ 占的过程中某一时刻会占的恰好是 $[u,r]$
• 如果从 $u$ 直接开始向右走走不完 $[u,r]$，那么 $u$ 一定不合法，因为一个合法的点一定能走完任意一个子区间

也就是说如果存在一个合法，那么 $u$ 合法等价于 $u$ 能走完 $[u,r]$，进一步可以等价于 $u$ 开始能走完 $[1,u]$ 和 $[u,n]$

推论：合法的起始点是一个区间 $[ansl,ansr]$

推论：不限制起始点的情况下，我们最后一次删右边，删完之后的右端点就是 $ansr$

只考虑答案不为 $0$ 的情况，我们再枚举一个 $ansl$，钦定 $ansl$ 必须可以，但不钦定 $ansl-1$ 一定不行，最后再容斥一下，这时由一个起始点合法的条件，我们可以得到 $lim_i$ 表示 $a_i$ 由 $ansl$ 必须合法限定的下界

令 $dp_{l,r,0/1}$ 表示当前删到了 $[l,r]$，且当前左端点是否被删失败过，这个是可以转移的

那么我们得到了一个 $O(n^3)$ 的做法

注意到所有我们关心的 $lim$ 数组都是 $n,n-1,\cdots,2,1,2,\cdots,n-1,n$ 的子区间，因此我们直接在这个序列上进行区间 dp 即可

复杂度 $O(n^2)$

F4 ( $n\le2\times10^5$ )

考虑答案必须是一个区间，那么我们直接从一个区间入手

钦定 $k$ 个元素，直接认为它们必须合法，然后不断向外扩展

对于初始的 $k$ 个元素，它们在这 $k$ 个元素内合法的方案数是好算的，用阶乘搞一搞即可

考虑扩展，扩展可以向左扩展一次，满足 $a_{l-1}\ge r-l$，或向右扩展一次，满足 $a_{r+1}\ge r-l$，但这样会算重，因此我们需要减掉左右扩展都可以的情况，即 $a_{l-1},a_{r+1}\ge r-l-1$

写到转移里就是 $2(n-i)f_i\rightarrow f_{i+1},-(n-i-1)^2f_i\rightarrow f_{i+2}$

直接做转移是 $O(n^2)$，转置一下即可做到 $O(n)$

设区间长度为 $k$ 算出来的答案是 $res_k$，那么 $res_k-res_{k+1}$ 就是答案 $\ge k$ 的方案数，再做一遍差分即可

复杂度 $O(n)$

---

13. AGC068A - Circular Distance [E] ⭐

题面

长为 $L$ 的环上有 $0,1,2,\cdots,L-1$ 这 $L$ 个位置，你需要从中选出 $n$ 个位置，定义一种选法的权值为选出的位置两两距离的最大值，距离定义为两端弧中较短的一边

求所有选法的权值之和，答案对 $998244353$ 取模

$2\le n\le L\le10^6$

题解

Sol

钦定 $0$ 必选，乘上 $L/n$ 就是答案

考虑枚举距离最大值 $D$，那么会产生一个区间不能选，这将环拆成了两部分，那么我们对这两部分考虑

具体地，设 $L=14,D=5$，那么我们将剩下的位置重新排列一下：

1  2  3  4  5
      9 10 11 12 13

这样 $(1,i)$ 不能和 $(2,[i,i+D-1])$ 同时选，$(2,i)$ 不能和 $(1,[i-D+1,i])$ 同时选

考虑添加 $(1,0)$ 和 $(2,??+1)$，然后我们将每个选法映射到一条 $(1,0)$ 到 $(2,??+1)$ 的路径，具体地：

• 当前在 $(1,i)$，如果 $(2,i+D)$ 选了，那么就跳到 $(2,i+D)$，否则跳到 $(1,i+1)$，并且这个位置可以任意选不选
• 当前在 $(2,i)$，如果 $(1,i+1)$ 选了，那么就跳到 $(1,i+1)$，否则跳到 $(2,i+1)$，并且这个位置可以任意选不选

我们枚举 $(1,i)\rightarrow(2,i+D)$ 有多少步，此时 $(2,i)\rightarrow(1,i+1)$ 只有 $O(1)$ 中情况，可以枚举，那么我们就知道 $(?,i)\rightarrow(?,i+1)$ 有多少步，可以用组合数计算出选 $n$ 个的方案数

对于一个 $D$ 的复杂度是 $\frac LD$ 的，总复杂度 $O(L\log L)$

---

14. AGC068B - 01 Graph Construction [E]

题面

对于两个 $01$ 个数分别相等的 $01$ 串 $S,T$，按照如下方式定义无向图 $G(S,T)$：

• 对每个 $i$，将 $S$ 中从左到右第 $i$ 个 $0$ 的位置与 $T$ 中从左到右第 $i$ 个 $0$ 的位置连边
• 对每个 $i$，将 $S$ 中从左到右第 $i$ 个 $1$ 的位置与 $T$ 中从左到右第 $i$ 个 $1$ 的位置连边

给定 $a_1,a_2,\cdots,a_n$，你需要构造两个 $01$ 串 $S,T$，使得：

• $S$ 和 $T$ 的 $01$ 数量分别相等
• $n\le|S|\le10^5$
• 对于所有 $1\le i<j\le n$，$i,j$ 在 $G(S,T)$ 中连通当且仅当 $a_i=a_j$

$1\le n\le100,1\le a_i\le n$

题解

Sol

注意到这实际上是在两个串的字符之间连边，但是我们最后需要保证连出来的边能通过 $S,T$ 的方式表示出来

这个条件比较强，一个必要条件是不存在三条边两两交叉，因此我们考虑限定一种特殊的结构：考虑一条 $S_i$ 与 $T_j$ 相连的边，我们要求 $ij$ 的边两两不交叉，$i=j$ 的话任意分到两边

在这种情况下，我们继续观察，$10^5$ 看起来像是什么 $n^2$ 的量级，因此我们考虑一些每次满足一个点的构造

经过若干时间的手模，我们可以得到如下的构造策略：

• 初始 $T$ 有 $n$ 个 $1$，$S$ 有 $n$ 个 $0$
• 然后枚举 $i=1\rightarrow n$，每次考虑满足第 $i$ 位（即将它和它后面第一个 $a_i=a_j$ 的连，不存在则和自己连），设它要连向点 $x$，为了达成这件事情，我们把 $x$ 的当前有效位置的 $S$ 填成 $1$，然后剩下所有数的有效位置都填成 $0$，相当于将这些数整体向后平移了

构造长度是 $n^2$ 量级的

---

15. AGC068C - Ball Redistribution [E/K]

题面

有 $n$ 个球和 $n$ 个盒子，分别编号为 $1\sim n$，初始你可以将每个球放到某个盒子里，然后对 $i=1\rightarrow n$，依次执行操作：

• 将此时在 $i$ 盒子中的球拿出来，任意重排成 $x_1,x_2,\cdots,x_k$
• 对所有 $j$，将 $x_j$ 放到盒子 $x_{(j\bmod k)+1}$ 中

现在给定 $a_1,a_2,\cdots,a_n$，表示第 $i$ 个球最后在第 $a_i$ 个盒子里，判断这个是否是操作后可能得到的最终局面

$1\le n\le2.5\times10^5,1\le a_i\le n$

题解

Sol

考虑把这个操作画到基环树上：我们每次操作就是对于 $i$，将所有连向 $i$ 的点排成一个环

那么倒过来考虑，操作 $i$ 的时候：

• 如果有人指向 $i$，那么 $i$ 必须只被一个人指向，并且 $i$ 在一个环里，我们会将这个环拆开连到 $i$ 上
• 如果没有人指向 $i$，那么我们可以任选一个环，将这个环拆开连到 $i$ 上

能一直操作 $i=n\rightarrow1$ 就说明合法

到了这里，可以直接猜测一下每次暴力拆连通块内的环在时间复杂度和正确性上都是对的，写一下就过了

std 给的做法是一些更有道理的东西：

我们考虑找一些答案的判据，一个必要的条件是对于 $u$ 的任意儿子 $v$，$v$ 子树中必须至少有一个编号大于 $u$ 的节点（否则这棵子树不会被 $>u$ 的操作改变）

经过手模可以发现这也是充分的，因为我们直接拆连通块内的环，操作之后，$u$ 儿子的边一定都会被断开，最多保留一个和 $u$ 处于同一个环内，因此 $u$ 一定是可以操作的

直接判断即可

复杂度 $O(n)$

---

16. AGC068D - Sum of Hash of Lexmin [E]

题面

给定一棵 $n$ 个点的有根树，$1$ 为根，且 $i$ 的父亲编号小于 $i$

对于一个 $1\sim n$ 的排列 $p_1,p_2,\cdots,p_n$，定义一个排列是好的如下：

• 定义一次操作为选择两个相邻元素 $p_i,p_{i+1}$，满足 $p_i,p_{i+1}$ 在树上为祖孙关系，然后交换 $p_i,p_{i+1}$
• 如果任意操作都不能得到比原来字典序更小的排列，则 $p$ 是好的

定义 $\text{hash}(p)=\sum_{i=1}^nB^{i-1}p_i$，求所有好排列的 $\text{hash}$ 值之和，对 $10^9+7$ 取模

$2\le n\le100$

题解

Sol

注意到 $fa_i<i$，这个是比较特殊的，因此我们可以对着这个发掘一些性质，不妨大胆猜测一下一个排列合法当且仅当不存在一步交换使其字典序变小，可以证明这是正确的

考虑对不能一步交换变小的排列进行计数，容斥，那么就是钦定一些祖孙链，算 $\text{hash}$ 值可以看作钦定一个点，然后贡献它的位权乘它的编号

令 $f_{i,x,y}$ 表示 $i$ 的子树，钦定出 $x$ 条链，其中前 $y$ 条链的长度 $B^{len}$ 之和，$g_{i,x,y}$ 表示 $i$ 的子树，钦定出 $x$ 条链，其中钦定的位置在第 $y$ 条链内，位权之和

转移可以用树形背包分析，复杂度 $O(n^4)$

---

17. AGC068E - Sort and Match [K] ✨

题面

给定 $n\times n$ 的矩阵 $a_{i,j}$，以及一个整数 $m$，对满足 $x_i\in[1,n]$ 的序列 $x_1,x_2,\cdots,x_m$，定义 $f(x)$ 为：

• 设 $y$ 为 $x$ 升序排序后的结果，$f(x)=\prod_{1\le i\le m}a_{x_i,y_i}$

对所有 $k=1,2,\cdots,n$，求所有满足 $x_1=k$ 的序列 $x$ 的 $f(x)$ 之和，对 $998244353$ 取模

$1\le n\le50,1\le m\le50$

题解

Sol

素质很差。

考虑建边 $y_i\rightarrow x_i$，对每个 $y$，将所有出边按照对应的 $x$ 在序列中出现位置排序

我们从 $1$ 开始直接搜，由于入度等于出度，最后搜不动的时候会回到 $1$，这时候我们再从 $2$ 开始，不断搜下去

如果我们钦定到达一个 $y$ 时，每次使用当前还没有使用过的顺序最靠前的边，那么可以说明我们建立了一个双射

因此我们只需要计算从 $1,2,\cdots,n$ 开始依次搜环的方案数

定义 $dp_{i,j,k}$ 表示从 $i$ 开始，只搜 $\ge i$ 的点，现在搜到了 $j$，经过了 $k$ 条边的方案数

倒过来考虑，那么 $x_1=k$ 就是在限制倒数第二个点，容易在 dp 的时候处理

复杂度 $O(n^3m)$

---

18. PA2022 - Chodzenie po linie [K]

题面

给定 $1\sim n$ 的排列 $p_1,p_2,\cdots,p_n$，建一张 $n$ 个点的无向图 $G$，满足 $i$ 和 $j$ 之间有边（$ia_j$

定义 $dis(x,y)$ 为 $x,y$ 在 $G$ 中的最短路长度，如果 $x,y$ 不可达则 $dis(x,y)=0$

对每个 $x=1,2,\cdots,n$，求 $\sum_{i=1}^n dis(x,i)$

$1\le n\le2\times10^5,1\le p_i\le n$

题解

Sol

考虑对于一个点 $(i,a_i)$，它到其他位置的最短路

最短路 $>1$ 的点即为所有 $(j,a_j)$ 满足 $ji,a_j>a_i$

继续扩展，我们发现最短路 $>2$ 的点也形如，所有 $(j,a_j)$，满足 $jx_r,a_j>y_r$，其中 $(x_l,y_l),(x_r,y_r)$ 为某两个点

这个规律对于任意最短路 $>t$ 的点都是成立的，并且 $(x_l,y_l),(x_r,y_r)$ 可以从 $t-1$ 的推过来，具体地，新的 $x_l=\min_{(k,a_k),a_k\ge y^\prime_l}k,y_l=\min_{(k,a_k),k\ge x^\prime_l}a_k$，$x_r,y_r$ 类似

那么我们就得到了一个 $O(n^2)$ 的算法，对每个 $x$ 用 $O(n)$ 的时间扩展一下即可

毛估估一下，$(x_l,y_l)$ 看起来比较难构造很多种不同状态，所以我们大胆给这个东西加一个记忆化，发现跑的很快

实际上，不同的 $(x_l,y_l)$ 数量是 $O(n\sqrt n)$ 量级的，证明有点神秘。

有了这个之后，我们可以直接记忆化，但是直接记忆化复杂度是 $O(n\sqrt n\log n)$，并且需要写哈希表，常数较大，因此我们考虑精细实现一下：

• 注意到我们把 $O(n\sqrt n)$ 个点都搜出来之后，需要进行二维数点，可以按照 $x$ 排序，然后用 $O(\sqrt n)-O(1)$ 的数据结构来实现二维数点，将复杂度平衡到 $O(n\sqrt n)$

• 朴素地搜 $O(n\sqrt n)$ 个点的话，需要使用哈希表，考虑优化一下

  我们按照 $x$ 从大到小的顺序，每次扩展当前 $x$ 的所有 $(x,y)$，仔细分析一下可以得到，我们生成的点 $(p,q)$ 一定满足 $q\le a_p$，且同一个 $p$ 的 $q$ 是以递降顺序被生成的，那么我们用 $n$ 个 vector 存这个东西，每次只需要检查对应 vector 的末尾是否与新生成出来的元素相等即可

---

19. PKUCPC2024 - Light up the Statues [K] ✔️

题面

数轴上有 $n$ 个雕像，一共有 $m$ 种魔法属性，第 $i$ 个雕像与第 $i-1$ 个雕像距离为 $d_i$，有一个魔法属性 $c_i$ 和代价 $p_i$

当你没有魔法属性的时候，你可以在一个雕像处耗费 $p_i$ 的代价祈祷，获得属性 $c_i$，当你带着属性 $k$ 经过一个雕像时，如果 $k=c_i$ 那么雕像 $i$ 就会被点亮

你如果有一个属性，那么你不能在获得其他属性，你必须回到你获得这个属性的位置，然后花费 $0$ 的代价把这个属性洗掉

给定 $w_0,w_1,\cdots,w_m$，分别表示持有第 $i$ 种属性时移动一单位距离的代价

你可以任意选定起点和终点，求点亮所有雕像的最小代价

$3\le n\le5\times10^5,1\le m\le2024$

题解

Sol

haoti a.

考虑答案是长成什么样子的：不难发现一定是若干个环，每个环覆盖一段相同的属性，然后最后用一条链把它们串起来，最后的答案就是 $\sum\text{环长}+w_0(r-l)$

首先考虑固定一个 $l,r$ 如何求环长和的最小值，显然可以对每种颜色分开考虑，注意到我们如果建一个虚点向所有 $i$ 连长为 $p_i$ 的边，并且在相邻的同属性雕像之间连 $w_c\times 2dis$ 的边，那么答案就是这张图的最小生成树

那么接下来考虑 $l,r$ 不固定的情况，一个自然的思路是对 $r$ 扫描线，那么我们就要维护每个 $l$ 的最小生成树，考虑多了一个 $r$ 的影响是加了一条 $r$ 到上一个同属性雕像的 $D$ 边，和一个虚点连向 $r$ 的 $p_r$ 边

首先加上 $d$ 边是好做的，因为不会产生任何环，而加上 $p_r$ 边就会产生环，那么我们假设这里上一次选的边是 $k$，需要知道的就是 $\max(D[k+1:r],p_k)$ 和 $p_r$ 的大小关系

那么也就是说我们现在对于一个 $l$ 需要维护出 $\max(D[k+1:r],p_k)$，考虑我们对这个序列做的事情：

• 在加入一条 $D$ 边的时候，我们需要将它们整体对一个值取 $\max$
• 在加入一条 $p_r$ 边的时候，我们需要取出所有 $>p_r$ 的位置，然后对它们进行操作，最后会全部覆盖成 $p_r$，并在最后一个位置加入一个 $p_r$

经过这些操作，我们的 $\max(D[k+1:r],p_k)$ 序列一定是单增的，因此可以用 deque 维护连续段，那么我们的修改就是 $O(n)$ 次区间加，以及区间取 $\max$

那么最后复杂度就是 $O(n\log n)$

---

20. ARC142D - Deterministic Pairing [E]

题面

给定一棵 $n$ 个点的树，对于树上的一个点集 $S$，定义如下操作为 $S$ 的一步移动：

• 对每个 $x\in S$，选择 $x$ 的一个邻点 $T$，将 $x$ 移动至一个邻点，你需要满足得到的新的点集的点依然互不相同

定义一个非空点集 $S$ 是好的当且仅当 $S$ 进行任意 $k\ge1$ 步移动得到的点集都是唯一的，求好的点集数量，对 $998244353$ 取模

$1\le n\le2\times10^5$

题解

Sol

注意到条件相当于 $k=1$ 的时候是唯一的，并且 $k=2$ 的时候唯一的合法方案是挪回来

称点集内的点为黑点，点集外的点为白点，观察到我们的移动其实就是指定若干条 黑-黑-……-黑-白 的链，然后沿着链移动

考虑什么样的情况是不合法的：

• 两个黑色链头不能相邻，否则这两条链可以合并
• 两个白色链尾不能相邻，否则操作一次之后可以得到上述的情况
• 类似地，黑色链头/白色链尾不能和链中间的元素相邻

那么我们直接设 $dp_{i,0/1/2/\cdots}$，表示 $i$ 的子树匹配链匹配到一些状态，转移即可

注意到黑色链头和白色链尾是对称的，因此我们可以出现一个链就乘 $2$，这样可以记得状态稍微少一点

复杂度 $O(n)$

---

21. ARC142F - Paired Wizards [E] ⭐

题面

有三个变量，$c_X,c_Y,ans$，初始 $c_X=c_Y=ans=0$

对 $X$ 执行 $1$ 操作会使 $c_X\leftarrow c_X+1$，执行 $2$ 操作会使 $ans\leftarrow ans+c_X$，对 $Y$ 执行 $1,2$ 操作是类似的

有 $n$ 次事件，第 $i$ 次事件会给定 $a_i,b_i,c_i,d_i\in[1,2]$，你需要选择以下两种中的一个：

• 对 $X$ 执行 $a_i$ 操作，对 $Y$ 执行 $b_i$ 操作
• 对 $X$ 执行 $c_i$ 操作，对 $Y$ 执行 $d_i$ 操作

$1\le n\le8000$

题解

Sol

Flamire 做法

注意到 $ans$ 是 $X$ 和 $Y$ 的 $12$ 子序列个数之和，这个贡献不好统计，我们可以把它变成所有 $2$ 的位置之和，减去 $\binom{cnt_2+1}2$

那如果我们能得到 $res_{i,j}$，表示 $X$ 的 $cnt_2$ 为 $i$，$Y$ 的 $cnt_2$ 为 $j$，我们就能得到最终的答案

将固定的先统计进答案，分类讨论一下选择的种类：

• $X$ 可以在 $1,2$ 间选择
• $Y$ 可以在 $1,2$ 间选择
• $(X,Y)$ 必须是 $(1,1)$ 或 $(2,2)$
• $(X,Y)$ 必须是 $(1,2)$ 或 $(2,1)$

直接枚举的话复杂度是 $O(n^4)$ 的，考虑优化一些枚举量

注意到第四种决策对位置和的贡献是固定的，也就是说最后我们分配四操作的时候只需要关心 $\binom{cnt_2+1}2$ 大小的影响，那么这是一个二次函数极值，将两边尽可能分配均匀即可

也就是说我们做完前三种决策之后，对每个矩阵中的元素算一下最优的四操作分配方案即可，枚举量降到 $O(n^3)$

考虑先做完前两个决策，那么第三种决策就是把每条斜线对一个固定的函数做 $(\min,+)$ 卷积，显然两个函数都是凸的，闵和即可优化到 $O(n^2)$

题解做法

注意到枚举了三四决策之后，一决策的选择只与当前 $X$ 已经被选了多少个 $2$ 有关，二决策同理

那么我们可以处理出 $f_i$ 和 $g_i$，分别表示 $X/Y$ 选了 $i$ 个 $2$ 后，一/二决策能得到的 $\text{位置和}-\binom{cnt_2+1}2$ 的最大值，最后在枚举三四决策后调用即可

复杂度 $O(n^2)$

---

22. ARC142E - Pairing Wizards [E] ⭐

题面

有 $n$ 个人，第 $i$ 个人有两个属性 $a_i,b_i$，你可以花费 $1$ 的代价将任意 $a_i$ 增加 $1$

给定 $m$ 个关系 $(i,j)$，你需要进行一些操作，使得对于任意 $(i,j)$，下面两件条件至少有一个满足：

• $a_i\ge b_i,a_j\ge b_j$
• $a_i\ge b_j,a_j\ge b_i$

求最小代价

$2\le n\le100,1\le m\le\frac12n(n-1),1\le a_i,b_i\le100$

题解

Sol

常做常新。

首先看到每个人要选一个数，可以想到切糕模型，但尝试建模的话会发现两个人之间的建边无法用最小割表示（因为切糕只能处理一个小于等于，另一个大于等于的代价关系）

因此我们需要挖掘一些性质：注意到对于一对 $(i,j)$，$a_i,a_j\ge\min(b_i,b_j)$ 必须成立

那么我们首先把每个人补到这个值，然后我们发现，如果我们将 $i,j(b_i\le b_j)$ 的限制看作 $i\rightarrow j$ 的边，那么只要有一条链 $i\rightarrow j\rightarrow k$，$i\rightarrow j$ 一定会被这个初始值满足

因此我们最后需要关心的限制形如一张二分图，将一边的点全部取反就变成了一边小于等于，另一边大于等于的切糕模型可以处理的问题

复杂度 $O(n^3A+n^2A^2)$

---

23. QOJ5070 - Check Pattern is Bad [E] ❓

题面

给定 $n\times m$ 的 WB? 矩阵，要求将 ? 都填成 W 或 B，使得不存在如下两种 $2\times2$ 的连续子矩阵：

WB  BW
BW  WB

给出构造或判断无解

$1\le n,m\le100$

题解

Sol

首先考虑将所有 $i+j$ 为奇数的位置取反，那么不能出现的就是全 W 或全· B

首先将所有确定了三个相同格子的子矩阵填上

接下来我们大胆猜测一下随便填一个 ? 都不会让有解的变成无解，手玩一下发现玩不出来，那么我们暂且认为这是对的

那么每次填一个 ?，然后再确定所有三个相同格子的，不断重复这个过程即可

复杂度 $O(nm)$

---

24. QOJ5071 - Check Pattern is Good [S]

题面

给定 $n\times m$ 的 WB? 矩阵，要求将 ? 都填成 W 或 B，使得如下两种 $2\times2$ 的连续子矩阵个数越多越好：

WB  BW
BW  WB

$1\le n,m\le100$

题解

Sol

将每个 $2\times2$ 建点，相当于限制某些全黑矩阵和某些全白矩阵不能同时出现

建图跑二分图最大独立集即可

---

25. QOJ1429 - Hit [E/K] ✔️

题面

给定 $n$ 个区间 $[l_i,r_i]$，你需要选择若干个整点，使得每个区间至少包含一个点，并且包含点最多的区间包含点数尽量少

你需要求出这个最小值并给出构造

$1\le n\le10^5$

题解

Sol

Flamire 做法

如果我们固定了答案，考虑判定答案 $v$ 是否合法，可以建一个差分约束模型：

• $(i\rightarrow i-1,0)$
• $(l_i-1\rightarrow r_i,v)$
• $(r_i\rightarrow l_i-1,-1)$

那么合法当且仅当这张图没有负环，但是我们不会判这个，我们暂且不管这件事情。

继续观察性质，注意到我们只保留非 $v$ 边后会得到一个最短路，此时 $i$ 的最短路是 $[i,+\infty)$ 能选出的最多不交区间数

对于一个任意 $l,r$，设 $w[l:r]$ 能选出的不交区间个数为 $c$，此时满足 $c-1\le dis_r-dis_l\le c$，也就是说设此时取所有 $dis_r-dis_l$ 的最大值 $X$，$v=X$ 一定合法，并且我们只需要额外判断 $v=X-1$ 是否合法

但是我们仍然不会对一个 $v$ 判断是否合法。

因此考虑直接跑 spfa，如果更新次数大于 50 倍点数就认为有负环，过了。

事实上，可以开到两倍点数也能过。

复杂度 $O(kn)$

题解做法

考虑一种贪心策略：每次取 $r$ 最小的还没覆盖过的区间，在 $r$ 的位置添加一个点，设这样生成的方案点数最多为 $X$

我们可以说明，答案一定为 $X$ 或 $X-1$：考察任意一个在当前方案中包含了 $X$ 个点的区间，设这 $X$ 个点从左到右为 $x_1,x_2,\cdots,x_X$，那么在任意方案内，区间内最靠左的点一定在 $x_2$ 左边，第二靠左的点一定在 $x_3$ 左边，一直这样推下去，可以得到这个区间内至少有 $X-1$ 个点

那么我们需要判断 $X-1$ 是否可行

考虑进行 dp，对每个点，存 $f_i$ 表示考虑了 $i$ 及 $i$ 左边的点，且必须选择 $i$ 位置的点，所有 $l\le i$ 的区间全被覆盖，是否可能

我们可以贪心，如果 $i$ 可行，那么上一个选的点 $j$ 一定是在 $[j+1,i-1]$ 不包含任何区间的情况下，越靠左越好，这个是可以根据 $i$ 快速求出的，称 $j=prv(i)$

那么我们从 $i$ 开始不断找 $prv$，找 $X-1$ 次 $prv$ 得到 $k$，如果存在一个区间包含 $[k,i]$，那么这个区间一定包含了 $X$ 个点，不合法，$f_i=0$

按照这样 check 一次的复杂度是 $O(n\log n)$，总复杂度 $O(n\log n)$

其实上述两个做法都可以不用 $X$ 和 $X-1$ 的优化，这样只是复杂度多一个 $\log$，出题人并没有卡。

---

26. CF2023D - Many Games [E]

题面

给定 $n$ 个物品，每个物品有属性 $(p_i,w_i)$

你需要选一个子集的物品，使得 $\left(\prod_{i\in S}\frac{p_i}{100}\right)\left(\sum_{i\in S}w_i\right)$ 尽可能大

要求输出这个最大值

$1\le n\le2\times10^5,1\le p_i\le100,1\le w_i,p_iw_i\le2\times10^5$

题解

Sol

有一个显然的 dp 是存对于一个 $\sum w$，最大的 $\sum p$ 是多少

这个限制就很怪。因此我们考虑做一些分析

设我们原来的概率为 $P$，收益为 $W$，那么加上一个 $(p_i,w_i)$ 后会变成 $\frac{p_i}{100}\cdot P(W+w_i)$，比原来优当且仅当 $\frac{p_iw_i}{100}>W(1-\frac{p_i}{100})$

那么首先将 $p_i=100$ 的判掉，因为必选，那么就可以得到 $W<\frac{p_i}{100-p_i}w_i$

由于 $p_iw_i\le2\times10^5$，这意味着我们考虑完 $p_i\ge P$ 的物品时，只用保留 $\frac{2\times10^5}{100-P}$ 的状态，那么状态数就变成调和级数的了

但是转移复杂度仍然过高。

注意到对于同一个 $p$，我们一定取的是 $w_i$ 最大的若干个，而 $W<\frac{p_i}{100-p_i}w_i$，因此如果我们取这里的 $w_i$ 为最小的选择的 $w$，就能得到我们不能选超过 $\frac{p_i}{100-p_i}$ 个当前 $p_i$ 的元素

因此最后总复杂度是：

$$\sum_{p=1}^{99}\frac{2\times10^5}{100-p}\times\frac{p}{100-p}$$

算一下可以发现是 $O(PW\cdot P)$ 的

---

27. CF2023E - Tree of Life [E]

题面

给定一棵 $n$ 个点的树，要求选出尽可能少的链，使得对于任意两条有公共点的边无序对 $(e_1,e_2)$，均在某条链中出现过一次

求这个最小的链数

$2\le n\le5\times10^5$

题解

Sol

首先有一个想法是从叶子往上推，在 $u$ 时，我们考察每个儿子传上来的链数是否 $\ge deg_u-1$，不够则补全，然后将子树两两配对一条链，剩下的全部上传

但是这样并不是最优的，因为我们会在根的位置剩下一堆没有用的链，将它们匹配掉可能使总链数更少，因此我们需要对这个方案进行调整

首先，我们可以将这些多余的链两两配对，那么最后有可能剩下一个绝对众数不能合并，我们进到这棵子树里继续以类似的方式合并，每次传进一个 $ex$ 表示需要合并掉多少条链

这样不断递归下去即可求解，复杂度 $O(n\log n)$

细节较多。

---

28. CF2035G - Go Learn! [E]

题面

考虑如下的二分函数：

let l = 1
let h = n

while l < h:
  let m = floor((l + h) / 2)

  if a[m] < k:
    l = m + 1
  else:
    h = m

return l

这是二分查找某值在递增序列中出现位置的代码

现在有一个待定的数组 $a_1,a_2,\cdots,a_n$，每个元素都在 $[1,n]$ 之间，有 $m$ 个二元组 $(x_i,k_i)$，保证 $x$ 互不相同，$k$ 互不相同

你需要选择这 $m$ 个二元组的一个子集 $S$，使得存在序列 $a$ 满足对于任意 $(x,k)\in S,a_x=k$，且在 $a$ 上面运行二分查找 $k$ 能够定位到 $x$，设 $|S|$ 的最大可能大小为 $r$

除此之外，你还需要求出有多少 $a$ 序列满足存在一个 $|S|=r$ 的子集 $S$ 满足条件，对 $998244353$ 取模

G1：$1\le m\le n\le3000$

G2：$1\le m\le n\le3\times10^5$

题解

Sol

将 $x\neq1,k=1$ 判掉之后，$r$ 就是剩下东西关于 $x$ 和 $k$ 的 LIS

最终这个二分会建出一个类似二叉搜索树的东西，但是值不一定有序，并且这棵树是 leafy 的

但是我们可以直接尝试头铁 dp，令 $w_i$ 表示以 $i$ 结尾的 LIS 长度，令 $f_i$ 表示我们选了第 $i$ 个位置，$a[1:i]$ 满足条件的序列个数，由于我们计数的是最大值，因此我们不用让其他元素不合法（因为一个 $a$ 只可能有一个方案，否则将不是最大值）

我们在从 $j$ 转移到 $i$ 的时候，需要满足 $w_j+1=w_i$ 且 $a_j<a_i$，考虑 $j$ 到 $i$ 路径上的节点的贡献，具体地：

• $j$ 在跳到 LCA 之前的过程中，如果作为父亲的左儿子，那么会要求这个节点 $\ge a_j$，此时我们计入父亲的贡献，乘上一个 $(n-a_i+1)$，然后再乘上右子树内所有数的贡献（$n^{siz}$）
• $i$ 在跳到 LCA 之前的过程中，如果作为父亲的右儿子，那么会要求这个节点 $<a_i$，此时我们计入父亲的贡献，乘上一个 $a_i-1$，然后再乘上左子树内所有数的贡献（$n^{siz}$）
• 对于 LCA，我们判断一下这个 LCA 上判定的值是不是 $j$，如果不是，则再乘上 $a_i-a_j$

也就是说我们的转移可以系数写成一个关于 $j$ 和 LCA 的值 $cl_{j,\text{LCA}}$，以及一个 $i$ 和 LCA 的值 $cr_{j,LCA}$ 的乘积，再额外乘上 LCA 的贡献

这个可以通过预处理，暴力转移做到 $O(n^2)$，可以通过 G1

考虑优化：注意到这个贡献看起来很能拆，因此我们考虑枚举 LCA，然后一块处理左边到右边的转移

由于 $cl,cr$ 的大小只有 $O(n\log n)$，依然是可以预处理的，那么忽略一点细节之后，我们就是要将左边的 $j$ 的一些信息，转移给右边的 $i$，满足 $w_i=w_j+1$ 且 $a_j<a_i$

注意到对于同一种 $w$，$a$ 的值是不断递降的，因此我们先得到左边每一个 $w$，对应的 $a$ 的 vector，求出信息的前缀和，然后转移到右边时用一个指针顺着扫即可

复杂度 $O(n\log n)$

---

29. CF2035H - Peak Productivity Forces [E]

题面

给定两个 $1\sim n$ 的排列 $a,b$

请你不断在 $a$ 上进行下面的操作，在不超过 $2n$ 次操作内将 $a$ 变为 $b$：

• 选择一个 $1\le i\le n$，将 $a[1:i-1]$ 向右循环移一位，将 $a[i+1:n]$ 向右循环移一位

给出构造或判断无解

$1\le n\le5\times10^5$

题解

Sol

Flamire 做法

无解当且仅当 $n=2$ 且 $a\neq b$，然后可以将问题转化为将 $a$ 排序

这个操作就看着很怪啊，考虑一下有没有可以利用的东西

我们发现这个操作每次会将 $a_{i-1}$ 挪到 $a_1$，因此我们考虑能不能在序列前面每次接一个元素让它变得有序

但这样的问题就是我们没办法移动 $a_n$

我们对于 $a_n$ 还有一种操作：用 $i=1$ 让 $a_n$ 移动到 $a_2$，那么我们可以通过结合这些操作，将整个序列排成一个 $1\sim n$ 有序的序列，但是有些相邻元素发生了交换（交换不交），然后期望有什么办法把这个东西在 $n$ 步内排序

具体地，设下一个操作的值在 $a_x$：

• $x\neq n$，那么操作 $i=x+1$ 即可
• $x=n$，且 $a_{n-1}=a_x-1$，那么我们先操作 $i=n$，再操作 $i=1$，这样我们将 $a_{n-1}$ 和 $a_n$ 以原序移动到了序列开头
• $x=n$，且 $a_{n-1}\neq a_x-1$，直接操作 $i=1$，将 $a_n$ 移动到 $a_2$，产生一个交换对

接下来考虑如何在 $n$ 步内将这个东西排序：

我不会。

所以考虑打打表找规律。

首先，暴力告诉我们，想将 $a_n$ 直接移到 $a_1$，即将 $a$ 循环移一位，最少需要 $n$ 步

但是我们发现，对于最后 $x$ 个元素，我们想将它们以某种顺序移到开头并排序，有很多种顺序都是可以在 $x$ 步内完成的

那么我们按块考虑，认为一个交换对是一个 $2$ 的块，其余都是 $1$ 的块，我们打表发现所有三个块和两个块的排列方式（一共 $2^2+2^3=12$ 种），都可以通过长度步数的操作，将其从最后挪到开头并排序的

全打出来塞到程序里，一开始判断一下块数是否是奇数，是奇数就操作一下后三个块，然后每次操作后两个块即可

实现的话，可以观察到操作的时候，我们相当于依次执行 $a_0\leftarrow a_{i-1},a_{i-1}\leftarrow a_i,a_i\leftarrow a_n$ 之后，整体序列就向左挪了一位，那么这是可以 $O(1)$ 模拟的，因此总复杂度 $O(n)$

题解做法

事实上，我们可以用 $n+1$ 步的操作，额外保证一阶段之后，$n$ 一定在 $a_n$ 的位置

那么后面排序的时候，我们可以进行 $n-1$ 操作，每次从 $a_{n-2}$ 和 $a_{n-1}$ 选一个放到序列开头，分别操作 $i=n-1$ 或 $i=n$

更优雅一些。

---

30. QOJ9489 - 0100 Insertion [E]

题面

定义一个 01 串是好的当且仅当存在一种方式每次从其中删除一个 0100 的子段，最后得到空串

给定一个长为 $n$ 的 01? 组成的串 $s$，求有多少方案将 ? 替换为 01，使得得到的串是好串，对 $998244353$ 取模

$4\le n\le500$

题解

Sol

如果我们以 0 的连续段的形式考虑这个问题，那么我们的操作相当于每次合并两个相邻连续段，要求前面的段 $\ge1$，后面的段 $\ge2$

那么如果我们将 0 看作 $+1$，1 看作 $-3$：

• 如果有两个 1 相邻，那么显然不行
• 如果有某个连续段长为 $1$，那么这个 1 一定要和后面的段一起删，也就是说，设这个 1 的位置为 $i$，那么设 $+1/-3$ 后缀和为 $suf$，一个必要条件就是至少存在一个 $j$ 使得 $suf_{i+1}-suf_j\ge2$，即 $suf_{i}+3-suf_j\ge2$

那我们猜一下，这就是充要条件：

• 1 不相邻，且 $s_1$ 不是 1
• $suf_1=0$
• 对于任意 $i$，$suf_i\ge\min(suf[i+1:n+1])-1$

必要性是好证明的，前两个条件显然，第三个条件如果不满足的话，一定存在一个 1 无法操作消除

充分性考虑归纳：

• 如果存在一个 1 后面的连续段 $\ge3$，那么操作掉这个 1 一定不存在任何问题，因为不会影响后缀和的最小值
• 否则，所有 1 后面的连续段都 $=2$（因为此时有 $1$ 就爆了），那么我们从左到右删一定是合法的

直接 dp 即可，复杂度 $O(n^3)$

---

31. CF1615H - Reindeer Games [E]

题面

有 $n$ 个点，每个点有初始点权 $a_i$，有 $m$ 条有向边 $u\rightarrow v$

你每次操作可以将一个 $a_i$ 加 $1$ 或减 $1$，要求操作后对于任意的有向边 $u\rightarrow v$，都有 $a_u\le a_v$

请给出一种可能的最后的点权，使得操作次数最少

$2\le n,m\le1000$

题解

Sol

Flamire 做法

注意到最后点权 $b$ 的取值只能是 $a$ 中的取值

那么相当于我们要给每个点分配一个 $va_1,va_2,\cdots,va_k$ 的取值，并且每个点取 $va_1,va_2,\cdots,va_k$ 有一个代价函数，并且这个代价函数是凸的

有一个常见的思路是拆成只有两种取值的情况，设我们能取的数是 $va_i$ 或 $va_{i+1}$，那么这个问题就可以网络流建模，对每个点比较取 $va_i$ 和 $va_{i+1}$ 的大小，从 $S$ 或 $T$ 建这个差值的边

注意到由于我们取的是相邻的两种数，所以这个差值一定是 $|va_i-va_{i+1}|$，也就是说我们实际上流量上限只有 $n$

同时我们观察 $i$ 加 $1$ 对图发生的改变，只是某一些点从连 $S$ 变为连 $T$

接下来就熟悉了，这个和一亿度灰长得就很像，感性理解一下随着 $i$ 增大割出来的 $S$ 集合会不断变小，$T$ 集合不断变大，因此我们对每张图分别跑网络流，最后将解合起来即可

跑网络流可以用退流优化，因此复杂度 $O(nm)$

保序回归

注意到这个东西就是 $L_1$ 保序回归问题。

保序回归问题可以表述为：

• 给定一张 DAG，初始每个点有点权 $a_i$，你需要重新分配点权 $b_i$，使得对于任意有向边 $u\rightarrow v$，都有 $b_u\le b_v$，并且 $\sum w_i|b_i-a_i|^p$ 最小

当 $p=1$ 时，$b$ 的取值只能从原来的 $a$ 中取，那么我们有结论：

• 对于任意两个相邻的 $a$ 值 $va_i,va_{i+1}$，当我们限制 $b_u\in\{va_i,va_{i+1}\}$ 时得到一组解 $b^\prime$，那么一定存在一组原问题的最优解满足 $b_u\le va_i$ 当且仅当 $b^\prime_u=va_i$

有了这个结论后，我们采用整体二分，每次取 $va_{mid},va_{mid+1}$，将点集分为不交的两部分，递归下去即可，复杂度是 $O(\text{Dinic}\cdot\log n)$

当 $p>1$ 时，我们有结论：

• 对于任意两个值 $x$ 和 $y$（ $x<y$ ），当我们限制 $b_u\in\{x,y\}$ 时得到一组解 $b^\prime$，那么对于限制 $b_u$ 不能在区间 $(x,y)$ 的问题，存在一组最优解满足 $b_u\le x$ 当且仅当 $b^\prime_u=x$

那么我们取 $x=mid,y=mid+\varepsilon$，网络流求解时差值取代价函数在 $mid$ 处的导数即可，复杂度是 $O(\text{Dinic}\cdot\log V)$

---