2018-2019 XIX Open Cup, Grand Prix of Korea

> 感谢 @jiangly 大神指导 **Link** : [CF gym](https://codeforces.com/gym/102059) ## B. Dev, Please Add This! **题意** ： 给出一个 $n\times m$ 的二维矩阵，每个位置可能是空地或者障碍物。某些空地上有星星。 在某个**给定的**空地上放一个球，接下来可以将这个球按如下规则移动 ： - 选择 上下左右 其中一个方向 - 将球一直滚动，直到碰到障碍物或者边界 若球经过某个有星星的空地，则可以将其收集。判定是否存在某种方案能收集到所有星星。 $n,m\leq 50$ ，时限$\texttt{2s}$。 ------------ 不难发现，除了从起点出发的第一步，球在移动前后的点一定靠着墙。 于是，我们讨论第一步的方案，并将起点转化到靠墙点上。 先不考虑球滚动中途经过的点。建立一张有向图 $G$ （只考虑靠墙点），若能在一次移动内从 $u$ 到 $v$ ，则连边 $u\rightarrow v$。 每条边滚动中途可能会经过若干星星。 将每条边看做一个点，建立新的有向图 $G'$。对于边 $l_1,l_2$ ，若走过边 $l_1$ 后能立即走过 $l_2$ ，则连边 $l_1\rightarrow l_2$。 由于 $G$ 中每个点的出边条数是 $O(1)$ 的，这新图 $G'$ 的边数仍然是 $O(nm)$ 的。 计算出每条边（新图的点）能获取的星星集合，然后就是要求出一条从起点出发的路径，使得星星集合的并集为全集。 然而这并不是一个容易的问题。 进一步发掘问题的特殊性质，能够发现，某个星星只能被对应的一条横边或一条竖边经过，于是可以考虑 $\text{2-SAT}$。 对于 $l_1,l_2$ ，若两者的交点处存在星星，则连边 ： - $\neg l_1\rightarrow l_2,\ \neg l_2\rightarrow l_1$ 此外，给 $G'$ 跑传递闭包。若 $l_1,l_2$ 不可达，则连边 $l_1\rightarrow \neg l_2,\ l_2\rightarrow \neg l_1$。 （由于 $G'$ 的边数和点数同阶，直接搜索即可做到 $O(n^2m^2)$ 求传递闭包） 最后用 $\text{2-SAT}$ 判定即可。复杂度 $O(n^2m^2)$。 ```cpp ``` ## C. Dstorv **题意** ： 在数轴上，有若干个红球和蓝球，给出他们的初始位置。 接下来，所有红球以 $1$ 的速度向左移动，所有蓝球以 $1$ 的速度向右移动。 若某一对红球与蓝球相撞，则有 $p$ 的概率红球保留，蓝球消失；否则蓝球保留，红球消失。 在等待足够长的时间后，不再会有碰撞发生。 求此时**恰**有 $a$ 个红球与 $b$ 个蓝球未消失的概率。答案对 $10^9+7$ 取模。 $n\leq 5000$ ，时限$\texttt{1s}$。 ------------ 不难发现，最终剩下的蓝球与红球在原序列不会是交错的。 对于每个前缀统计消完后剩余 $a$ 个红球的概率，对每个后缀计算消完后剩余 $b$ 个蓝球的概率。 枚举分界线后，将上述两者相乘求和即可。 ## D. Dumae **题意** ； ## K. Interesting Drug **题意** ：