[bzoj4569]-[SCOI2016]萌萌哒

题目一点都不萌……

题目(bzoj)

题目(洛谷)

 

来说说这题吧

首先一看题就知道这提要求个并查集,然后答案就是9×10^(cnt-1),其中cnt为集合个数。

为啥?首先这些限制就是要你合并一些集合,数字的第一位不能取0,剩下的就可以取0,所以一开始乘个⑨,后面就一直乘10.

然后呢?直接搞并查集O(n^2)毫不留情T掉,我们考虑倍增。

…为什么会考虑倍增?首先,并查集是可以合并的,于是利用线段树那种思想,将一个区间划分成左右两区间,然后划分到区间大小为1时再往上慢慢合并,可以证明每次操作是log(len)的,其中len为该区间大小。

于是这题就出来了:设p[x][i]表示从x开始走2^i所能到达的点,这样就可以操作了。

 

发表评论