- 搬题人：
- A, D, E：p_b_p_b
- B, C：cdw
- 组题人：hehezhou
- 验题人：AutumnKite, chenkuowen01
- 题解：AutumnKite, cdw, chenkuowen01, hehezhou
捉迷藏
题目来源：
- 京都大学プログラミングProgramming コンテストContest 2021, Problem L
- Petrozavodsk Winter 2022, Day 1, Kyoto U Contest, Problem L
- XXII Open Cup, Grand Prix of Kyoto, Problem L
QOJ 链接：https://qoj.ac/problem/2550
为方便叙述，我们先假设树以 $v$ 为根。我们称距离 $v$ 为 $d$ 的点为“候选点”。令 $h=\lfloor\frac{d-1}{2}\rfloor$。
考虑一条从 $v$ 出发的最长链，B 的策略一定是沿这条链走 $h$ 步。假设 B 走到了 $u$，则 A 此时一定在 $u$ 的某棵存在“候选点”的子树中。
接下来 B 的策略有两种：
- 往回走，即回到 $u$ 的父亲。
- 往 $u$ 的某棵不存在“候选点”的子树中走。
然后找到最长的路径一直走即可。显然这个过程中 A 一定追不到 B。
考虑从 $v$ 出发的最长链一定是到直径的某个端点，所以我们可以分别以直径两个端点为根，上述过程可以简单的维护。
时间复杂度 $O((n+q)\log n)$。
新问题
题目来源：Romanian Master in Informatics 2020, Day 1, Task "Floppy".
QOJ 链接：https://qoj.ac/problem/147
算法 1
记录单调栈的弹出和压入。
算法 2
按先序遍历的顺序记录笛卡尔树的每个结点是否有左右儿子。
括号序列
题目来源：Romanian Master in Informatics 2021, Day 2, Task "NoM".
QOJ 链接：https://qoj.ac/problem/2811
官方题解：https://rmi.lbi.ro/rmi_2021/editorial.pdf
考虑容斥，设 $f_i$ 表示有序地选择 $i$ 个位置的有序对使得每对的下标之差均为 $M$ 的倍数的方案数，然后选择 $i$ 个括号放进这些位置，其他 $2(N-i)$ 个元素任意排列，所以答案为 $\displaystyle\sum_{i=0}^N(-1)^i(2N-2i)!\binom Nif_i$，而 $\displaystyle f_i=\left[\frac{z^i}{i!}\right]\prod_{j=0}^{M-1}\sum_{k=0}^{\lfloor n_j/2\rfloor}\frac{n_j!}{(n_j-2k)!}\cdot\frac{z^k}{k!}$，其中 $n_j$ 表示 $[1,2N]$ 中模 $M$ 的余数为 $j$ 的数的个数。
暴力计算多项式乘法，时间复杂度 $\mathcal O(N^2)$，若使用 FFT 计算则时间复杂度 $\mathcal O(N\log N)$。
子序列
题目来源：Petrozavodsk Winter 2022. Day 3. Kazakhstan Contest, Task G
QOJ 链接：https://qoj.ac/problem/2570
解法一
by chenkuowen01
考虑先进行一次 $dp$，$f(i)$ 表示原数列中以 $i$ 为结尾的最长上升子序列长度。
$dp$ 转移大致为： $f(i)=\max_{j\lt i\land a_j\lt a_i} f(j)+1$
这部分可以采用树状数组优化，复杂度为 $\Theta(n \lg n)$
考虑一张 $n+2$ 个点（结点编号依次为 $0\cdots n+1$）的图 $G=(V,E)$ 以如下方式建边：
- 若$j\lt i,a_j\lt a_i,f(j)=f(i)-1$，则加一条边 $(j,i)$。
- 若$f(i)=1$，则加边 $(0,i)$。
- 若$f(i)$ 为最大值，则加边 $(i,n+1)$。
现在问题转化为要删去若干个结点，使得不存在合法的从$0$到$n+1$的路线
可以把问题转化为最小割模型，但显然使用最大流方法无法满足效率的要求。
这个图虽然不是平面图，但我们可以从平面图最小割得到一些启发。我们考虑按某种顺序依次截断从$0$到$n+1$的通路，尝试进行dp。
$g(i)$ 表示对于每个 $x$，不存在 $j(j\le i,f(j)=f(i))$使得存在 $j$ 到 $x$ 的路径或 $x$ 到 $j$ 的路径。不存在经过 $x$ 的通路的最少需要删除的点数。
令 $last(i)=\max_{(j,i)\in E} j$
$next(i)=\max_{(i,j)\in E} j$
$h(i)=\max_{j< i\land f(j)=f(i)} j$(没有则视为$-1$)
然后考虑转移：
对于 $0$ 和 $n+1$，这两个点不能删除，转移是显然的。
对于剩余的点转移有两种选择，一种是不删除，一种是删除。
对于不删除的情况，若原先就不存在经过这个点的通路，则可直接转移到 $h(i)$，即 $g(h(i))=\min(g(h(i)),g(i))$。
否则有两种情况，一种是去前面截断通路，一种是去后面截断通路，即：
$g(last(i))=\min(g(last(i)),g(i))$
$g(next(i))=\min(g(next(i)),g(i))$
对于删除的情况，转移只有一种：
$g(h(i))=\min(g(h(i)),g(i)+1)$
$g(-1)$ 即为答案。容易发现这个转移是有后效性的，所以可以转化为最短路模型。本题边权只有0和1，所以可以采用 01bfs（如果你不知道这个算法也可以采用 dijkstra）。
这部分复杂度为 $\Theta(n)$ 或 $\Theta(n\lg n)$ 。
所以整体的复杂度为 $\Theta(n\lg n)$
解法二
by hehezhou
往最小割的方向继续思考。
把每个点拆成入点和出点，并在之间连一条权值为 $1$ 的边，即可将模型转为最小割，即最大流。
这张图最大流的组合意义即为：最多能选出不交的最长上升子序列数量。
实际上，每次选择下标字典序最小的最长上升子序列并删去是正确的。
可以将图看作一个分层图，每层的点有序，并且每层每个点向下一层的一个区间连边，连边区间具有单调性，这和原问题是等价的。
记第 $i$ 层第 $j$ 个点为 $(i,j)$，则下标字典序最小的最长上升子序列等价于这样标号后，字典序最小的路径。
首先证明一个结论：存在一个最优方案，所有路径边不交，即不存在两条路径，分别存在 $(i,x_1)-(i+1,y_1)$ 和 $(i,x_2)-(i+1,y_2)$ 两条边，满足 $x_1\lt x_2$ 且 $y_1\gt y_2$。
否则可以将路径替换为 $(i,x_1)-(i+1,y_2)$ 和 $(i,x_2)-(i+1,y_1)$，后面的部分同样交换，由于出边区间的单调性，这样仍然合法，并且交点个数变少，不断重复即可得到一个不交的方案。
将路径按照字典序排序，每次考虑求出某个最优方案中字典序最小的路径。
直接挑选字典序最小的合法路径，这一定在某个最优方案中。
这是因为在这条路径上方（同层点中编号更小的）的点要么无法从起点到达，要么无法到达终点，是无用的点，可以删去。在删去这些点并重标号以后，这条路径就是 $(1,1)-(2,1)-(3,1)-\cdots$。
由于存在一个最优方案的路径不交，这个最优方案的所有路径至多有一条（即方案中字典序最小的）和找出的路径有交，将这个最优方案的第一条路径替换为找出的这条路径，仍然是一个合法的最优方案。
因此不断找出字典序最小的路径并删去，可以得到某个最优方案。
考虑怎样快速的进行这个过程：
首先求出每个点出边的左右端点，每次找路径使用 $\text{dfs}$ 算法。
$\text{dfs}(x,y)$ 需要尝试求出从 $(x,y)$ 出发的，只包含未被删去的点的，字典序最小的路径。
每层点删去的一定是一个前缀，因此可以 $O(1)$ 求出出边区间剩余的部分，并从小到大枚举，继续进行 $\text{dfs}$。
如果枚举完所有出边后，仍未找到一条合法路径，那么这个点无用（无法到达终点），可以被删去。如果此时同层上方有未被删去的点，说明这些点无法从起点到达，一并删去，保持了前缀的性质。
否则一路回溯就找到了一条路径，这个点同样会被删去。
因此每个点只会进行一次 $\text{dfs}$，并且所有点至多被 $\text{dfs}$ 内枚举一次，总复杂度 $O(n)$。
算上求最长上升子序列的部分，总复杂度 $O(n\log n)$。
平均分
题目来源：Petrozavodsk Winter 2022. Day 3. Kazakhstan Contest, Task H
QOJ 链接：https://qoj.ac/problem/2571
我们形式化一下问题：分成三个组，和分别为 $x,y,z$，$x\le y\le z$，最小化 $z-x$。
考虑 meeting in the middle，两侧分别爆搜三个组，这部分复杂度为 $\Theta(3^{\lceil n/2\rceil})$。
设爆搜出来的一组方案三个和为 $x_0,y_0,z_0$，由于和是固定的，我们只需要保留一个二元组 $(x_0-z_0,y_0-z_0)$。
考虑左右合并的部分，对于一个左侧二元组 $(a,b)$ 和一个右侧二元组 $(x,y)$，能合并的条件为： $ a+x\le b+y\le 0$，最大化 $a+x$。
这是一个类似二维偏序的问题，可以排序后使用树状数组求解。
总复杂度 $\Theta(3^{\lceil n/2\rceil}\times n)$
