标签: ACM

4 篇文章

基础数据结构(前缀和/差分/树状数组/线段树)学习笔记
前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: 1. $sum_{i,j}=a_{i,j}$ 2. $sum_{i,j}+=sum_{i-1,j}$ 3. $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分…
图匹配学习笔记
这两天零零散散地对图匹配算是进行了一个较为系统的学习,写个简单的学习笔记,既是记录,也是一边写一边帮助回忆巩固。 二分图匹配 判定 静态:黑白染色。 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图…
[Practice]算法竞赛小东西简记
分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma …
[Competition]大学算法竞赛比赛记录册
不知道过了多久,似乎是时候开始回归之路了。 PAT 甲级 2023冬考 链接:Link 官方还没公开题目,暂用这个 时间:23.12.2 分数:400/400 排名:1/185 简评: diagonal这个单词不认识卡了我半天... A dfs水题,前提是认识diagonal B 单调栈水题 C 树上dfs+双指针,两个part没啥关联,不难 D …