GYM102439 2018-2019 9th BSUIR Open Programming Championship. Semifinal 题解
jiangly
·
·
个人记录
A. Four minutes until BSUIR Open
用单调栈维护对速度有限制的摄像头，最后枚举每对相邻的摄像头，解二次方程得到所用时间。时间复杂度 O(n)。
B. Varvara and matrix
由于每行每列最多只有一个 0，所以限制只有两种形式：
- 第 i 个 0 不能为 A (B)。
- 第 i 和 0 和第 j 个 0 不能同时为 A (B)。
转化为 2-SAT。建第一种边时可以用 bitset 优化。时间复杂度 O(nm(1+\frac{\min\{n,m\}}w))。
C. Cockroach Racing
$$
dp[l][r][i][j]=\sum_{l\le k\le r}dp[l][k][i+1][0]\cdot dp[k][r][i][j+1]
$$
总和的转移类似。时间复杂度 $O(10\cdot n^3m)$。
#### D. Light show
加向量的时候维护最大的基即可。时间复杂度 $O(nq(1+\frac{\min\{n,q\}}{w}))$。
#### E. Small business
简单分类讨论即可。
#### F. Prime or number
显然充要条件是 $n-n\bmod 2$ 的二进制表示有恰好一个 $1$。
#### G. Sequence exploration
当 $n\ge 35$ 时，末 $1000$ 位的循环节为 $4$。时间复杂度：$O(35\cdot m)$。
#### H. Nonfibonacci numbers
发现限制其实是十进制表示中不包含 $1$, $2$, $3$, $5$, $8$。数位 DP，时间复杂度 $O(\log n)$。
#### I. Equal Mod Segments
记 $C=\max\{a_i\}$。对于一个固定的左端点，$a_l\bmod a_{l+1}\bmod\cdots\bmod a_r$ 相等的极长区间个数只有 $O(\log C)$，倒过来同理。对每种不同的数分别扫描线即可。时间复杂度 $O(n\log C\log n)$。
#### J. Boedium
对每个人算出他命中 $0,1,\ldots,20$ 发子弹的概率。枚举 $1$ 号选手命中的子弹数，简单 DP 即可。时间复杂度 $O(20^2\cdot n)$。
#### K. Innovations
每条边分别算贡献。一条边最多被修改 $\log\log w$ 次，用并查集维护还未变成 $1$ 的边即可。时间复杂度 $O(n\log \log w+m\alpha(n))$。
#### L. The only winner
假设要算每对数的和都 $\le m$ 的方案数。令 $l=m/2$，则 $l+1,\ldots,2n$ 的每个数都匹配了 $1,\ldots,l$ 中的某个数，剩下的任意匹配，因此方案数为 $\frac{(m-2n)^{2n-l}(2l-2n)!}{(l-n)!2^{l-n}}$。而要求有恰好一对数的和为 $m+1$，其余都 $\le m$，容易算出方案数为 $\frac{(2n-m+l)(m-2n)^{2n-l-1}(2l-2n)!}{(l-n)!2^{l-n}}$。对 $m$ 从 $2n$ 到 $4n-2$ 求和即可。时间复杂度 $O(n\log n)$。