第十八届东南大学大学生程序设计竞赛（春、夏季） - 题解

A. 数方框

本题中确保了所有方框线条宽度都是1像素。对于一个方框而言，只需要确定其左上角与右下角，就可以确定整个方框的坐标。假设整个图片中第$i$行第$j$列的值记为$I$，只需要找出所有左上角$(I_{i,j}=I_{i+1,j}=I_{i,j+1}=1)$与右下角$(I_{i,j}=I_{i-1,j}=I_{i,j-1})=1$，然后对于每对左上角与右下角做配对并判断右下角与左上角坐标的的相对位置正确性，就得到了一组合法的方框坐标。对于一组合法的方框坐标，只需要判断四个顶点之间是否形成闭合连线，就可以确定是否为一个合法的方框。对于任意两个横坐标或纵坐标相同的顶点，判断他们之间是否存在连线等价于判断这两个顶点间的像素值之和是否等于顶点间的距离。显然，预先处理好每行每列的前缀和就可以做到$O(1)$复杂度对其进行判断。

B. 年底查账

本题利用差分序列即可解决。

C. log are trees

设所有点对构成的长度为$i$路径数有$cnt_i$个，显然可以$O(n)$地求出答案$ans=\frac{\sum_{i=1}^n(i+1)\left(cnt_i\sum_{j=1}^icnt_j\right)}{n^4}$。

问题转化成如何求$cnt$数组，考虑点分治。统计子树信息过程中记录每个子树到分治中心距离，设存在两个子树到分治中心距离为$i$的节点分别有$A_i,B_i$个，则两子树间的路径长度为$i$的路径数$C_i=\sum_{j=0}^iA_j\times B_{i-j}$，这是一个卷积的形式，可用$FFT/NTT$进行加速优化。

为避免子树间两两合并导致时间复杂度过大，考虑容斥计算，即所有子树信息合并后对自己做一次卷积运算，再减掉非法答案，即每个子树对自己做一次卷积运算。

时间复杂度$O(nlog^2n)$。

D. Far Away Light

将$n\times m$个格点分成以下4类：

1. $x\neq x_2$且$y\neq y_2$
2. $x = x_2$且$y\neq y_2$
3. $x\neq x_2$且$y= y_2$
4. $(x_2,y_2)$

目标状态$(x_2,y_2)$属于第4类，起始状态$(x_1,y_1)$是4类中的某一类。每个时刻的移动等价于状态的转移。因此我们可以使用动态规划来计算状态转移的方案数，状态转移时使用乘法原理，叠加时使用加法原理。

在第$i$个时刻，令$f_{i,0\sim3}$分别表示在第$i$个时刻，云在以上四种状态之一时的方案数，不难得到：

这是一个线性递推式，复杂度$O(k)$，无法通过本题。

考虑使用矩阵优化，将上式转化为：

快速幂优化即可。时间复杂度$O(\log{k})$。

E. corps-sans-organes

注意到答案具有单调性，因此对答案进行二分。

显然答案下界是$1$，使用归纳法可得出答案的一个上界是$k$，因此在$[1,k]$内进行二分。

令当前二分的中间值为$x$，只需求出表格中有多少数字比$x$小。

即求$\sum_{i=1}^n\sum_{j=1}^m[i\times j\leq x]$，其中$[expression]$当表达式$expression$为真时值为1，否则值为0。

推导上式，可得：

由于$n$比较大，直接计算上式复杂度过高。

注意到$\lfloor\dfrac{x}{i}\rfloor$可能的取值只有大约$\sqrt x$种，可分块计算，时间复杂度$O(\sqrt{k}\log{k})$。

F. 数独游戏

这是本场比赛的签到题。由题意，棋盘的每一行都是数字1~9的一个排列，又数据保证每行最多只有一个元素未填，所以未填元素的值为1+2+...+9的和减去所在一行其余元素的值。

时间复杂度$O(n^2)$。

G. 变石 Alexandrite

考虑一束光的折射路径，可以发现只有两大类情况：“表面$\rightarrow$特殊晶格$\rightarrow\cdots\rightarrow$特殊晶格”（不射出）与“表面$\rightarrow$特殊晶格$\rightarrow\cdots\rightarrow$特殊晶格$\rightarrow$表面”（射出）。因此，分析光的折射路径，就相当于分析光经过的特殊晶格。

对于从同一方向进入某一特殊晶格的多束光，最终会从该特殊晶格的同一方向出射，因此我们可以简单地将从方向$dir$进入特殊晶格$i$的光最终的出射位置记作$dest[i][dir]$，这个状态的规模是$4\times obj$。对其进行求解时，记从特殊晶格$i$折射后的方向为$dir'$、折射后下一个到达的特殊晶格为$j$（这可以通过预处理得到），那么求$dest[i][dir]$就相当于求$dest[j][dir']$，使用记忆化搜索可以完成求解。本题需要对于四个方向分别处理，比较考验选手的代码能力与实现技巧。

本题存在一个加强问题，可以在同规模数据下支持两类操作（$q=1\times 10^5$）：动态添加/删除特殊晶格与进行查询。出于平衡整体难度的考虑没有进行加强，但也欢迎选手在赛后进行思考与交流。

