Oql's Blog

发表于 分类于

题目大意

一棵 $n$ 个节点的树，点有 $k$ 种颜色。

现在要求选出最小的颜色集合，使得在颜色集合中的点形成一个连通块。输出该集合的大小。

$n,k\leq 10^5$

阅读全文 »

发表于 分类于

A

小学数学题。

B

并不会证明？

C

移到角落然后一起移上去就可以了。

D

每个段分开来考虑就好了。

E

小数数学题。

F

考虑每一位的贡献，最后乘起来就好了。

现在题目变成 $m$ 个限制，每个限制形如 $[l,r]$ 不全为 $1$ 或者必须全为 $1$。

那么设 $f_i$ 表示考虑到第 $i$ 位，且该位选 $0$ 的方案数。若该位必须选 $1$，则 $f_i=0$。

然后two-pointer维护合法区间即可。

时间复杂度 $O(k(n+m))$。

G

为什么会有这么sb的题。。。

AC自动机上状压DP即可。太智障了，懒得写了。