Petrozavodsk Camp, Summer 2021 Kyoto U Contest

排名	当场过题数	至今过题数	总题数
55/90	6	11	13

C

solved by Bazoka13

题意

构造一个 \(n \times n\) 的字母矩阵，满足往下往右没有长度大于 \(1\) 的重复子串，要求 \(13 \le n \le 100\)。

题解

手搓搓麻了。

jgg 说随机放合法的就可以（x

D

upsolved by JJLeo

题意

一共有 \(n\) 个物品，第 \(i\) 个物品重量为 \(2i-1\)，将 \(n\) 个物品分为 \(>1\) 组，使得每组重量和均相等，或判断无解。(\(2 \le n \le 10^5\))

题解

如果 \(n\) 是偶数，很好解决。

如果 \(n\) 是质数，总和是 \(p^2\)，只能分为 \(p\) 组或 \(p^2\) 组，而 \(2p-1 > p\)，因此必然无解。

如果 \(n\) 是质数的平方，设为 \(p^2\)，有一种将其分为 \(p\) 组的方案，将 \(p^2\) 个数按大小从上到下从左到右写成 \(p \times p\) 的矩阵，如果每组每行都恰好选了一个，显然每组的和是相等的。可以发现每组选一个对角线符合这个条件。

否则，可以将 \(n\) 写为 \(p(p+q)=p^2+pq\)，其中 \(p\) 是 \(n\) 的最小质因子，\(q\) 是偶数，而 \(p^2\) 和 \(pq\) 都可以分为 \(p\) 组，各自每组内和均相等，将这 \(2p\) 组两两组合即可得到和相同的 \(p\) 组。

G

upsolved by JJLeo

题意

初始序列只有一个 \(1\)，每次有三种操作：

• 往序列后面插一个 \(1\)。
• 往序列后面插一个 \(m\)。
• 在序列中两个相邻数 \(a_i,a_{i+1}\) 中间插入数 \(x\) 满足 \(a_i < x < a_{i+1}\) 或 \(a_{i+1} < x < a_i\)。

最终要得到一个长度为 \(n\) 的序列，问有多少种不同的操作序列？操作有一步不同就算不同，即使最后得到的序列是相同的。(\(1 \le n \le 3000\)，\(2 \le m \le 10^8\))

题解

考虑最终序列一定是形如一堆 \(1\) 和 \(m\)，每个 \(1\) 和 \(m\) 交界处中间有数个 (可能为 \(0\)) 升序 \([2,m-1]\) 中的数，每个 \(m\) 和 \(1\) 交界处中间有数个 (可能为 \(0\)) 降序 \([2,m-1]\) 中的数。

其等价于不断进行这样的操作：

• 如果当前以 \(1\) 结尾放 \(m\)，否则放 \(1\)，选数个 \([2,m-1]\) 个数按升序或降序放在中间。
• 放一个和当前结尾一样的数。

对于第一种操作，由于最终问的是操作序列数量，而中间选的这些数之后啥时候放都可以，因此我们考虑直接为其选定位置。设 \(f_i\) 是序列已经有 \(i\) 个数的操作序列方案数，那么显然还有 \(n-i\) 个位置的操作是没确定的，因为我们需要先放后面那个 \(1\) 或者 \(m\) 才能放中间的数，因此第一个未被确定的位置一定是放这个数，之后枚举中间选 \(j\) 个数，那么可以从剩下 \(n-i-1\) 个位置挑 \(j\) 个，且这 \(j\) 个的相对顺序可变，同时这 \(j\) 个数的范围是 \([2,m-1]\)，有转移式： $$ f_{i+j+1} \leftarrow f_i\binom{n-i-1}{j}j!\binom{m-2}{j} $$ 对于第二种操作，相当于选择第一个未被确定的位置放这个数，因此有： $$ f_{i+1} \leftarrow f_i $$ 总时间复杂度为 \(O\left(n^2\right)\)。

H

solved by 2sozx JJLeo

题意

\(n \times m\) 的方格图中，有一些位置上有障碍，此外的一个格子上有豆子，豆子每次可以向左右或向下走一格，不能走到障碍上。此外，这个图是左右循环的，也就是最左往左可以走到最右，反之亦然。但是其不是上下循环的，即最下面不能再往下走了。要求豆子不能走到之前经过的格子上。

求出豆子在每个位置上的 SG 函数，判断异或和是否非 \(0\)。(\(1 \le n,m \le 10^3\))

题解