H. 谱面改造

本题是一个比较简单的构造题。假设目前在重新摆放第$i$个按键，所有轨道中最后一个按键的时间为$last_k$（$1\leq k\leq n$），则应当将其摆在$last_k$最小的轨道。那么最优的$min\_gap$就等于$min\left\{sorted\_t[i]-sorted\_t[i-n]\right|n+1\leq i\leq m\}$。

这可以通过反证法进行证明，假如存在另一个按键$j$（$t_j>t_i$）与轨道$k'$（$last_{k'}>last_k$），使得$i$摆放在$k'$、$j$摆放在$k$的结果更优，那么按键$i$、$j$分别与所在轨道上一个按键的gap为$t_i-last_k'$和$t_j-last_k$，与之前的构造方案相比，有$min(t_i-last_{k'},t_j-last_k)=t_i-last_{k'}<min(t_i-last_k, t_j-last_{k'})$，一定会使得$min\_gap$变小，故不存在这样的$j$与$k'$。

I. 解锁游戏

两绳之间交叉为一对二维偏序关系。

对于每条绳子$\{a_i,b_i\}$，不妨按照其中一维排序，设排序后另一维序列为$\{c_n\}$，原问题等价于修改若干个$c_i$使得排序后整个$\{c_n\}$单调不降。

考虑哪些绳子不需要改动，若两条绳子在$\{c_n\}$中构成逆序对，则至少有一条绳子需要改动，因此所有不需要改动的绳子在$\{c_ n\}$中位于一个单调不降的子序列上，设$cnt$为不需要改动的绳子数，则$ans_{min}=n-cnt_{max}$，求$\{c_n\}$中最长不降子序列即可，时间复杂度$O(nlogn)$。

J. 光之桥

本题等价于在一张带权图中存在若干个节点，它们之间可以任意添加至多$q$条固定权值的边，因此可以用分层图来解决。因为$q$至多为9，因此整个分层图至多为10层。对于第$i$层到第$i+1$层，可以在这两层图上的$k$个特殊节点间都添加一条权值为$w_i$，从第$i$层指向第$i+1$层的有向边。最后对于分层图求最短路即可。整体复杂度为$O((m+k^2)q)$。

K. 迷失游乐园

首先考虑一个 $O(k*k!+n+m)$ 的做法：

枚举所有的序列 {$c_1,c_2,...,c_k$}，一共 $k!$ 个，下面考虑如何快速判断一个序列是否合法。

对于每个点 $u$ ,假设其保留的边为 ($u,e_u$) 。因为每个顶点的出度都为 $1$, 所以如果可以做到每个顶点的出度也为 $1$，就可以让留下的边形成若干个环，从而达到题目要求。反之，如果存在某个点 $v$ 入度为 $0$，显然不满足题目要求。每个顶点的出度都为 $1$，相当于所有 $e_u$ 互不相同，即 $e_u$ 并集为全集{1,2,...,n}，那么我们就可以说这是一个合法序列。

上述判断方法可以使用hash加速，给每个节点随机一个值 $val_i$， 我们只需要判断 $val_{e_1} \oplus val_{e_2} \oplus ... \oplus val_{e_n}$ 是否与 $val_1 \oplus val_2 \oplus ... \oplus val_n$ 相同即可。

对于每个出度 $i$， 预处理不同 $c_i$ 时，对应顶点保留的出边的异或和，即可实现一个 $O(k*k!+n+m)$ 的方法。

下面考虑加速上述算法： 可以发现，我们枚举 $c_1$~$c_9$ 的值并不会影响到 $c_{10}$~$c_{14}$ 对最总异或和的贡献，所以可以使用中途相遇法，先枚举$c_1$~$c_9$的值，再枚举 $c_{10}$~$c_{14}$ 的值，最后使用 map 将上述两组哈希值合并。 总的时间复杂度为 $O( \sqrt{k!} \times log(k!)+n+m)$ 。

L. 五子棋

输出1，需要下一手无法获胜，并且不论自己怎么下，对方下一步都能五子连珠。由于棋盘太小，所以完全可以暴力枚举下在每个空格。如果下在某处后，我方直接胜利，那么输出0，如果存在少于两个地方，对方下子后可以五子连珠，输出0，其余情况输出1。如果只有1处，那么我们下一步下在那里，棋局必然可以继续。

M. Crystal Gravity

以下给出一种可行的构造方案。

将$\dfrac{n(n+1)}{2}$个点分成$n$组，每组$n$个顶点。

首先对每组内部的顶点两两之间连一条边。

此时第$i$组的顶点度数为$i-1$，接下去只需对每个顶点和不同组的一个顶点连一条边，并且保证组和组之间连通。

然后依次将第$n$组的每个顶点和前$n-1$组的一个顶点连一条边，使得组和组之间连通。

此时每组内需要连边的顶点个数分别为$0,1,2,\cdots,n-2,1$，可以证明$n-2$不大于剩余顶点个数的一半，因此一定有解，贪心地连边即可。

把以上三步组合起来即可得到一种可行的方案。