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

夏季赛命题组

A. Simple A / B Problem

C++ 或 Java 使用题述类型，读入两个整数并输出整除结果即可，注意特判除 $0$ 与范围内最小值除 $-1$ 两个会导致浮点异常的情况。

Python 根据题述整除定义实现一遍即可。

B. 奖杯上的图案

首先求出所有交点（可直接计算 $y=kx+b$ 与 $x=b$ 两种直线），然后绕一圈连起来，注意最后可能是绕一圈的顺序是顺时针，用分割成三角形求叉积的方法求多边形面积后取绝对值即可。

C. 经典的传统题

倍增多倍 c 备用，后根据所需长度的二进制分解结果拼接对应多倍 c 即可，即实现基于字符串拼接的“快速幂”（即反复平方法）。

D. SEU

首先根据 $0$ 的联通性判断出所有的 e，然后根据连通块中心附近 $1$ 的数量区分 s 和 u。

E. 城市驻军

树上枚举每个点作为所选集合的重心，随后搜索到重心距离相等的点，即可计算答案。

F. 小 Q 的数列

维护两个大小相等的大根堆和小根堆，其中较小的元素放在大根堆中（当前要求的为当前两堆元素集合并的中位数），每次累加堆顶元素即可。

G. 简单的色子

根据六种旋转方式进行 BFS 或带限界的 DFS 即可。

H. 挖岩石

首先明确一点，我们不会无缘无故消一个方块，也就是说消方块的地方一定与人的活动范围有关。所以我们不需要知道具体地图变成什么样了，只需要知道人在当前行的活动区间是多少。

于是就可以进行 DP。用 $f[i][l][r]$ 表示目前人走在第 $i$ 行，可以活动的区间是 $[l,r]$ 转移分 $4$ 种：

1. 直接走到 $l-1$ 或向左跳
2. 直接走到 $r+1$ 或向右跳
3. 自左向右挖洞，在洞的右端跳
4. 自右向左挖洞，在洞的左端跳

但是这样有漏洞，比如：

######
...###

然后挖洞的区间是 $[1,5]$ 并在 $5$ 处跳，之后人在第 $2$ 层的活动区间是 $[4,5]$，并会判断出不能向左跳，这是因为上面岩石挡住了，但这个实际上这个岩石已经被消去了，但这个信息丢失了。

所以需要改进状态 $f[i][l][r][0\sim 1][0\sim 1]$ 表示人活动区间的左边是否是空，右边是否是空,复杂度 $O(N^5)$。