Contest Info

practice link

Solutions

A. Feeding Chicken

签到题。

B. Send Boxes to Alice

题目大意：给出 \(a_{1},\cdots,a_{n}\)，每次操作可以使某个正的 \(a_{i}\) 减 \(1\)，\(a_{i-1}\) 或 \(a_{i+1}\) 加 \(1\)，求最小的操作次数使得 \(a_{i}\) 的 \(\gcd\) 大于 \(1\)。

题解：显然我们只用枚举一个质数 check。设质数为 \(p\)，\(p\) 应当整除 \(\sum a_{i}\)，我们需要通过操作使得它整除每个 \(a_{i}\)。考虑前缀和 \(s_{i}=\sum_{k=1}^{i}a_{k}\)，一次操作相当于将某个 \(s_{i}(1\le i<n)\pm1\)。最终所有的前缀和都需要满足 \(s_{i}\) 被 \(p\) 整除，且 \(s_{i}\) 不降。如果不考虑单调性，显然答案就是 \(\sum_{i=1}^{n-1}\min(s_{i}\mod p,p-(s_{i}\mod p))\)。而由于开始时 \(s_{i}\) 单调，因此这种方案显然最终也是单调的。

C. Point Ordering

题目大意：给你 \(n\) 个点，保证它们构成一个凸多边形，但是不知道相对顺序。每次询问你可以问这样两种问题：

• \(1,i,j,k\)，\(i,j,k\) 两两不同，告诉你这三点形成的三角形的面积
• \(2,i,j,k\)，\(i,j,k\) 两两不同，告诉你 \(\overrightarrow{A_{i}A_{j}}\times\overrightarrow{A_{i}A_{k}}\) 的符号

在 \(3n\) 次询问内，求出从 \(1\) 开始逆时针的点的顺序。

题解：由第二个询问可以知道三个点的相对顺序。首先用 \(n\) 次询问将所有点关于 \(1,2\) 分为两个部分，再用 \(n\) 次询问求出所有 \(\Delta A_{1}A_{2}A_{i}\) 的面积，备用。

以右半凸壳为例，我们按照面积最大的点为界，再将该凸壳分为两半，那么显然每一小半凸壳上的点就可直接按面积排序了。这部分又需要 \(n\) 次询问。

D. Tree Queries

题目大意：给你一棵树，每个点有点权 \(a_{i}\)，开始时均为 \(0\)。有两种操作：

• 给出 \(v,d\)，然后等概率选取一点 \(u\)，对于所有满足 \(\text{path}(r,u)\) 经过 \(v\) 的点 \(r\)，给 \(a_{r}\) 加 \(d\)
• 给出 \(v\)，求 \(v\) 的期望点权

题解：这题有非常漂亮的解法，但是出题人的似乎有点暴力？

首先对于点 \(u\)，它的点权期望增加 \(n\) 减去以 \(v\) 为根时 \(u\) 所在子树的 \(\text{sz}\)，再除以 \(n\)。当然我们可以不用换根，只需要对 \(v\) 的父亲那棵子树特殊处理一下就可以了。由于我们可以对 \(v\) 的每棵子树分别处理，考虑在树状数组上维护 dfs 序，但是由于子树最坏可以有 \(\mathcal{O}(n)\) 个，因此复杂度是 \(\mathcal{O}(n^{2}\log n)\) 的，还不如暴力.jpg

注意到我们也可以把一些操作 1 存下来，然后对于每个操作 2，暴力处理存下来的操作 1。这样自然而然就想到了大小分块，对于度数小于 \(\sqrt{n}\) 的点用数据结构维护，大于的点则存下来，这样的复杂度是 \(\mathcal{O}(n\sqrt{n}\log n)\)。据说这样已经可以过了.jpg

但是我们还有一个更优雅的做法，对于每个操作 1，我们只更新它的重儿子所在子树，以及父亲的子树，其它统统存下来。而在询问时，我们会发现，只有每次向上跳轻边时，才需要暴力统计，复杂度直接降到 \(\mathcal{O}(n\log n)\)。太 nb 了.jpg

E. Send Tree to Charlie

题目大意：有一棵树，开始 \(i\) 的点权为 \(i\)，对于 \(n-1\) 条边的一个排列，按顺序将每条边的两个点的点权交换。现在已知最终点权 \(i\) 所在结点为 \(a_{i}\)（若 \(a_{i}=0\) 则表示可在任意结点），求有多少种符合上述操作及限制的最终局面（而不是排列的数量）。

题解：首先我们来归纳地证明，如果每个点的所有邻边的操作相对顺序不变，那么最终局面也不变。考虑加入一个新的叶子 \(u\)，设它的邻点为 \(v\)。假如其它所有边的操作顺序已经确定，\(u,v\) 这条边在 \(v\) 的哪两个其它邻点之间操作也已经确定，那么这条边不论在区间中哪个位置操作，显然都不影响最终局面。

其次我们证明，我们固定每个点的邻边的操作顺序后，一定能找到一个全局的操作顺序使得每个点都满足。这个比较简单，我们按照 dfs 顺序依次构造即可，由于是棵树，很容易避免冲突。

然后我们来解决这道题目。如果点权 \(i\) 最终仍在 \(i\)，显然是非法的，然后考虑所有点权初始点和当前点的距离之和，容易发现每次操作后必然增加 \(2\)，因此最终的和必须恰好是 \(2n-2\)。

假如我们要求 \(i\) 最终在 \(a_{i}\)，设 \(i\) 到 \(a_{i}\) 的路径为 \(i=v_{0},v_{1},\cdots,v_{t}=a_{i}\)。那么我们有：

• \(v_{1}\) 应当是 \(v_{0}\) 的邻点中第一个操作的
• \(v_{t-1}\) 应当是 \(v_{t}\) 的邻点中最后一个操作的
• \(v_{j+1}\) 在 \(v_{j}\) 的邻点中应当紧随 \(v_{j-1}\) 操作

这些条件是充要的。另外注意到刚刚的路径长度之和 \(=2n-2\)，因此限制数量的总和也是 \(\mathcal{O}(n)\) 的（超过时非法）。

由于刚才的引理，我们只需要将每个点的邻边的排序方案数乘起来即可。这个方案就较容易求了，这里不再赘述（主要是 case 太多）。

时间复杂度 \(\mathcal{O}(n)\)。