KEYENCE Programming Contest 2019 题解
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} \]
时间复杂度 \(O(H+W)\)。
