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

冬季赛命题组

序号	题名	预估难度	实际情况
A	毒瘤的账单	简单	13/28
B	阿纬和蓝胖	较难	0/0
C	Hello_Classroom	一般	7/10
D	君日本语本当上手	简单	13/20
E	小雅米的无向图	一般	9/9
F	毒瘤的清洁工	一般	3/9
G	Hello_Bill	简单	12/17
H	毒瘤的车位	较简	4/7
I	小雅米的摩天大厦		7/9
J	空间折叠		8/11
K	Hello_Subway	简单	27/27
L	影~流~之~主	简单	27/27

A. 毒瘤的账单

容易发现，其实每一条支出对答案的贡献，只和小数点后第三位有关，当作字符串读入处理即可。

注意，若使用 double 类型直接处理可能会由于精度问题导致错误。

B. 阿纬和蓝胖

我们设获得 $n$ 颗宝石并且当前为可以获得宝石的状态（即已经连续多重施法至少 $t$ 次）的期望施法次数为 $f(n)$ 。 $f(n)$ 可以由 $f(n-1)$ 推得。当我们已经获得了 $n-1$ 颗宝石后，下一次施法时，我们有 $p$ 的概率再一次多重施法，获得 $n$ 颗宝石；而在剩下 $1-p$ 的概率里，计数器清零，我们要多获得一颗宝石的期望是 $f(1)$ 。于是有

f(n)= p [f(n - 1) + 1] + (1 - p) [f(n - 1) + 1 + f(1)]

整理得

f(n)= f(1) + (n - 1) + (1 - p) (n - 1)f(1)

所以我们的目标变为求 $f(1)$ 。

设 $f(1) = k$ , 考虑下一次没有多重施法为第 $i$ 次。

当 $1 \leq i \leq t$ 时，概率为 $p ^ {i - 1} (1 - p)$ , 此时前 $i$ 次施法全部无效，必须重新开始计数，所以期望施法次数为 $i + t$ 。

当 $i > t$ 时，概率为 $p ^ t$ ，此时已经连续施法 $t$ 次，可以获得一颗宝石，期望施法次数即为 $t$ 。

综上，可得出

k = \sum_ {i=1} ^ t p ^ {i - 1} (1 - p) (i + k) + p ^ t \times t

化简，有

k = \frac{1 - p^t}{(1 - p) \times p^t}

带入上面式子即可得出 $f(n)$ 。题目中需要用到快速幂和逆元，逆元可以通过扩展欧几里得或者是费马小定理求出。

C. Hello_Classroom

构造题。构造方式有很多，这里给出其中一种。

考虑每一行，若该行无选手则跳过。若该行有选手，则从左到右进行扫描，将从该选手开始，一直到下一名选手之前的位置划分给该选手，再将第一名选手之前的位置划分给第一名选手。

再考虑每一列，从有选手的行开始，一直到下一个选手之前的行都与该行相同。对于最上面一行前面的空行都与第一个有选手的行相同。

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

D. 君日本语本当上手

注意区分每种替换规则，之后进行模拟即可。

E. 小雅米的无向图

对每一个连通分量连一棵树即可。

另外不妨可以对有向图的情况进行拓展思考。(提示：对每个强连通分量连一个环后缩点、用拓扑序进行处理)

F. 毒瘤的清洁工

解法1

耐心地分类讨论坐标关系的各种情况，可直接得到结果。

解法2

在以下的描述中，我们将坐标系下，满足 $x,y$ 均为整数的点 $(x,y)$ 称为格点。即设想坐标系下有一个网格，所有的格点对应所有的整点。如果坐标范围很小，我们只需要用一个二维数组暴力模拟矩形染色的过程即可。

注意，由于这里需要同时考虑格点和小方格内部的点，可以使用如下技巧：将原始格点坐标 $(x,y)$ 映射到新坐标系下的点 $(2x,2y)$ ，将小方格 $(x,y)-(x+1,y+1)$ 映射到新坐标系下的点 $(2x+1,2y+1)$ ，将线段 $(x,y)-(x+1,y)$ 映射到新坐标系下的点 $(2x+1,2y)$ ，线段 $(x,y)-(x,y+1)$ 映射到新坐标系下的点 $(2x,2y+1)$ 。那么这样，原始地面上每一个可以被独立操作的区域都被映射到了新坐标系下的一个点，换言之，对原始地面的任何一个操作，都可以被描述为对新坐标系下格点的操作。我们用一个二维数组表示这些格点的状态，然后就可以暴力模拟了。

