第二届东南大学大学生程序设计竞赛（冬季） - 题解 - 帖子

第二届东南大学大学生程序设计竞赛（冬季）命题组

初赛

A. 三带二

将 $5$ 个数从小到大排序，若满足以下两种情况之一：

前三个数分别相同，后两个数分别相同。
前两个数分别相同，后三个数分别相同。

满足任意一种情况输出 yes，否则输出 no。

B. 机械姬哥

本题做法是利用矩阵维护当前所做的变换，对于某个点的查询只需要用该点原始坐标乘上矩阵即可。请注意本题所有数据均可用整数运算完成，因此不需要使用浮点，以避免浮点误差。

C. 姬哥的通信网

记 $f_{i,j}$ 为节点 $i$ 向节点 $j$ 的通信次数，则本题转化为了二维区间+查询问题。可以用二维树状+差分维护解决。

注意到本题 $nq=10^8$ ，因此也可以对于每个通信按行做暴力差分，对于每个查询按列暴力求和即可。

请注意本题中 $f_{i,i}$ 需要特判为 $0$ ，因为节点无法与自己通信。

D. 简单的数学题

$\sum_{i=1}^mC_{a_i}^2=\sum_{i=1}^m\frac{a_i \times (a_i-1)}{2}=\frac{1}{2}\sum_{i=1}^m(a_i^2-a_i)=\frac{1}{2}\sum_{i=1}^ma_i^2-\frac{n}{2}$ ，显然，当 $a_i$ 取 $\underbrace{1,1,...1}_{n-1个1},n-m+1$ 时取最大值， $a_i$ 取 $\underbrace{\lfloor \frac{n}{m} \rfloor ,\lfloor \frac{n}{m} \rfloor ,...,\lfloor \frac{n}{m} \rfloor}_{n \mod m 个}$ 时取最小值。

E. 更简单的数学题

假设 $n=\prod_{i=1}^k p_i^{a_i}$ ，其中 $p_i$ 为 $k$ 个不同的质数,由乘法原理可知 $n$ 的因子数量为 $\prod_{i=1}^k (a_i+1)$ 。所以预处理所有质数，将每个数质因数分解，求出因子数量即可。

F. 环游世界

给定一张无向完全图，每个点给定一个点权，每条边的权值是它连接的两个点的点权的差的平方，求权值和最小的哈密顿回路。

由于哈密顿回路一定经过每一个点，所以每个 $x_i^2$ 必定恰好在结果中出现两次，因此我们只需要最小化交叉乘积项，即最大化 $\sum x_i x_{i+1}$ 即可。

将所有边权从小到大排序后，显然最终的结果一定是 $x_1x_2+x_1x_3+x_2x_4+x_3x_5+...+x_{n-2}x_n+x_{n-1}x_n$ 。

G. 小塔

首先，对于整张图，我们可以直接采用 Floyd 算法求出每两点之间的最短路。

然后，我们使用动态规划求解。令 $F[i][j]$ 为小塔处于 $i$ 号女生宿舍，且拜访状态为 $j$ 时的最少时间，其中对于 $j$ ，它用二进制表示时从低到高第 $k$ 位为 $1$ 代表已经拜访过编号 $k$ 的女生，反之没有。这种方法叫做状态压缩。

这样很容易就可以通过枚举下一次的拜访女生的编号来进行更新，注意考虑 $f=0$ , 即某次拜访时女生不在宿舍的情况即可。

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

H. 赛场选择

按题意模拟即可。

决赛

A. IQ test

本题为 Codeforces 25A 原题，原题链接为 https://codeforces.com/contest/25/problem/A。

因为时间紧迫加上这题真的很好就搬了过来(逃)。

考虑做法，只有一个数与其他数的奇偶性不同。

特别的我们发现，对于这个与众不同的数，它与周围 $2$ 个数的奇偶性不同，且周围这 $2$ 个数的奇偶性相同。