一开始读错题了，没看到这个图是左右循环的，就直接设每个状态为 [位置] \(\times\) [从上面下来| 从左边过来| 从右边过来]，每个点的出度至多为 \(3\)，直接记忆化搜索求 SG 函数即可。

发现样例过不去，加了左右循环有什么问题呢，如果一行没有障碍，那么绕一圈回到自己并不能走到自己，上面的方法就寄了。

以向右为例，注意到这样的一行中，如果确定了一个起点，那么结构就是它指向向右的一个格子以及向下的一个格子，一直往右走，直到这个格子左边的那个格子，它只指向下面的那个格子 (因为不能经过相同的格子)。

下面格子的 SG 函数都已经知道了，所以相当于 \(\operatorname{mex}(a_1,\operatorname{mex}(a_2,\operatorname{mex}(a_3,\cdots\operatorname{mex}(a_k,x))))\) 的形式，而每个点出度为至多为 \(2\)，因此相当于只有 \(0,1,2\) 三种值，将两两 \(\operatorname{mex}\) 的值处理出来后相当于用线段树处理区间进来一个数 \(x\) 出去什么数的问题。

除了这些行的状态需要用这个方法求，其它都沿用之前的记忆化搜索。

一些踩的坑：

• 以向右为例，输入的值并不是 \(0\)，而是这个格子左边的那个格子，它的 SG 函数就是下面那个格子的 SG 函数单独取 \(\operatorname{mex}\)。
• 上面这条不完全对。因为，除了这种特殊的行，其他还沿用上面的部分，而在这样的行中，只有确定了往一个方向走才能用线段树预处理出来的值，而这已经走了一步了，以向右为例，它左边那个格子也不能走，所以输入的值是这个格子左边的左边的那个格子。

综上，时间复杂度为 \(O(nm \log m)\)。

I

upsolved by JJLeo

题意

给定一个 \(n\) 个点 \(m\) 条边的点双连通分量，需要给每条边染色，有共同点的边颜色不能相同，使得对于每条边 \((u,v)\)，存在一条不经过这条边的 \(u,v\) 之间的路径满足路径上颜色数量不超过 \(8\)。

除了输出染色方案，对每条边还要输出不超过 \(8\) 种颜色，保证存在一条上述路径其颜色均在这之中，方便 checker 检验正确性。

(\(3 \le n \le 5555\)，\(3 \le m \le \min\left(\dfrac{n(n-1)}{2},9999\right)\))

题解

随便建出一个 dfs 生成树，如果我们能保证从根到任意节点的颜色都不超过 \(7\)，就完成了题目中的任务，设一条边为 \((u,v)\)，\(v\) 的深度大：

• 对于非树边，走它们之间的树边，这条路径就是从根到 \(v\) 路径的一部分。
• 对于树边，从 \(v\) 往下走，一定能找到一个点 \(x\) 返祖到 \(u\) 的祖先 ，那么这条路径就是从根到 \(x\) 路径的一部分，额外再加上这条返祖边，最多有 \(8\) 种颜色。

一种构造方法为，按深度依次给每个点儿子的父边染色，首先不能其父边同色，然后优先染其它祖先边的颜色，如果还不够则随便染其它颜色。最重要的是染色的顺序，按照每个子节点对应的子树大小从大到小排序后依次染色。其正确性证明如下：

考虑点 \(v\) 和其父亲 \(u\)，如果 \((u,v)\) 的颜色不同于其往上所有边的颜色，设其往上所有边的颜色共有 \(c\) 种，那么根据我们的染色方案，有 \(\textit{siz}_v \le \dfrac{1}{c}(\textit{siz}_u-1)\)，减掉的 \(1\) 是点 \(u\) 也算 \(1\) 的大小。

这个式子可以化为 \(\textit{siz}_u \ge c \cdot \textit{siz}_z + 1\)。

对于一个叶子，其到根的颜色数量为 \(C\)，那么从下往上依次找到这样的边，初始其 \(\textit{siz}\) 为 \(1\)，每次都将其乘以 \(c\) 再加 \(1\)，而 \(c\) 依次为 \(C-1,C-2,\ldots,1\)，因此最后会变为 \(\sum \limits _{i=1}^{C-1} i!\)，也就是说 \(n \ge \sum \limits _{i=1}^{C-1} i!\)。

当 \(C \ge 8\) 时，\(\sum \limits _{i=1}^{C-1} i! \ge \sum \limits _{i=1}^7i=5913 > 5555\)，因此至多有 \(7\) 种不同的颜色。

