学习知识点时遇到比较好的博客文章,记录一下。
然后这些文章里面又有对其作者启发的文章也建议看看。
我只是记录了我自己看了比较有启发的文章。
图论
匈牙利算法
匈牙利算法相关证明:为什么不需要考虑原有点的匹配方式;为什么只需要遍历一遍左部点;为什么回溯时 vis 数组不置零_smallC233的博客-CSDN博客
一些可能存在的疑惑,在这篇博客获得解决。
数据结构
分块
数列分块总结——题目总版(hzwer分块九题及其他题目)(分块) - Flash_Hu - 博客园
【知识总结】分块和值域分块_Cutele_的博客-CSDN博客
分析主要分为两部分:不完整的块、整块、预处理/维护(又分为数据的性质,单个数据的标记,如排序,统计是否为0,元素和 ...)...
比如,统计大于/小于的个数,就可以采用维护排序的做法,然后维护时可以用各种各样的数据结构。
因为很多时候还是要保持有原来的序列,所以常常要另外为每一块开一个数组。
选取的块的大小,可能因为和数据有关,就比较玄学(bushi),具体调参,可以生成大数据,然后用两个设定不同的对拍,看运行时间。
带插入的,用重新分块的操作,既可以在一块过大,也可以在$\sqrt{n}$次插入后重新分块等。
有时候还需要把块区间预处理出一些数据,复杂度一般为$O(块多少 \cdot n)$。
多个标记需要想清楚更新的先后顺序。
这边也贴一下我的分块九题code好了。虽然第三题std有点锅,直接set.erase
掉,它这一个数就全删了,但还是orz hzwer学长。
后几篇是讲区间众数、值域分块、莫队相关,也是由hzwer学长的第九题引出的。
Kruskal重构树
学习笔记:Kruscal 重构树 - DMoRanSky - 博客园
图很棒,看图就很容易理解了。
(现在的理解)是用来求两个点之间经过的最大/最小路径的最小/最大值,转化为两点的LCA。
以求最大值的最小值为例,整个重构的过程,可以想我们的目标是把答案放在LCA,那么就是从小到大枚举边权,然后小的先合并,之后都用DSU的祖先来整体来看,也就是想要跨越这两个集合,一定要经过新加进来的边(因为比他小的边连完后,这两个集合仍然独立)。
重构树更多是一种思想,比如Problem - F - Codeforces就是重构树,思路类似于Kruskal重构树,但是可以不把另外的点建出来。
杂
浅谈 OI 中的数据结构题 - DPairの博客 - 洛谷博客
动态规划
高维前缀和/子集和DP (SOS DP, sum over subset)
SOS Dynamic Programming Codeforces
Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution - Codeforces
这部分好像思想与FMT/FWT
比较类似,那边的文章也可以看看。
多维独立的信息,分步再整合的感觉。
树上背包
子树合并背包类型的dp的复杂度证明_背包型树形dp 复杂度_cervoliu的博客-CSDN博客
LCA是通俗易懂的复杂度估计。
数学
FFT/NTT
FFT/NTT 多项式学习笔记 - Fenghr - 博客园
NTT&FFT 快速?变换,以及扩展 - chasedeath - 博客园
因为系数表达式相乘不方便,而点值表达式相乘,直接点值的函数值相乘就行,所以用FFT把系数表达式转化为点值表达式,相乘后,再用IFFT(FFT的逆操作)变回系数表达式。推导看下来大概就会明白FFT和IFFT的联系,然后复数运算常数比较大,自己实现下这个类比较好。
FMT/FWT
位运算卷积(FWT) & 集合幂级数 - command_block 的博客 - 洛谷博客 (luogu.com.cn)
快速沃尔什变换/FWT 详详详解_Hypoc_的博客-CSDN博客
快速变换之Fast Mobius Transform - 知乎
快速莫比乌斯变换 / Fast Mobius Transform, FMT - AE酱 - 博客园
快速沃尔什变换及快速莫比乌斯变换学习笔记 | Bill Yang's Blog
生成函数
Tutorial] Generating Functions in Competitive Programming - Part 1 - Codeforces
Tutorial] Generating Functions in Competitive Programming - Part 2 - Codeforces
计算几何
点在多边形内部
一般多边形是O(n),凸多边形可以二分logn
做法上,除了确定是凸多边形且有按照一定顺序排列的是可以logn确定是否在区域内,
一般的多边形,如果是普通多边形,射线法和转角法一致,而非一般的复杂多边形,两者对多边形区域的判定是有区别的。
如GIS算法基础(二)计算几何基础(中) - 小钟233 - 博客园中提到的例子(我做对横坐标和纵坐标都做了-3的偏移。
Input:
7
0 6
6 0
15 15
9 15
18 0
24 6
12 27
1
12 12
Output:
OUT - 射线法
IN - 转角法
思维
Meet in the Middle
Meet in the middle算法总结 - birchtree - 博客园
之前学过双向广搜,其实就是这个思想。
若为 闭区间
dfs(0, n/2-1, 0, ans1);
dfs(n/2, n-1, 0, ans2);
/**********或者************/
dfs(1, n/2, 0, ans1);
dfs(n/2+1, n, 0, ans2);
/* 不然会造成RE/MLE等情况,因为不是一半分
就记忆下面的这种就行,上面是都-1。 */
DSU On Tree
Tutorial Sack/dsu on tree - Codeforces
主要是启发式合并的思想,这几篇文章提到的基本上还是轻重链的形式。Problem - E - Codeforces,这一题也是启发式合并,但不是轻重链,而是把要维护的信息用map来维护,合并的时候是启发式合并的思想。所以,主要是启发式合并的思想。
这种形式,我的理解是:
对每个子树来说,是对大的部分(重儿子)保留,轻儿子暴力求,有点把轻儿子合到重儿子的意味。然后,对于当前子树是重儿子的链,在后面被当作轻儿子时,一样要清空暴力求,来保证结果的正确性。从单个子树来看,它每棵子树都是从轻儿子开始求,然后撤除轻儿子的答案,来避免影响之后求重儿子,而重儿子因为是最后一个求,就保留只跑一遍,可以传递回父节点的值。
关于时间复杂度第二篇文章比较清楚,就不再反复论证了。
莫队
莫队算法——从入门到黑题 - WAMonster - 博客园
莫队细讲——从零开始学莫队 - Hastieyua - 博客园
开始的几篇文章哪一篇好像都可以一篇全吃(
莫队是对询问优化,尽量运用给前一次提问的信息来更新下一次提问的答案。
让左右双指针走的“步数”尽量相近。
容斥
虽然思想很简单,但是很多时候就忘了。
常伴随正难则反的想法。
Comments | NOTHING
该文章已经关闭评论