因此我们只需要枚举连续的三个数，若三个数的奇偶性两两相同则跳过。否则我们要找的数一定在这三个数中，再条件枚举即可找到答案。

本题输出由原题输出不同值的下标变成输出不同的值，稍加了一些改动，目的是让某种特殊的排序算法也可顺利通过该题。

B. 姬哥与Jiva

本题为大模拟题。只需要对每个类名做一下字符串哈希即可，可以使用 map 或 unordered_map 完成，也可以直接用其读入序号替代。对于读入的每个 class，将其下所有成员添加到该类下，并将其父类所有成员也添加到该类下(注意去重)，最后统计每个类下的成员数量即可。

C. 姬哥大逃亡

本题为求取球面上两点之间最短距离。可以证明：球面两点最短距离即为这两点与球心所构成的圆上这两点之间劣弧的长度。因此本题只需求取起点与终点之间的夹角，最后乘以球半径即为答案。

D. 姬哥与考试周

可以发现，姬哥能和每个特产谈心要求每时每刻谈心的天数 $\geq$ 分手的天数，故方案数即为卡特兰数。

解法1

由于 $n\leq 1000000$ ，故可通过递推预处理所有卡特兰数。记 $n$ 个特产的方案数为 $F(n)$ ，则有 $F(n)=2\frac{F(n-1)(2n-1)}{n+1}$ 。

其中取摸意义下，除 $n+1$ 即为乘 $n+1$ 对模数的乘法逆元，可通过递推预处理、费马小定理、扩展欧几里得等任意方法求得。

解法2

考虑卡特兰数的一个通项公式，记 $n$ 个特产的方案数为 $F(n)$ ，则有 $F(n)=\frac{\binom{2n}{n}}{n+1}$ ，其中 $\binom{n}{m}$ 为组合数。则我们可以预处理 $n!$ 取模，以及其逆元。读入 $n$ 后计算组合数即可。

E. 姬哥做水题

本题实际为寻找序列中是否存在两个数之和等于 $k$ ，可以使用双指针法扫描求取。

本题也可使用查找值的方法解决。但需注意 $a_i+a_i=k$ 的情况，因为两个数的下标必须不同。另外本题对 map 做法进行了卡常(使用 map 进行查找可能会超时)。

F. Dark Matter

对于每组数据，注意到 $n\leq40$ ，暴力枚举每个数删或者不删的复杂度是 $O(2^n)$ 。

考虑优化暴力做法。将数列均分成两部分，每部分的长度为 $\dfrac{n}{2}$ ，分别对这两部分进行暴力枚举，记录下所有可能的乘积，此时两部分分别有 $O(2^{\frac{n}{2}})$ 个数。

现在原问题等价为：在两个数列中分别取出一个数，使其乘积不大于 $L$ 且最大。分别对两个数列排序后双指针枚举或者二分查找最大的乘积，时间复杂度为 $O(2^{\frac{n}{2}}\log2^{\frac{n}{2}})$ 。

总时间复杂度为 $O(T2^{\frac{n}{2}}\log2^{\frac{n}{2}})$ 。

G. 刀斯林计划

题目要求对于 $n$ 个点的环套树的最大独立集。

借由一遍 DFS 我们可以求得处于环上的所有点的序列。然后我们先向下进行动态规划。令 $F_1[i][j]$ 为以 $i$ 为根的子树在 $i$ 状态为 $j$ 时所能取点的最大个数， $j$ 为 $0$ 时代表不取 $i$ ，为 $1$ 代表取 $i$ 。只需注意相邻两层的点不能都取即能轻松计算。

然后考虑环上的情况，和之前类似维护一个 $F_2[i][j][k]$ 。注意因为是环，所以要考虑到序列上第一个点和最后一个点不能取的状态相同，所以还需一个 $k$ 来维护第一个点的状态。

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

H. 取数游戏

枚举成为答案的数是哪一个，判断其合法性，即必须在它之前拿走的数的个数是否不超过要求。在合法的所有数中，取最大的即可。