KEYENCE Programming Contest 2019 题解

AutumnKite

题解AtCoder

发布于：2020年10月19日

次浏览

比赛地址

ABC 就不写了。

D - Double Landscape

题意

在一个 $N\times M$ 的网格中不重复地填入 $1$ 到 $N\times M$ 的整数，使得第 $i$ 行的最大值为 $A_i$ ，第 $j$ 列的最大值为 $B_j$ ，求方案数。对 $10^9+7$ 取模。

$N,M\le 1000$

题解

将 $A,B$ 从小到大排序，显然不影响答案。

从大到小填数，分为若干种情况：

若当前数是超过两行或超过两列的最大值，则一定无解。
若当前数是恰好一行和一列的最大值，则必然填在交界处。
若当前数是恰好一行或恰好一列的最大值，则必然填在该行或该列。
否则，该数可以填在最大值大于等于当前数的任意位置。

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

代码

E - Connecting Cities

题意

有一张 $N$ 个点的无向完全图，第 $i$ 个点有点权 $A_i$ 。定义一条边 $(i,j)$ 的边权为 $|i-j|\times D+A_i+A_j$ 。求最小生成树权值。

$N\le 2\times 10^5$

题解

直接套用 Boruvka 算法。

每次合并时，对于每个点 $i$ ，可以对 $j < i$ 和 $j > i$ 两种情况分别求出不在同一连通块的最小边。

只需要正反扫一遍，维护最小值和与最小值不在同一连通块的最小值即可。

时间复杂度 $O(N\alpha(N)\log N)$ 。

代码

F - Paper Cutting

题意

有一个 $(H+1)\times (W+1)$ 的网格，有 $H$ 条水平线和 $W$ 条垂直线。

你需要执行 $K$ 次操作，每次沿一条水平线或垂直线将网格切开。定义一次操作的权值为做完该操作后网格被分成的块数。

定义一个操作序列的权值为 $K$ 次操作的权值和。

求所有操作序列的权值之和。对 $10^9+7$ 取模。

$H,W\le 10^7$

题解

考虑求出第 $k$ 次操作对答案的贡献，为 $k!(K-k)!\binom{H+W-k}{K-k}\sum_{i=0}^{k}\binom{H}{i}\binom{W}{k-i}(i+1)(k-i+1)$

考虑优化后面部分，有 $\begin{aligned} & \sum_{i=0}^{k}\binom{H}{i}\binom{W}{k-i}(i+1)(k-i+1) \\ =~&(k+1)\sum_{i=0}^{k}\binom{H}{i}\binom{W}{k-i}+\sum_{i=0}^{k}i(k-i)\binom{H}{i}\binom{W}{k-i}\\ =~&(k+1)\binom{H+W}{k}+HW\binom{H+W-2}{k-2} \end{aligned}$