容斥 学习笔记

小小的知识点,大大的坑。 容斥原理 设集合 $S_{1\dots n}$,有 $$ \left| \bigcup_{i=1}^n S_i \right| = \sum_{k=1}^n(-1)^{k+1}\sum_{1\le p_1 < p_2 < \cdots < p_k \le n} \left| \bigcap_{i...

P4173 残缺的字符串 题解

P4173 残缺的字符串 带通配符的字符串匹配模板题。 两个长度为 $n$ 的字符串 $a, b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2 = 0$。 如果带有通配符,将通配符看成 $0$,则 $a,b$ 相等当且仅当 $\sum_{i=...

ARC098F Donation 题解

ARC098F Donation 题意 给定一张 $n$ 个点 $m$ 条边的无向连通图,每个点有两个属性 $a_i,b_i$。 一开始你有 $w$ 元,你要从某个满足 $a_s \le w$ 的节点 $s$ 开始,每次进行下列两个操作中的一个: 选...

ARC097F Monochrome Cat 题解

ARC097F Monochrome Cat 题意 给定一棵 $n$ 个点的树,每个点要么是白色要么是黑色。 你可以从任何一个顶点出发,每秒执行下列操作中的一个: 走到一个相邻的节点,反转到达的节点颜色。 反转所在的节点...

ARC096F Sweet Alchemy 题解

ARC096F Sweet Alchemy 题意 有 $n$ 个物品,买一个第 $i$ 个物品需要花费 $m_i$ 元。 除了第一个物品外,第 $i$ 个物品有一个上级物品 $p_i(< i)$。 给定 $d$,设第 $i$ 个物品买了 $c_i$ 个,要求对...