时间戳

首页 > 技术文章 > ACM入门方式

ACM入门方式

zhihaospace 2020-05-10 08:54 原文

转载：https://www.zhihu.com/question/51727516/answer/927853763

目录：

  • 图论部分
  • 数论/数学部分
  • 图论与数学同时比较相关的部分
  • 字符串
  • 计算几何(等EC结束之后让会几何的人帮我补充这部分.jpg)
  • 动态规划
  • 数据结构

正文：

图论部分：(非常独立)

（其实图论方向没有太明显的"难度区分"，你可以先学完1和2就直接去学二分图匹配……不过按顺序来总是不会错哒。）

  1. 图的邻接表存储（不需要学邻接矩阵，那个没用）: 邻接表存储
  2. 图的深度优先搜索和广度优先搜索，网上资料实在太多啦！
  3. 拓扑排序：拓扑排序
  4. 非常冷门的算法：差分约束，如果时间紧可以先跳过：差分约束
  5. 非常非常非常冷门的算法：prufer编码：参考题目
  6. 最短路：SPFA算法和(堆优化的)Dijkstra算法，理解最短路图的概念，理解平面图最小割与最短路的关系：
    1. SPFA正式比赛慎用。
    2. 【Algorithm】平面图最小割转最短路 - Bombe - 博客园(难度较高，可暂时略过……)
    3. 堆优化Dijkstra
    4. 同余最短路：[bzoj2118]墨墨的等式--同余最短路 - ylsoi - 博客园
  7. 欧拉回路：欧拉回路
  8. tarjan算法求强联通分量、求边的双联通分量、求割点、求桥：tarjan求强连通分量+缩点+割点/割桥（点双/边双）以及一些证明 - Styx-ferryman - 博客园
  9. 二分图的概念，匈牙利算法和时间复杂度为(n^3)的KM算法：
    1. 时间复杂度为n^3的KM算法可以只知道用途并且把代码抄到板子上，代码参考UOJ上面比较快的二分图最大权匹配的板子即可。
    2. 匈牙利算法要熟悉原理及其变形：匈牙利算法
  10. 用Dinic算法求网络流，费用流：[算法]网络最大流Dinic - LinZhengmin - 博客园
  11. 最小树形图：最小树形图--朱刘算法 - GGBeng - 博客园
  12. 稍微冷门一点点：一般图最大权匹配，说的就是带花树。这个也去参考UOJ上面抄一个最好看的板子就好辣！
  13. 稍微冷门一点点点：2-SAT，但是不会的话会死得很惨。2-SAT超入门讲解 - hl666 - 博客园
  14. 分数规划虽然不属于图论范畴，但是有相对应的题目：图论&数学：最小平均值环 - 静听风吟。 - 博客园，主要学习分数规划的方法。

数论/数学部分：（非常独立）

  1. 费马小定理、欧拉定理：费马小定理及欧拉定理，并且会：
    1. 利用它们在O(logn)的时间复杂度内计算一个数的逆元
  2. 素数筛法，请务必掌握的是"线性筛"：线性筛筛积性函数 - yyys - 博客园
    1. 另外，请一定要记住"线性筛"强调的是"线性筛不仅能筛出素数，还能筛一些积性函数"。
    2. 上面说的这句话在"莫比乌斯反演"题目里尤为重要。
  3. 辗转相除法，扩展欧几里得算法，中国剩余定理，会抄不互质的CRT的板子：
    1. 扩展欧几里得
    2. 中国剩余定理
  4. 容斥原理（基础）及Min-Max容斥原理（偏难，出了就做不出来系列）：
    1. 基础的容斥原理自行百度啦QAQ
    2. Min-Max容斥原理：6.陈立杰-计数与期望 - 百度文库
  5. Lucas定理等一系列组合数取模的计算：组合数取模方法总结
  6. BSGS算法：BSGS算法 - 小蒟蒻yyb - 博客园
  7. 线性基：线性基
  8. 高斯消元：高斯消元，另外注意在模意义下高斯消元的时候把除法改为乘以逆元。
  9. 解二次剩余：二次剩余Cipolla算法学习笔记 - bztMinamoto - 博客园
  10. 拉格朗日插值: [学习笔记]拉格朗日插值 - *Miracle* - 博客园
  11. 莫比乌斯反演及一系列反演问题：
    1. 学会简单的莫比乌斯反演并推出式子，只需要在准备课件的前一个晚上，盯着电脑屏幕从白天到夜里凌晨连刷12题就行了（划掉）
    2. 我当时是在这里学的。ACdreamer的博客
    3. 另外要尽量去理解这个：炫酷反演魔术 - 幻灯片 - vfleaking的博客
    4. 上面那个幻灯片里面包含"子集和变换",“集合并卷积”等一系列东西，考到了不会的话要死得很惨。
    5. 再次强调要知道FWT（上面那个ppt里）是怎么来的，要学会上面所说的子集和变换等等一系列子集反演内容。
  12. 学会求原根，在做题的时候智力上线记得"有个东西叫生成函数"以及"把乘法转化成原根的加法"，掌握FFT与NTT的板子：
    1. 快速数论变换（NTT） - HuaZhang - 博客园
    2. 快速傅里叶变换 & 快速数论变换
    3. 知道FFT可以做这个：通配符匹配
  13. 学会杜教筛怎么用并学会推杜教筛的式子：铃悬的数学小讲堂--杜教筛 - 铃悬 的博客 - 洛谷博客
  14. 学会min_25筛:关于min_25筛的一些理解 - GuessYCB - 博客园
  15. Burnside定理以及Polya定理："如果学会这两个定理的非模板题，那么出了这种题就是胜负手，因为懂这个定理的人实在太少了（但同样也不会出现很多这种题QAQ）"。定理内容及例题
  16. 类欧几里得：找不到课件地址了QAQ。

