分类: 算法

17 篇文章

基础数据结构(前缀和/差分/树状数组/线段树)学习笔记
前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: 1. $sum_{i,j}=a_{i,j}$ 2. $sum_{i,j}+=sum_{i-1,j}$ 3. $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分…
图匹配学习笔记
这两天零零散散地对图匹配算是进行了一个较为系统的学习,写个简单的学习笔记,既是记录,也是一边写一边帮助回忆巩固。 二分图匹配 判定 静态:黑白染色。 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图…
fhq_treap(无旋 treap) 学习笔记
fhq_treap(无旋 treap) 参考:远航之曲的博客。 感觉比较意识流。 核心思想是平衡树分裂和合并。 类似于 Splay 把区间分离出来,fhq_treap 可以把平衡树进行分裂来提取需要的区间,再通过合并平衡树来维持树高(即堆性质)。这样不仅可以做到维护区间,还免去了旋转操作,代码较为简单。 split & merge &…
最小费用最大流(MCMF)简要学习笔记
在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法,更推荐类似于 Dinic 的 spfa+dfs 的写法,详见最下方的“附加代码”部分。 MCMF(基于 spfa 实现) 模板题:Luogu3381。 即给定一张网络,每条边都有一个权值和流量限度,这条边上每有一个流量,总费用就加上这个权值,你需要在…
块状链表学习笔记
块状链表 参考:Tak_vin 的 博客 及相关代码。 这篇可能写的巨草,主要是给我自己看的。 一种根号数据结构,支持一个区间的动态插入和随时访问。 以 Luogu4008 [NOI2003] 文本编辑器 为例。 题意: 维护一个文本编辑器,支持: Move/Prev/Next 移动光标位置 Insert 在光标处插入若干个字符 Delete 删除…
树上启发式合并(dsu on tree)学习笔记
参考:p_z_y 的博客,YellowBean 的代码启示。 尽量写短点。 dsu on tree 模板题:CF600E Lomsat gelral。 题意: 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色,颜色是以编号表示的, $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数…
数据维护中的值域分块
第一道题 CF1515I Phoenix and Diamonds 题目链接。 题意(5s,1000MB): $n$​ 种钻石,一颗第 $i$​ 种钻石重量为 $w_i$​,价值为 $v_i$​,一开始第 $i$​ 中钻石的库存为 $a_i$​。接下来进行 $m$​​ 次操作: 1 k d:进货了 $k$ 个种类为 $d$ 的钻石; 2 k d:卖…
珂朵莉树(Chtholly Tree/ODT)学习笔记
参考:泥土笨笨的博客,Leap_Frog 的博客。 好久没写学习笔记了啊…… 珂朵莉树 模板:CF896C Willem, Chtholly and Seniorious。 题意: 给定一个序列,支持区间加,区间赋值,询问区间第 $k$ 小,区间幂次和(即 $x$ 次方的和,取模)。 数据范围 $10^5$,数据随机。 珂朵莉树(Chtholly …
决策单调性优化 dp 简要笔记
引用/参考:绍兴一中相关课件,Acfboy 的博客。 决策单调性 决策单调性指的是 dp 的决策时的最优位置是单调的。 常见地,若存在: $dp_i = f(dp_j)$ 中,$i$ 的决策位置是 $pos_i$,那么对于所有 $i\ge2,pos_i \ge pos_{i-1}$。 难点在于观察(猜)出其为决策单调,经常可以不证明。一般通过打表观…
OI 里的数学内容整理(提高组)
本博客仅罗列定理,不给出证明,如需要请自行搜索。 质数相关 线性筛素数 inline void sieve(int n){//线性筛求 pri 和 phi phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;} for(int j=1;j<=cnt&a…