部分内容来自牛客相关课程课件 图匹配 二分图匹配 判定 静态：黑白染色。 动态：分层并查集。并查集可以维护的可以是点的连接关系，也可以是关系的连接方式。连接两个点，我们可以改为连接这两个点的逻辑关系，黑-白，白-黑。如果有一天同一个点的黑白被连在了一起，则这就不是一个二分图。 分层并查集经典例题：P2024 [NOI2001] 食物链。 最大匹配：…

题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包，每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个，我们需要这个答案序列先单调非降再单调非升，即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …

这是第一场所有赛题都由我命制的公开比赛，也是第二场我参与命题的公开比赛。 比赛时由于内测下来大家都觉得 D 比 E 难，就更换了 DE 的顺序，本篇题解中没有发生更换，望读者注意。 比赛链接：Link. A. 伊甸之花 题目链接：Link. 若乐曲中同时存在 $1$ 和 $m$ 则无解，否则一定可以通过整体上移/下移一个音调来满足条件，时间复杂度 …

区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。 例如二维前缀和求法： $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题：NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…

分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系，相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块，就可以给其中一块的所有点标记为 $1$，另一块所有点标记为 $0$，这样对于每个点只需要进行一些异或运算 $\Sigma …

团队赛 队伍信息 队名：普罗旺斯 / Lavender Field 成员：water_tomato, 514inparadox, temp6 2024 CCPC 网络预选赛 链接：Link 时间：24.9.8 过题数：10/12 排名：48/($\approx$ 2100) 2024 ICPC 网络预选赛 I 链接：Link 时间：24.9.15 …