图论与数学同时比较相关的似乎只有一个定理：

【算法】Matrix - Tree 矩阵树定理 & 题目总结​www.cnblogs.com

字符串（"基本上"一定复合动态规划(DP)）：

  1. KMP算法：KMP算法
  2. 扩展KMP：扩展KMP算法小记 - Dilthey - 博客园
  3. 字符串HASH：字符串HASH
    1. PS: 关于hash类的题目有不少，比如奇怪的树hash，需要单独去学。
    2. 有概率配合哈希表(C++中的map)使用，比赛时智力记得上线。
  4. Manacher：Manacher算法的详细讲解
    1. 知道manacher的回文半径有什么用，怎么用，稍微做两道题就行了。
  5. Trie树/字典树：Trie（前缀树/字典树）及其应用 - bonelee - 博客园
  6. AC自动机及Trie图：Trie图（DFA），AC自动机 - AC_Von - 博客园
    1. 学完Trie图之后对于AC自动机的用法会减少，基本都是用Trie图的。
    2. 意识到fail指针形成了一棵树，并学会在fail树/Trie图上进行DP
    3. 做几道相关的DP题
  7. 后缀数组(SA)：后缀数组
    1. 其实下面的SAM可以求后缀数组，不想学就算了。(碰到出题人卡SAM就喷出题人)
  8. 后缀自动机(SAM)：后缀自动机
    1. 依旧是需要学会SAM上的DP，并意识到parent树的niubi之处。多做题。
    2. 但一般SAM上面的DP就会比较难，甚至可以复合其它的数据结构，比如Link-Cut-Tree（LCT）：（据某毒瘤出题人说“我出的那道LCT+SAM的题被学军的同学A穿了，感觉OI选手还是强啊”）
  9. 回文树：回文树算法，建议去看看论文。

计算几何(非常独立)：

先参考这个模板里面提到的东西：计算几何 · GitBook

  1. 基本的点积、叉积概念，基本向量代数运算，会推微积分的式子。
  2. 凸包的计算(用叉积，尽量规避三角函数)：向量积&&凸包算法 - Go!Adela - 博客园
    1. 哪怕凸包不会求，凸壳也要会求，这句话是写给要学习"动态规划"的ACMer的。
  3. 旋转卡壳: 旋转卡壳
    1. 利用旋转卡壳O(n)求极大三角形的算法已经被hack掉了，如果之后在网上看到请不要抄O(n)做法。
  4. 半平面交:（先看4.1中的内容） 半平面交
    1. 半平面交与凸包表现出高度一致性：半平面交对偶转凸包问题 - 博客 - Trinkle的博客
    2. 心疼一秒做DP题的：上面的半平面交对偶转凸包的东西在斜率优化里依然需要用到。
  5. k次圆覆盖问题：k次圆覆盖
  6. 辛普森积分：辛普森积分暴力大法好
  7. 模拟退火：浅谈玄学算法--模拟退火 - M_sea 的博客 - 洛谷博客

动态规划(DP)：

很不幸，这种类型的题目没有板子一说，也没有一个人敢说"碰到DP我一定能做出来"，它想出得有多难就有多难。而且可以和数据结构/字符串的题目进行复合，难度从最低到最高的题目都有。

