比赛地址

白昼夢 / Daydream

如果当前字母是 d 则依次匹配 dreameraserdreamerasedreamerdream,如果当前字母是 e 则依次匹配 erasererase

不如直接倒着做

代码

連結 / Connectivity

开两个并查集,然后开个 map 维护一下 [find1(i),find2(i)] 即可。

代码

へんなコンパス / Manhattan Compass

把曼哈顿距离转成切比雪夫距离后 BFS 一下,同时用 set 维护所有点即可。

没有代码。

シャッフル / Shuffling

然被包含的区间是没用的,于是可以把左右端点都转化为递增的。

考虑 DP。设 $dp_{i,j}$ 表示到前 $i$ 个位置有 $j$ 个 $1$ 的方案数,$sum_i$ 为前 $i$ 个数中 $1$ 的个数。

那么当 $r_i<l_{i+1}$ 时,我们要在 $r_i-l_i+1$ 个位置中放 $sum_{r_i}-j$ 个 $1$,转移为

$$ dp_{l_i-1,j}\times{r_i-l_i+1\choose sum_{r_i}-j}\to dp_{l_{i+1}-1,sum_{l_{i+1}-1}} $$

否则,我们枚举在 $l_{i+1}-l_i$ 个位置中放的 $1$ 的个数,转移为

$$ \sum_k dp_{l_i-1,j}\times{l_{i+1}-l_i\choose k}\to dp_{l_{i+1}-1,j+k} $$

答案即为 $dp_{n,sum_n}$。

复杂度据说是 $\mathcal{O}(n^2)$ 的,但是我并不会证。

代码

最后修改:2020 年 09 月 12 日 10 : 19 PM