第一届东南大学大学生程序设计竞赛（春季）暨CCPC东南大学校队选拔赛 - 初赛 题解

春季赛命题组

A. 住宿计划

枚举ryh的位置，二分答案，二维前缀和优化。时间复杂度 $O(n^2\times \log n)$。

注：本题存在$O(n^2+\log^2(n))$的做法

B. 超级水仙花数

我们可以搜索每个数字各有几个，用求和的结果与每个数字个数比较，可以在较快时间内求出答案，交表即可。

C. 你的名字

本题可以直接搜索解决，状态可用二进制位来压缩。考虑到有 $k$ 种钥匙，$k$ 最多为 $5$，我们可以用一个二进制数来表示当前身上携带钥匙的情况，那么最多携带情况一共有 $2^5 = 32$ 种，于是总的状态数最多有 $n \times m \times 32$ 种，然后从 $(1,1)$ 开始向四周扩展转移即可。注意每次取出的状态应该保证是最优的，所以我们用一个堆来维护当前所有状态，每次都取距离起点所花时间最少的状态转移即可。或者可以将各个状态能转移的建边，跑一边最短路即可。

D. 偷税吧，少年

由于解有了上下界而且都是整数，可以直接枚举解，求导判断重根，$k$ 阶导数等于 $0$ 就是 $k$ 重解。高精度或者方程两边同时对一个随机大素数取模都可行。

E. 简单的推导

若 $(u,v)$ 间是第一类边则连一条边权为 $0$ 的边，若 $(u,v)$ 间是第二类边则连一条边权为 $0$ 的边，否则不连边，BFS 求最短路即可。

F. 奇妙数

对较小情况进行暴力计算后得出规律或直接推到均可。非 $1\times 1$ 矩阵的答案为 $\min(n,\frac{m+1}2)+min(m,\frac{n+1}2)$。

G. 查寝时间

直接分类讨论日期的各种情况或者使用 Java 的 Calendar 类均可。注意 $2020$ 年的闰年，而 Calendar 类的 set 函数直接设置 DAY_OF_WEEK 不能保证时间仍在那周内，需要使用 add 等函数来替代实现。

H. 十分难题

对于前 $90\%$ 的数据，直接判断 $2\sim \lfloor \sqrt n\rfloor$的整数是否能被 $n$ 整除即可。而余下 $10\%$ 较难，这就是“十分”有“玄机”的含义。注意到题中包含样例，可直接判断之（或者读最后一位，判断是否为偶数）。这样只有一组不确定数据。注意一个直接且保证正确的算法极其困难，于是我们可以使用两个算法来解决问题，一个在这时输出 YES，另一个则反之，均提交后必有一提交正确。

I. 欲于辉夜之城起舞

本题比较简单。把中心点设出来，列出最后所求式子后展开求偏导即可得出答案。

J. 心里阴影

因为矩形不会相互包含，先将矩形按照 x 坐标排序，y 坐标一定是递减的。记 $f_i$ 为考虑了排序后前 $i$ 个矩形并且选了第 $i$ 个矩形的最大值，$f_i = \max(f_j+(x_i-x_j)\times y_i-a_i)$ 暴力转移即可。

注：本题存在线性解法。

K. 杂鱼们的悲惨命运

首先不考虑存在虎级怪人的情况，对于棋盘上每一个可达的点，假设 $t$ 时刻在 $(i,j)$ 的概率为 $p_{t,i,j}$，则可以求出该点对 $p_{t+1,i,j},p_{t+1,i,j+1},p_{t+1,i,j-1},p_{t+1,i+1,j},p_{t+1,i-1,j}$ 的贡献。

存在虎级怪人时，需去掉该时刻该位置的 $(t,i,j)$ 对周围的贡献。

L. 最终表白

首先去除所有所有环上的点以及从出发可以到到环的点，在剩余图上动态规划即可。

M. 头号玩家

本题相对较为复杂。首先看出这是一个最大流模型。考虑把每个契约地拆为两个点，一个入点和一个出点。将所有出点连向对应入点，容量为 $a_i$。对于两个相邻契约地 $u$ 和 $v$，我们将 $v$ 的出点连向 $u$ 的入点，容量设为 $a_v$，将 $u$ 的出点连向 $v$ 的入点，容量为 $a_u$。将源点连向所有出点，容量为 $a_i$，将所有入点连向源点，容量为 $b_i$，然后跑一边最大流，如果有解则最大流等于一开始所有人数和。只需要在残留网络上查看对应边流量输出即可。注意特判第一天和第二天的总人数是否相同！