CF1740G Dangerous Laser Power

CF1740G


这场 cf 的时间非常阳间,题目质量也比较好做起来很顺手,但是正好和昨天的 CSP 出现了冲突,导致我没有办法现场参加(错过了上大分的机会😢)

感觉有点偏手速场(?)总之我最后 1h 都在罚坐。

虽然题目非常复杂,但是从宏观来看,每个激光的速度会越来越快,具体来说,一定是经过的传送门的 strength 的前缀 \(\max\)。从传送门的角度去看,某个激光能产生贡献当且仅当进来的时候的速度小于 strength,换句话说就是没有走过 strength 大于等于当前的传送门。

首先给出一个猜想,存在一种方案使得所有传送门都能被满足。可以通过给出构造方案直接证明。

那么可以按照传送门的 strength 从小到大排序,依次决定类型,根据上文提到的观察,可以看作是将 \(n\times m\times 4\) 个点逐渐联通的过程,产生贡献当且仅当激光的出发点在同一个联通块内。

那么每次就可以求出当前传送门的能量,进而确定类型,接着再次连边。这样显然是不会产生矛盾的,即每个点都会被满足。


然后讲一讲是如何实现的,这里参考了 ugly2333 的代码。

目标是要维护所有 出发位置到当前位置经过的 strength 的 \(\max\) 之和(在模 \(2\) 意义下的值)以及路径模 \(2\) 意义下的值。

这两个都可以在合并的时候进行更新。


CF1740G Dangerous Laser Power
https://shmilyty.cf/cf1740g/
作者
ShmilyTY
发布于
2022年10月30日
许可协议