= =
发现自己啥都不会(
去补了补正睿暑假的内容(
能找到题的话会尽量把题交到代码公开的 OJ 上,找不到就把代码挂洛谷剪贴板。
欧拉路径 / 回路
瞎扯
欧拉路径指经过每一条边恰好一次的路径,欧拉回路指经过每一条边恰好一次的回路。
欧拉回路可以使用简单的 dfs 求出,但是在遍历边 时需要先把 遍历完再加边 。
技巧
欧拉回路有两个最重要的性质:
- 经过每条边恰好一次
- 到达每个点的次数等于离开每个点的次数
举例来说,例题 2 利用了性质 1,例题 3 利用了性质 2。
例题
拓扑排序
是人都会
并查集
发现自己啥都不会 = =
值得注意的是,路径压缩加上按秩合并的并查集复杂度才是反阿克曼函数级别的,只有其中一个的话是 的。
例题
- 食物链 以及 Code
- 「NOIP 2010」关押罪犯 以及 Code
- CF1250E The Coronation 以及 Code
最短路
最短路树(图)即当确定一点 时,对于所有点 只保留 最短路上的边形成的树。
例题
- 「JLOI 2011」飞行路线 以及 Code
- 「网络流 24 题」软件补丁 以及 Code
- 「USACO 2008 Jan. Silver」Telephone Lines 以及 Code
- 「USACO 2011 Jan. Gold」道路与航线 以及 Code
- 「NOIP 2009」最优贸易 以及 Code
矩阵快速幂
瞎扯
邻接矩阵快速幂和普通的没啥区别,只是转移矩阵经常长得像邻接矩阵(
附赠 封装板子
Tips
-
注意广义矩阵乘法的单位矩阵也是会变的,如果单位矩阵不好推的话就换个写法
-
-
初始矩阵的行数为 ,所以它与一个 的转移矩阵做乘法是 而不是 的,可以利用这一点来优化
-
如果一种广义矩阵乘法要满足结合律,它的两种运算(代替原来的加法和乘法的二元运算)需要构成一个半环,即:
- 加法满足封闭性、交换律、结合律,存在单位元,但是不需要逆元
- 乘法满足封闭性、结合律
- 乘法关于加法满足分配律,即 且
- 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
字符串 / 哈希
例题
- 【模板】KMP字符串匹配
- 「USACO 2015 Feb. Silver」Censoring 懒得放代码
- 「POI 2006」OKR-Periods of Words 懒得放代码
- 「NOI2014」动物园 以及 Code
- CF1200E Compress Words 以及 Code
- 「BJOI 2015」树的同构 懒得放代码
- 「JSOI 2016」独特的树叶 以及 Code
数学 / 数论
瞎扯
高斯消元在异或意义下同样成立
之前写的学习笔记:
因为时间实在是不够了,例题不涉及组合数学部分
也实在懒得放代码了(
〇你〇,文化课能不能去死啊(
例题
- 【模板】线性筛素数
- 「SDOI 2008」仪仗队
- GCD SUM
- 【模板】二元一次不定方程 (exgcd)
- 【模板】乘法逆元
- 「NOIP 2012」同余方程
- 【模板】中国剩余定理(CRT)/曹冲养猪
- 「TJOI 2009」猜数字
- 「SDOI 2010」古代猪文
- 【模板】扩展中国剩余定理(EXCRT)
- 「NOI 2018」屠龙勇士 以及 Code
- 【模板】高斯消元法
- 「JSOI 2008」球形空间产生器
- 「SDOI 2010」外星千足虫
分块入门
例题
- #6277. 数列分块入门 1 以及 Code
- #6278. 数列分块入门 2 以及 Code
- #6279. 数列分块入门 3 以及 Code
- #6280. 数列分块入门 4 以及 Code
尾声
我们的故事暂且告一段落了。
OI,七月再见。