回到原问题，考虑到总共只有三个矩形，我们可以对坐标进行离散化，然后转化为坐标范围很小的问题。

G. Hello_Bill

构造题。构造方式有很多，这里给出其中一种。

首先统计三人总共花了多少钱，设三人分别花费 $a_1$ , $a_2$ , $a_3$ ，三人花费的平均数为 $a_{ver}$ 。则可以通过 $a_1$ 给 $a_2$ ， $a_2$ 给 $a_1$ 两次操作，使得 $a_1$ 等于 $a_{ver}$ 。再通过 $a_2$ 给 $a_3$ ， $a_3$ 给 $a_2$ 两次操作，使得 $a_2$ 和 $a_3$ 达到平均数。

时间复杂度为求和的复杂度，即 $O(n)$ 。

H. 毒瘤的车位

由于题目保证每一行、每一列有障碍的车位数量都恰好是 $1$ ，不难发现，对输入矩阵，交换任意的两行或者两列，不影响答案。这意味着输入矩阵一定可以通过行与行的互换，变成一个单位矩阵。

容易发现输入矩阵其实没有用处，本题答案只和 $n$ 有关。不妨设 $D_n$ 为矩阵为 $n$ 阶时的答案。

（自此，你可以通过枚举算法来找出数列 ${D_n}$ 的前几项，然后猜出递推规律，暴力递推解决该问题）

如果我们把输入矩阵化成一个单位矩阵，就会发现，本题求的就是 $N$ 的全错位排列数。即求一个排列 $P_1,P_2,...,P_n$ ，要求对任意 $i$ 有 $i \neq P_i$ ，有多少种方案。设 $D_n$ 为矩阵为 $n$ 阶时的答案，那么 $D_1 = 0, \ D_2 = 1$ ，且

\ D_n=(n-1)(D_{n-1}+D_{n-2}) \ \ (n \geq 3)

注意，由于答案较大，本题中需要使用 long long 类型来存储一些数值。

当然，本题也可以使用状态压缩动态规划来解决。

I. 小雅米的摩天大厦

首先考虑第一座大厦，如果为高度为奇数，那么就要第一座第二座大厦一起增加 $1$ ，然后这样考虑第二座、第三座...这样处理完所有的塔后如果增加的高度超过了应有的高度或者还有一座奇数高度的塔则输出NO，否则为YES

J. 空间折叠

感性上穿梭一次可以压缩一个维度，穿梭两次可以压缩两个维度，那么答案即为 $min(|x_s-x_t|,|y_s-y_t|,|z_s-z_t|)$ 。

下面我们来证明这个结论。

我们可以分别枚举两次穿梭走的是哪两个维度，因为距离是取最小值的所以在 $9$ 种情况中取最小值即可。

假设我们两次走的都是相同的维度，不妨设走的都是 $x$ 轴与 $y$ 轴那么走的距离为 $\sqrt{(x_s-x_p)^2+(y_s-y_p)^2}+\sqrt{(x_t-x_p)^2+(y_s-y_p)^p}$ 上式最小值为 $\sqrt{(x_s-x_t)^2+(y_s-y_t)^2}$ 。假设走的两次维度不同，不妨设第一次走了 $x$ 轴与 $y$ 轴，第二次走了 $x$ 轴与 $z$ 轴那么走的距离为 $\sqrt{(x_s-x_p)^2+(y_s-y_p)^2}+\sqrt{(x_t-x_p)^2+(z_t-z_p)^2}$ 上式最小值为 $|x_1-x_2|$ 。

综上，答案为 $min(|x_s-x_t|,|y_s-y_t|,|z_s-z_t|)$

K. Hello_Subway

模拟题。

解法1

简单的分类，可以将问题分为 $3$ 种情况。

第一种是套票的平均单次价格大于等于单程票的平均价格，显然全买单程票划算。

否则套票平均单价便宜，要么对与 $\frac nm$ 的部分买套票，对于剩余的部分买单程票，要么全买套票(可能会存在套票买多反而便宜的情况，考虑样例 8 3 3 5 四个数)。

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

解法2

因为数据范围很小，枚举所有盒饭的单程票和多程票的取值，最后得到最小的那个也是答案。