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

第十七届东南大学大学生程序设计竞赛春、夏季赛命题组

初赛

A. 积为给定的数

对于每一个 $a_i$ 判断 $\frac S{a_i}$ 是否在数组内即可。判断方法可为排序后二分、平衡树、哈希等。亦可使用 “two pointers”。

B. Yami走迷宫

观察可知总共走 $\sum t_i$ 步，每个方向恰走 $t_i$ 步，顺序任意。故答案为 $\binom{\sum t_i}{t_1}\ldots \binom{t_{n-1}t_n}{t_n}=\frac{(\sum_{i=1}^n{t_i})!}{\prod_{i=1}^{11}{t_i!}}$ 。

C. 军费

对于任意素数的答案显然为 $n-1$ ，否则答案小于 $n-1$ 。

对于小于 $6$ 的情况可逐一验证，而大于 $6$ 偶数，因题设范围内的哥德巴赫猜想被验证成立，答案不小于 $n-2$ ；对于奇合数，其可被拆为 $3$ 个奇素数，故答案不小于 $n-3$ 。答案为 $n-2$ 的奇素数则必须被拆成两个素数，考虑奇偶性，其中一个素数必为 $2$ ，对另一数字进行素性判定即可。

素性判定可用暴力或 Miller–Rabin 方法。

D. 椿萧

观察简单的动态规划执行结果可知每次贪心增加消耗精力最少的敌人直到不能增加即可。

对于增加每个敌人所需消耗的额外精力值，可用对于每种 $A_i$ 的敌人分别构建线段树维护的方法解决。

E. 规划

枚举 $x_k \ne 0$ 的数目 $i$ ，则有

\sum_{i=0}^n \binom n i \binom {p-1} {i-1} 2^i =\sum_{i=0}^n \binom n i 2^i \sum_{j=i}^p \binom {j-1}{ i-1}=\sum_{i=0}^n 2^i \binom n i\binom p i

F. ddc的理想生活

\frac{t_1}{p_1}+\frac{t_2}{p_2}<=1

若满足上式条件，输出 YES，否则输出 NO。

该题要注意讨论分子分母分别为 $0$ 的情况。

G. ddc的千年等待

直接按自然数幂和公式计算即可。注意按照定义， $l > r$ 时答案为 $0$ 。具体公式可上网搜索（作为初赛问题），也可使用拉格朗日插值法或伯努利数等方式推得。

H. 三国杀

本题总共8种牌，摸2张牌则共计有64种情况。由于对方手中有一张未知牌，因此我方若摸到【桃】【闪】【无懈可击】这些防御牌则必然无法击杀对方；剩下的情况逐一判断即可。

决赛

A. 素数伴侣

本题是比较经典的二分匹配问题。显然两个大于2的数相加为素数意味着这两个数必为一奇一偶，因此可以将所有奇数归为左部，偶数归为右部，对于相加为素数的两个数之间连一条边，做最大二分匹配即可。素数的判定可以预先打素数筛，或是根号判素亦可。

B. 画饼

构造若干个互不相连的完全图即可。

C. 跑图

本题首先 Floyd 求出任意两点间的最短距离。注意到本题支线任务不超过 $5$ 个，且每个支线检查点不超过 $9$ 个，因此可以把当前的任务状态压缩为一个五位数 $D$ ， $D_i$ 表示第 $i$ 位数字，代表任务 $i$ 接下来需要前往该任务的第 $D_i$ 个检查点。则对于两个数 $D$ 和 $D'$ ，若 $D'_i=D_i+1(i\in [1,5])$ ，则 $D$ 可向 $D'$ 连接一条有向边，权值即为任务 $i$ 的第 $D_i$ 个检查点到第 $D'_i$ 个检查点间的最短距离。最后只需要求一遍最短路即可。

D. 断言

暴力枚举子集判断即可。

事实上，根据鸽巢原理容易证明命题永远为真，因此直接输出 YES 即可。

E. 两面包夹芝士

答案即为 $f(i,j)=\min_i\min_j{\min(|x_1-i|+|y_1-j|,|x_2-i|+|y_2-j|)}$ 在一矩形范围内的所有整点中的最大值。

可按绝对值内的表达式正负将矩形切成 $9$ 块，分别讨论每块中的极大值，容易发现极大值只在若干个特定点（具体在不同情况下不同）存在。分别求值后取最大值即可。

F. 超级回文数

本题首先通过差分前缀和（类似字符串哈希）维护整数 $n$ 的任意一个子串 $n_{l,r}\ mod\ 10^9+7$ 的值。然后用马拉车算法或者回文自动机求出 $n$ 中所有的回文子串，通过差分前缀获得对应的数值，最后累加取模即可。

G. 求和

预处理出所有区间的最小值后，进一步预处理出所有区间的答案，然后 $O(1)$ 回答询问即可。

H. Yami的守望

我们暴力预处理出每个时刻是否有人访问百货店，暴力处理的时间复杂度根据调和级数是 $O(nlogn)$ 的。

I. 我们联合

讨论子树上根节点是否驻军或是否已在防守范围内进行树上动态规划即可。

J. 传递性

可以把无向边拆成两条有向边，进而按所有边的始点作为维度构建线段树，每个点上存的即为以该点为始点的边的最值，每次询问即可转换为区间最值查询。

另一种编码简单的方法是给每条边随机赋权值，统计区间内以每个点为顶点的边的权值的异或和的异或和（可由 BIT 维护），判断异或和是否为 $0$ 即可(当且仅当满足题设条件时每条边恰被统计两次)。

K. 一决高下

将题目按照做题时间排序，yky按从小到大的时间做，ddc按从大到小的时间做，比较最终两者的题数和罚时即可。

L. 重组

统计出每个因子出现的个数，第 $i$ 个因子的个数记作 $q_i$ ，总的因子数的个数显然是 $tot=\prod_i (q_i+1)$ ，于是每个因子最终贡献的幂次为 $\frac 1 2 q_i tot$ 。算幂次时根据费马小定理，要对 $10^9 +6$ 取模，但是这里有个除 $2$ 很讨厌，考虑到 $q_i$ 和 $tot$ 中至少由一个能被 $2$ 整除，这里我们可以在计算过程中先对 $2(10^9+6)$ 取模。

M. 积为给定的数

本题解法很多，设 $pre_n = \prod_{i=1}^{n}$ 枚举 $l$ 再判断是否存在 $r$ , 使得 $pre_r=\frac S{pre_l}$ ,我们可以用取模的方式解决乘法溢出的问题。

或者排序后使用 “two pointers” 也可以避免溢出的问题。

本题还可以使用暴力枚举的做法，注意到我们最多乘 $log_2S$ 次非 $1$ 的数就一定会超过 $S$ ，所以我们可以枚举左端点 $l$ ,每次暴力跳到下一个非 $1$ 的数，时间复杂度 $O(nlogS)$ 。