凡是谁说了解"动态规划的本质"就会做动态规划都是在耍流氓（笑

400道都不够用的。我也想整一个

在这里只能总结一下出现的比较经典的类型。想提升考场上做出来dp题的概率只能靠疯狂刷题。

从图论角度理解DP：什么是动态规划（Dynamic Programming）？动态规划的意义是什么？

"哪怕不写代码也写出递推式试试看吧"，抱着这种心态去做题吧！

  1. 记忆化搜索：主要用于不是循环结构的递推表达式状态的计算
  2. 背包dp：我的观点是没必要看背包九讲，之后自己刷题刷多了自然都会了。
  3. 树形dp：树形DP入门学习 - seaupnice - 博客园
    1. 树形dp比较常见，虽然知道这一点并不能帮你做题。
    2. 一般是考虑子树/相邻儿子对于当前节点的贡献，需要多刷题总结。
  4. 区间dp：入门题
  5. 状态压缩dp：一些题目
    1. 一些另外的题目：为什么只有题目？……这个问题问得好啊，因为这个只能刷题QAQ
  6. 插头dp：两篇文章: 插头dp && 基于连通性状态压缩的动态规划问题 - 百度文库
    1. 题目自己找咯~
  7. 基于数据结构优化的dp：(ps：以后会稍微谈谈各种递推式的优化，优化套路差不多)
    1. 前缀和/前缀最大值/...优化dp：CF601C Kleofáš and the n-thlon(期望+前缀和优化dp)
    2. 单调队列优化dp：不太像dp的dp
    3. 树状数组/线段树优化dp：[noip科普]关于LIS和一类可以用树状数组优化的DP - liu_runda - 博客园
    4. 斜率优化dp：制糕神的算法工坊：动态规划的斜率优化——从入门到入土
  8. 一个奇怪的dp思想：管道取珠

数据结构（可以跟很多东西沾边）：

  1. 链表：链表实战（带图分析）
  2. 哈希表(C++常用MAP)：制糕神的算法工坊：OI/ACM中的哈希表，一些哈希算法以及题目
  3. ST表：ST表的原理及其实现 - 真是啰嗦 - 博客园
  4. 堆：C++里的priority_queue……会用就可以啦，原理不是必须要懂。
  5. 并查集：并查集
    1. 如果不会线段树分治，可以只学习路径压缩的并查集。
    2. 如果会线段树分治，"按大小启发式合并的并查集"非常合适。
  6. 单调队列：简单数据结构总结--单调队列 - dreagonm - 博客园
  7. 树状数组：树状数组详解 - Xenny - 博客园
  8. 线段树：线段树 从入门到进阶 - Dijkstra·Liu - 博客园
    1. 线段树的动态开点形式：线段树 动态开点 - Lonely.Devil - 博客园
  9. 平衡树：
    1. 旋转Treap&&非旋转Treap：旋转/非旋转treap的简单操作 - F.W.Nietzsche - 博客园
    2. Splay：Splay详解 - JSOI爆零珂学家yzhang - 博客园 (其实Splay不算是平衡树)
    3. 其实旋转的Treap用处不是太大……
  10. 启发式合并：数据结构：启发式合并 - 静听风吟。 - 博客园
    1. 合并的对象不仅限于并查集，线段树，平衡树。
    2. 其基本思想有点类似于贪心。
  11. 树链剖分，可以用于求LCA，一般绑定线段树使用：树链剖分详解 - Ivanovcraft - 博客园
  12. K-Dtree: K-D TREE算法原理及实现 - 采男孩的小蘑菇 - 博客园
  13. 莫队算法：莫队算法--从入门到黑题 - WAMonster - 博客园
  14. 可持久化数据结构：可持久化线段树总结（可持久化线段树，线段树） - Flash_Hu - 博客园
    1. 可持久化Treap - permui - 博客园
    2. 如果可以离线，请千万不要为了秀自己的代码能力而写可持久化，因为：
      1. 写出来是在秀自己的代码能力
      2. 写不出来是在秀自己的智力
  15. 线段树分治： [学习笔记]线段树分治 - *Miracle* - 博客园
  16. CDQ分治：CDQ分治总结（CDQ，树状数组，归并排序） - Flash_Hu - 博客园
    1. 常用来解决3维偏序问题，离线+排序降一维，CDQ分治降一维，线段树降一维。
  17. 放弃那些奇奇怪怪的树套树吧，比赛的时候没人愿意考也没人愿意写。

推荐阅读