【学习笔记】基础的各种东西

= =

发现自己啥都不会（

去补了补正睿暑假的内容（

能找到题的话会尽量把题交到代码公开的 OJ 上，找不到就把代码挂洛谷剪贴板。

欧拉路径 / 回路

瞎扯

欧拉路径指经过每一条边恰好一次的路径，欧拉回路指经过每一条边恰好一次的回路。

欧拉回路可以使用简单的 dfs 求出，但是在遍历边 $(u,v)$ 时需要先把 $v$ 遍历完再加边 $(v,u)$ 。

技巧

欧拉回路有两个最重要的性质：

经过每条边恰好一次
到达每个点的次数等于离开每个点的次数

举例来说，例题 2 利用了性质 1，例题 3 利用了性质 2。

例题

拓扑排序

是人都会

并查集

发现自己啥都不会 = =

值得注意的是，路径压缩加上按秩合并的并查集复杂度才是反阿克曼函数级别的，只有其中一个的话是 $O(\log n)$ 的。

例题

最短路

最短路树（图）即当确定一点 $u$ 时，对于所有点 $v\not = u$ 只保留 $(u,v)$ 最短路上的边形成的树。

例题

「JLOI 2011」飞行路线以及 Code
「网络流 24 题」软件补丁以及 Code
「USACO 2008 Jan. Silver」Telephone Lines 以及 Code
「USACO 2011 Jan. Gold」道路与航线以及 Code
「NOIP 2009」最优贸易以及 Code

矩阵快速幂

瞎扯

邻接矩阵快速幂和普通的没啥区别，只是转移矩阵经常长得像邻接矩阵（

附赠封装板子

Tips

注意广义矩阵乘法的单位矩阵也是会变的，如果单位矩阵不好推的话就换个写法
$i,j,k \to i,k,j$
初始矩阵的行数为 $1$ ，所以它与一个 $n \times n$ 的转移矩阵做乘法是 $O(n^2)$ 而不是 $O(n^3)$ 的，可以利用这一点来优化
如果一种广义矩阵乘法要满足结合律，它的两种运算（代替原来的加法和乘法的二元运算）需要构成一个半环，即：
- 加法满足封闭性、交换律、结合律，存在单位元，但是不需要逆元
- 乘法满足封闭性、结合律
- 乘法关于加法满足分配律，即 $a(b+c)=ab+ac$ 且 $(a+b)c = ac+bc$
- via. tiger0132

例题

斐波那契数列
「NOI2012」随机数生成器以及 Code
「HNOI2011」数学作业以及 Code
P哥破解密码以及 Code
「GZOI2017」河神以及 Code
「SCOI2009」迷路以及 Code，洛谷过了但是 loj 莫名 RE
「SDOI2009」HH 去散步以及 Code
「ZJOI2005」沼泽鳄鱼以及 Code
「TJOI2017」可乐（数据加强版）以及 Code
「USACO 2007 Nov. Gold」Cow Relays 以及 Code
「NOI 2020」美食家以及 Code

字符串 / 哈希

例题

数学 / 数论

瞎扯

高斯消元在异或意义下同样成立

之前写的学习笔记：

因为时间实在是不够了，例题不涉及组合数学部分

也实在懒得放代码了（

〇你〇，文化课能不能去死啊（

例题

分块入门

例题

尾声

我们的故事暂且告一段落了。

OI，七月再见。