sol 1733E

SilviaLss · 2022-11-06 18:36:04 · 题解

写篇题解记录一下 cf 场上几乎秒了 *2700 题 /cy。

首先，每一个不同的时刻出生的史莱姆走的路程都不一样，所以显然不可能会有两只史莱姆会相遇（给这个条件完全是在迷惑选手）。然后分析这个数据范围，想着大概是 Tt\log n 或者是 Tn^2 的复杂度（n 是地图大小，此处为 120），发现前者完全没啥可行的方法，于是去想后者。

我们发现直接做很麻烦，于是我们做一个差分，考虑求方案数。设 f_t 表示前 t 时刻有多少个史莱姆经过了 (x,y)，我们只需要判断 f_t-f_{t-1} 是否为 0 即可。我们发现这个东西特别好处理。如果有 t 只史莱姆经过了 (a,b)，那么则有 \frac{t+1}{2} 去了 (a,b+1)，\frac t2 去了 (a,b)（默认取整）。这个东西直接 n^2 dp 就可以了。

注意初始化 dp_{0,0}=t-x-y+1 而不是 t，因为走的步数不足 x+y 的无法造成贡献。

考场提交。