最后对于所有非树边 \((u,v)\)，寻找一种不冲突的颜色即可。

输出方案时，对于非树边，直接输出 \(v\) 到根的所有边颜色即可。

对于树边，首先要找到 \(x\) 这个点，输出 \(x\) 到根的所有边颜色，同时要把与 \(x\) 的返祖边颜色加进去。

这里可以用 tarjan 实现，但我偷懒乱搞简化出了很多 bug，细节出奇的多，寄！

J

upsolved by JJLeo

题意

交互题，有一个 \(1\) 到 \(n\) 的排列，你需要把它猜出来，可以问两种询问：

• 询问三个位置的中位数。
• 询问两个位置的大小关系。

第一个询问可以问 \(2n\) 次，第二个询问只能问两次。(\(4 \le n \le 60000\))

题解

核心思路是一直维护四个位置的基本信息，每次用不超过 \(2\) 次询问得到一个新位置的值，同时仍保证有四个位置的基本信息，当然这四个位置可能会发生变化。

设四个位置为 \(i,j,k,l\)，基本信息指的是：

• \(\max(a_i,a_j) < \min(a_k, a_l)\)。
• \(\max(a_i,a_j)\) 和 \(\min(a_k, a_l)\) 的值。

首先我们对前四个位置问 \(\dbinom{4}{3}\) 次第一种询问就可以得到前四个位置的基本信息：

返回结果有两次是 \(\max(a_i,a_j)\)，两次是 \(\min(a_k, a_l)\)，对得到前者的两次询问的下标取交集就能知道 \(i,j\)，另外两个即为 \(k,l\)。

接着依次考虑每个位置 \(x\)，先询问 \(i,k,x\) 三个位置的中位数，设其为 \(A\)。

• 如果 \(A < \max(a_i,a_j)\)，因为 \(a_k>\max(a_i,a_j) > A\)，那么 \(A = \max(a_i,a_x)<\max(a_i,a_j)\)，说明 \(a_j=\max(a_i,a_j)\)，我们可以确定 \(a_j\) 的值，将 \(j\) 改为 \(x\)，\(\max(a_i,a_j)\) 改为 \(A\) 即可。
• 如果 \(A = \max(a_i,a_j)\)，因为原序列是排列，所以 \(a_i=\max(a_i,a_j)\)，我们可以确定 \(a_i\) 的值，将 \(i\) 改为 \(x\)， 再问一次 \(i,j,k\) 三个位置的中位数即可得到 \(\max(a_i,a_j)\)。
• 如果 \(A = \max(a_i,a_j)<A<\min(a_k,a_l)\)，则 \(a_x=A\)，不需要改变四个位置。
• 如果 \(A = \min(a_k,a_l)\)，因为原序列是排列，所以 \(a_k=\min(a_k,a_l)\)，我们可以确定 \(a_k\) 的值，将 \(k\) 改为 \(x\)， 再问一次 \(j,k,l\) 三个位置的中位数即可得到 \(\min(a_k,a_l)\)。
• 如果 \(A > \min(a_k,a_l)\)，因为 \(a_i<\min(a_k,a_l)<A\)，那么 \(A = \min(a_k,a_x)>\min(a_k,a_l)\)，说明 \(a_l=\min(a_k,a_l)\)，我们可以确定 \(a_l\) 的值，将 \(l\) 改为 \(x\)，\(\min(a_k,a_l)\) 改为 \(A\) 即可。

最后只剩下四个元素，我们用两次第二种询问得到 \(i,j\) 位置的大小关系，以及 \(k,l\) 位置大小关系，就能把四个没有位置的值正确地分配到这四个位置上。

K

upsolved by

题意

题解

L

upsolved by

题意

题解

M

upsolved by JJLeo

题意

\(n\) 个位置，每个位置都必须放一个合法的括号序列 (可以为空)，要求所有位置的左括号数量之和是 \(m\)，且不能有一个位置的左括号数量是 \(k\)，求方案数。(\(1 \le n,m \le 10^6\)，\(1 \le k \le m\))

题解

设 \(C_n\) 是卡特兰数第 \(n\) 项，显然答案为：

\[ \left[x^m\right]{\left(\sum _{i=0} ^\infty C_ix^i-C_kx^k\right)}^n \]

多项式快速幂常数太大，寄。

考虑另一种方式，设 \(f_{i,j}\) 是 \(i\) 个位置一共 \(j\) 个左括号的方案数，那么利用容斥答案即为：

