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

= =

发现自己啥都不会(

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

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

欧拉路径 / 回路

瞎扯

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

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

技巧

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

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

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

例题

  1. 板子 以及 Code
  2. 无序字母对
  3. CF547D Mike and Fish

拓扑排序

是人都会

并查集

发现自己啥都不会 = =

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

例题

  1. 食物链 以及 Code
  2. 「NOIP 2010」关押罪犯 以及 Code
  3. CF1250E The Coronation 以及 Code

最短路

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

例题

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

矩阵快速幂

瞎扯

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

附赠 封装板子

Tips

  1. 注意广义矩阵乘法的单位矩阵也是会变的,如果单位矩阵不好推的话就换个写法

  2. i,j,ki,k,ji,j,k \to i,k,j

  3. 初始矩阵的行数为 11,所以它与一个 n×nn \times n 的转移矩阵做乘法是 O(n2)O(n^2) 而不是 O(n3)O(n^3) 的,可以利用这一点来优化

  4. 如果一种广义矩阵乘法要满足结合律,它的两种运算(代替原来的加法和乘法的二元运算)需要构成一个半环,即:

    • 加法满足封闭性、交换律、结合律,存在单位元,但是不需要逆元
    • 乘法满足封闭性、结合律
    • 乘法关于加法满足分配律,即 a(b+c)=ab+aca(b+c)=ab+ac(a+b)c=ac+bc(a+b)c = ac+bc
    • via. tiger0132

例题

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

字符串 / 哈希

例题

  1. 【模板】KMP字符串匹配
  2. 「USACO 2015 Feb. Silver」Censoring 懒得放代码
  3. 「POI 2006」OKR-Periods of Words 懒得放代码
  4. 「NOI2014」动物园 以及 Code
  5. CF1200E Compress Words 以及 Code
  6. 「BJOI 2015」树的同构 懒得放代码
  7. 「JSOI 2016」独特的树叶 以及 Code

数学 / 数论

瞎扯

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

之前写的学习笔记:

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

也实在懒得放代码了(

〇你〇,文化课能不能去死啊(

例题

  1. 【模板】线性筛素数
  2. 「SDOI 2008」仪仗队
  3. GCD SUM
  4. 【模板】二元一次不定方程 (exgcd)
  5. 【模板】乘法逆元
  6. 「NOIP 2012」同余方程
  7. 【模板】中国剩余定理(CRT)/曹冲养猪
  8. 「TJOI 2009」猜数字
  9. 「SDOI 2010」古代猪文
  10. 【模板】扩展中国剩余定理(EXCRT)
  11. 「NOI 2018」屠龙勇士 以及 Code
  12. 【模板】高斯消元法
  13. 「JSOI 2008」球形空间产生器
  14. 「SDOI 2010」外星千足虫

尾声

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

OI,七月再见。