第七届东南大学短码竞赛 - 题解 - 帖子

第七届东南大学短码竞赛命题组

初赛

A. 加法问题

因为 $\sum_{i=1}^n{a_i \times 10^n} \equiv \sum_{i=1}^n{a_i}(mod\ 9)$ ，所以我们把 $n$ 对 $9$ 取模即可。

B. 跳舞机

一个较为简便的判断方法是利用 ASCII 码，'A' 与 'C' 的 ASCII 码都不是 $2$ 的倍数，'B' 和 'D' 都是 ASCII 码是 $2$ 的倍数。

C. 回文方阵

注意要分 $n$ 的奇偶性讨论

$n$ 为奇数时，中心元素只可以出现 $1$ 次，对称轴上的元素可以只出现 $2$ 次，其余元素都是都为 $4$ 个为一组出现的。
$n$ 为偶数时所有元素都是 $4$ 个一组出现的。

本题代码较长，有处诸多细节以优化。例如将奇偶的情况合并在一起等方法都可以缩短代码长度。

D. 购物

直接使用 C++ 中的 std::set 内置的 lower_bound 函数可以直接达到题目的要求。

E. 数列求和

先求出 $f_n$ 的前 $m+2$ 项，再求出 $s_n$ 的前 $m+2$ 项。由于 $s_n=\sum_{i=0}^{m+1}{b_in^i}$ ，并且已经求出 $s_n$ 的其中 $m+2$ 项，即可利用各种方式（差分组合数，拉格朗日插值，牛顿插值）求出 $s_n$ 的表达式，然后带入即可求出其中的某些项。

决赛

A. 酒店隔离

本题要分许多种情况进行讨论。首先排除没有 'X' 的情况，答案为 $n-1$ 。

我们先把所有连续的 '.' 提取出来，要分靠边和在两个 'X' 之间的两种情况考虑。小雅米和小雅女可以在同一段，或者在两个不同的段中。

本题代码较长，有许多可以优化代码的地方。例如如何提取连续的 '.'，如何找最大值以及次大值，如何处理两个可能存在的靠边段等。

B. 发电机

如果 $p > \sum_{i=1}^{n}a_i$ ，则永远运行。

现在考虑不能永久运行的情况。如果给定时间 $t$ ，可以简单判断多智体系统能否在 $t$ 的时间内运行。如果假设最终答案为 $T$ ，小于 $T$ 的时间都能运行，大于 $T$ 的时间都不能运行，满足单调性。可以二分时间 $t$ ，判断是否可行。最终达到精度要求。

C. 木棍

假设矩形的边长为 $a,b(a<b)$ ，则 $\frac{C^2}{S}=4(\frac{a}{b}+2+\frac{b}{a})$ ，现在就是比较 $\frac{a}{b}+\frac{b}{a}$ 的大小即可。

首先如果有一个长度木棍的数量大于等于 $4$ ，则选 $4$ 根这个木棍是最优的。

考虑其他情况，剔除数量为 $1$ 的木棍后，假设现在有 $a,b,c（a<b<c）$ 三个长度的木棍，显然选择 $a,b$ 或者 $b,c$ 比选择 $a,c$ 更优。所以对木棍进行排序，然后每次选择相邻长度的木棍，比较即可。

如果使用 c++ 答题，double 可能产生精度误差，所以要使用 long double 或者利用勾函数的单调性比较。

D.乘法问题

本题为自带高精度语言的签到题，只需要比较 $\prod_{i=1}^n{a_i}$ 是否为 $\prod_{i=1}^n{b_i}$ 的倍数即可。

对于其他语言，我们把 $a_n$ 和 $b_n$ 分解到质因数 $2,3,5$ 即可。

E. 级数求和

直接使用提示中的函数即可，或者暴力迭代很多次也可以通过。