\[ \sum_{i=0}^n{(-1)}^i\binom{n}{i}{(C_k)}^if_{n-i,m-ik} \]

如果 \(f_{i,j}\) 可以 \(O(1)\) 计算就可以 \(O(n)\) 完成。

这玩意看起来没有显然的 \(O(1)\) 式子，题解告诉我们遇事不决推式子：

\[ \begin{aligned} f_{i,j}&=\sum_{k=0}^jf_{i-1,j-k}C_k \newline &=\sum_{k=0}^j\left(\sum_{l=0}^{j-k}f_{i-2,j-k-l}C_l\right)C_k \newline &=\sum_{0\le k+l \le j}f_{i-2,j-(k+l)}C_kC_l \newline &=\sum_{x=0}^jf_{i-2,j-x}\sum_{k+l=x}C_kC_l \newline &=\sum_{x=0}^jf_{i-2,j-x}C_{x+1} \newline \end{aligned} \]

利用这个式子，回到一开始的式子：

\[ \begin{aligned} f_{i,j}&=\sum_{k=0}^jf_{i-1,j-k}C_k \newline &=f_{i-1,j}+\sum_{k=1}^jf_{i-1,j-k}C_k \newline &=f_{i-1,j}+\sum_{k=0}^{j-1}f_{i-1,j-1-k}C_{k+1} \newline &=f_{i-1,j}+f_{i+1,j-1} \newline \end{aligned} \]

现在变成了一个 \(O\left(n^2\right)\) 的式子了，继续考虑其组合意义，令 \(g_{i,j}=f_{i-j,j}\) (\(i \ge j\))，则递推式为：

\[ g_{i,j}=g_{i-1,j}+g_{i,j-1} \]

注意到 \(g_{0,0}=f_{0,0}=1\)，\(i>0\) 时 \(g_{i,i}=f_{0,i}=0\)，这个边界条件很重要，说明其并不是单纯的向右向上走的方案数。

另有 \(g_{1,0}=f_{1,0}=1\)，因此对 \(i,j\) 均不为 \(0\) 时可以认为这个式子为从 \((1,0)\) 出发，每次令横纵坐标之一增加 \(1\)，始终 \(i>j\) 的最终到达 \((i,j)\) 的方案数，平移一下即为从 \((0,0)\) 出发，每次令横纵坐标之一增加 \(1\)，始终 \(i\ge j\) 的最终到达 \((i-1,j)\) 的方案数，由求解卡特兰数的折线对称法易得其方案数为 \(\dbinom{i-1+j}{j}-\dbinom{i-1+j}{j-1}\)。

将上述三种情况从 \(g\) 再变换为 \(f\)，有：

\[ f_{i,j}=\begin{cases} \dbinom{i+j-1+j}{j}-\dbinom{i+j-1+j}{j-1}, &i>0 \newline 1, &i=j=0 \newline 0, &i=0,j>0 \end{cases} \]

即可 \(O(1)\) 求解。

记录

0h：开局MJX乱看看了个CD，CSK看榜才发现AB大SB签到，写了过了，ZYF看E也是个大签到题写了过了。看M可以用模板但是复杂度感觉不对但是写了些。MJX想了想C又想了想D，不会CSK开始手搓CD，MJX看看F，发现也是个大签到题。

1h：F过了，写个了C的随机数一直在后台跑着。MJX和ZYF想H，发现做法老显然了，直接开写，写完样例没过。期间MJX开始YY C 和M，想了M容斥但是那个数感觉完全不可O(1)算（然后就可以O(1)算）。F发现读错题了，在同一行可以循环，开始想咋做，发现可以直接线段树维护进来一个数出去什么数，然后ZYF开写。

2h：MJX想对角线构造C，但是寄了，CSK想了个D的构造，然后到小情况不会做了。MJX开始帮ZYF造造数据看看看看代码，CSK开始想CD两题的构造。改了改然后交了一发H，WA了，发现写反了（其实没写反，是写少了）。改了多过了两点。

3h：改了个写法发现数组开小了RE了，交上去还是WA，CSK构造出来了C，贼猛，过了。MJX看ZYF写的合并写反了，改了改然后可以WA31了。后来发现他终态并不一定是0，改了后交了一发，WA9。然后发现小数据就错了，其实特判掉 \(m = 2\) 然后继续 dfs SG函数。

4h：改了过了，挂机！

总结

Dirt