如果问依赖性就 topo sort

DAG 的问题就 dfs+memo

矩阵和 Array 通常都是 DP

问数量的通常都是 DP

问是否可以，也很有可能 DP

[ 在数组中选取子集，达到某一目标 ] 这类问题的通用解法。

• 类型1 : 目标值明确，可以把目标值看出背包容量，数组值看做物品，转成背包问题
• 类型2 : 目标值不明确，容量不知道，不能用背包，只能枚举子集的和

1）先分析数据量，找出所有变量

• 根据数据大小，分析时间复杂度和空间复杂度，考虑能用的算法
• 不要想当然的面向用例编程，要把所有情况考虑到，题目没说只有一个的，就需要考虑多个
  • 比如UVA11624，不要默认只有一个fire

2）做题先写数学公式，画出每一个map/set中的变化，然后再写代码。

3）遇到很复杂的背景题，要仔细看输入输出的要求。

4）一眼看不到方法的问题，三种情况：

• 第一种是脑筋急转弯
  • 尽量画图，找规律
• 第二种是需要把题目抽象一下
  • 课程表抽象成节点，用图算法
• 第三种需要把求解的答案转换一下（一般需要简单的数学公式推导一下），再用固定的算法模板
  • 分割等和子集，不要上去就dfs，枚举情况，把他转变成求一个集合答案为和的一半；如
  • 目标和，把找目标和，变成找固定负数个数
  • 最后一块石头的重量，不要想着一步一步粉碎石头，解空间太大，根据题目的要求，分析出两堆石头重量尽可能接近，剩下来的重量就小。
• 第四种两种算法的结合
  • 可能需要先用前缀和预处理一下，然后再建图/模拟
  • 或者先用01背包计算出所用满足情况的满足条件，然后再计算输出答案

5）确保算法没问题但没 AC

• 找没考虑到的特殊情况
• long long
• 输出格式问题

• 440 K-th Smallest in Lexicographical Order
• 二分查找从入门到入睡 https://leetcode.cn/circle/discuss/ooxfo8/
• 十大排序从入门到入赘 https://leetcode.cn/circle/discuss/eBo9UB/
• 868
• 523
• 322
• 474 记忆化搜索 if (memo[i].find(idx) != memo[i].end()) return cnt; 无论返回多少都可以，没有关系？？？？？？？？？？？？？？？？？？
• 322 为什么 dp 赋初始值 0x3f 可以，而 INT_MAX， INT_MAX / 2 就不行
• 面试题 17.07. Baby Names LCCI
• 双向bfs，127/752/剑指 Offer II 109/剑指 Offer II 108. 单词演变
• 蓄水池算法
• bitmap
• 字典树
• 大数的十进制与二进制互转新方法
• 红黑树比 AVL 树具体更高效在哪里

// 用来代替map<char, int>，charmap比map会快5倍左右
class charmap {
public:
    int nums[26] = {0};
    int& operator[](char c) {
        return nums[c - 'a'];
    }
    int& data(int i) {
        return nums[i];
    }
};

// lambda cmp
auto tupleCmp = [](const auto& e1, const auto& e2) {
    auto&& [x1, y1, d1] = e1;
    auto&& [x2, y2, d2] = e2;
    return d1 > d2;
};

auto myCmp = [](const auto& e1, const auto& e2) {
    auto&& [to1, w1] = e1;
    auto&& [to2, w2] = e2;
    return w1 > w2; // 小顶堆 返回的是下沉规则，true则下沉 即值大的下沉
};

// function cmp
bool myCmp(const vector<int> &a, const vector<int> &b) {
    return a[0] > b[1];
}


// heapNode
struct HeapNode {
    int u;
    int d;

    HeapNode(int uu, int dd) : u(uu), d(dd) { }

    bool operator<(const HeapNode &node) const { //重载<运算符
        return d > node.d;  // 小顶堆
    }
};


// set 的运算符重载
struct myCmp {
	bool operator()(int a, int b) { 	// 重载()运算符，从大到小排序
        return a > b; 
    }
};

set<int, cmp> s;	

//自定义哈希函数，元素类型为 pair<T1, T2> a(X1, X2);
struct pair_hash
{
    template <class T1, class T2>
    size_t operator () (pair<T1, T2> const &pair) const
    {
        size_t h1 = hash<T1>()(pair.first); //用默认的 hash 处理 pair 中的第一个数据 X1
        size_t h2 = hash<T2>()(pair.second);//用默认的 hash 处理 pair 中的第二个数据 X2
        return h1 ^ h2;
    }
};

//https://blog.csdn.net/qq_32320399/article/details/81518476
static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();

💗绝世好题，做一道相当于做好多道

💛该数据结构/算法的代表性题目

💙有点难度，但必须掌握

💚

💜

https://github.com/guodongxiaren/README/blob/master/emoji.md

题号前*表示有多种解法， :(表示:( 　　:)表示:)

R代表Recursion，Q代表Queue，S代表Stack，DFS代表深度优先遍历，BFS代表广度优先遍历

模板题-连续

模板题-离散

树状数组能有的操作，线段树一定有；

线段树有的操作，树状数组不一定有。

但是树状数组的代码要比线段树短，思维更清晰，速度也更快，在解决一些单点修改的问题时，树状数组是不二之选。

双指针/滑动窗口

树中 Sec 4.1 有详细概述

master 公式(主定理) 是利用分治策略来解决问题经常使用的时间复杂度的分析方法。分治策略中递归来求解问题分为三步：分解、解决，合并。

T(N) 的公式从大规模来看，不细分。 $$ T(N) = a * T(N/b)+O(n^d) $$ 其中 n 表示问题的规模，即总样本数， a 表示递归的次数，即生成的子问题数，子过程调用多少次 b 表示每次递归是原来的N/b之一个规模，$N/b$ 是子过程数据量 d 表示额外操作的次数，$O(n^d)$ 除去过程之外剩下的数据量，剩余时间复杂度。

①$\text{if} \quad \log_ba > d \quad => \quad O(N^{\log_ba})$

②$\text{if} \quad \log_ba = d \quad => \quad O(N^d *\log N)$

③$\text{if} \quad \log_ba < d \quad => \quad O(N^d)$

注意: 多个递归的规模必须一样，否则master公式失效。

例子：二分 $$ T(N) = 2 * T[N/2] + O(1) $$ a = 2, b = 2, d = 0

$d &lt; \log_2 2$, 时间复杂度为 $O(n)$

Greedy(==排序很重要==)

DP

打家劫舍专题

子序列专题

股票专题

全排列DP专题

编辑距离

背包专题

脑筋急转弯

记忆化搜索

• vector

• set

  • unordered_set

• string

• map

  • unordered_map

• queue

  • priority_queue

• stack

• pair

• algorithm

基础篇（30 天）

基础永远是最重要的，先把最最基础的这些搞熟，磨刀不误砍柴工。

• 数组，队列，栈
• 链表
• 树与递归
• 哈希表
• 双指针

**篇（30 天）

这些**是投资回报率极高的，强烈推荐每一个小的专题花一定的时间掌握。

• 二分
• 滑动窗口
• 搜索（BFS，DFS，回溯）
• 动态规划

提高篇（31 天）

这部分收益没那么明显，并且往往需要一定的技术积累。出现的频率相对而言比较低。但是有的题目需要你使用这些技巧。又或者可以使用这些技巧可以实现「降维打击」。

• 贪心
• 分治
• 位运算
• KMP & RK
• 并查集
• 前缀树
• 线段树
• 堆

算法

• 基础技巧：分治、二分、贪心
• 排序算法：快速排序、归并排序、计数排序
• 搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等
• 图论：最短路径、最小生成树
• 动态规划：背包问题、最长子序列

数据结构

• 数组与链表：单 / 双向链表
• 栈与队列
• 哈希表
• 堆：最大堆 / 最小堆
• 树与图：最近公共祖先、并查集
• 字符串：前缀树（字典树）/ 后缀树

操作系统

• 内存管理
• 线程处理
• 文件系统
• 网络

•考察数据结构，比如链表、栈、队列、哈希表、图、Trie、二叉树等

•考察基础算法，比如深度优先、广度优先、二分查找、递归等

•考察基本算法**：递归、分治、回溯搜索、贪心、动态规划等

• Easy：常规字符串操作、常规数组操作、简单数据结构。
• Medium：数组操作、滑动窗口、哈希表、二分、搜索（bfs、dfs）、常规DP、单调栈、二叉树相关、排序算法、前缀树、堆、并查集等
• Hard：DP（背包相关、概率DP、简单数论算法、数位DP、记忆化搜索）、简单图算法（最短路、最小生成树）、数据结构实现、字符串算法（后缀数组、回文相关）

1. Pattern: Sliding window，滑动窗口模式
2. Pattern: two points, 双指针类型
3. Pattern: Fast & Slow pointers, 快慢指针类型
4. Pattern: Merge Intervals，区间合并模式
5. Pattern: Cyclic Sort，循环排序
6. Pattern: In-place Reversal of a LinkedList，原地链表翻转模式
7. Pattern: Tree Breadth First Search，树上的BFS模式
8. Pattern: Tree Depth First Search，树上的DFS模式
9. Pattern: Two Heaps，双堆类型
10. Pattern: Subsets，子集类型，一般都是使用多重DFS
11. Pattern: Modified Binary Search，改造过的二分
12. Pattern: Top ‘K’ Elements，前K个系列模式
13. Pattern: K-way merge，多路归并类型模式
14. Pattern: 0/1 Knapsack (Dynamic Programming)，0/1背包类型
    1. 0/1 Knapsack, 0/1背包
    2. Unbounded Knapsack，无限背包
    3. Fibonacci Numbers，斐波那契数列
    4. Palindromic Subsequence，回文子系列
    5. Longest Common Substring，最长子字符串系列
15. Pattern: Topological Sort (Graph)，拓扑排序模式

Class1-Grokking the Coding Interview: Patterns for Coding Questions

Class2-Grokking Dynamic Programming Patterns for Coding Interviews

数据结构：数组，栈，队列，链表，二叉树，二叉搜索树，哈希表

常用算法：贪心法，字符串处理，复杂度分析，递归，BFS，DFS，分治，排序

带名字的都不考 Morris / Dijkstra / Floyd / Manacher / Tarjan / Dinic / KMP

只有两种：数组（顺序存储）和链表（链式存储）。

「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。

「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

刷题，就是在锻炼你的眼力，看你能不能看穿问题表象揪出相应的解法框架。

比如说，让你求解一个迷宫，你要把这个问题层层抽象：迷宫 -> 图的遍历 -> N 叉树的遍历 -> 二叉树的遍历。然后让框架指导你写具体的解法。

对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。

数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。这也就是数据结构的使命。

如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。

线性就是 for/while 迭代为代表，非线性就是递归为代表。再具体一步，无非以下几种框架：

数组遍历框架，典型的线性迭代结构：

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

链表遍历框架，兼具迭代和递归结构：

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

二叉树遍历框架，典型的非线性递归遍历结构：

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

二叉树框架可以扩展为 N 叉树的遍历框架：

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。图可能出现环？这个很好办，用个布尔数组 visited 做标记就行了。

所谓框架，就是套路。不管增删查改，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了，下面会具体举例。

先刷二叉树，先刷二叉树，先刷二叉树！二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。

只要涉及递归的问题，都是树的问题。

数据结构的基本存储方式就是链式和顺序两种，基本操作就是增删查改，遍历方式无非迭代和递归。

刷算法题建议从「树」分类开始刷，结合框架思维，把这几十道题刷完，对于树结构的理解应该就到位了。这时候去看回溯、动规、分治等算法专题，对思路的理解可能会更加深刻一些。

Talk is cheap. Show me the code.

Stay hungry Stay foolish

You build it. You run it.

Go big or go home

Done is better than perfect

Eating our own dog food

https://blog.csdn.net/cleveland_/article/details/89373062

https://www.nowcoder.com/question/next?pid=27976983&qid=235783&tid=55263574

最后不输出空格

for (int i= 0; i < N; ++i) {
    cout << (i != N-1 ? (to_string(nums[i]) + " ") : to_string(nums[i]));
}

for (int i= 0; i < N; ++i) {
    if (i == 0) cout << nums[i];
    else cout << " " << nums[i];
}

for (int i= 0; i < N; ++i) {
    if(i == 0) printf("%d",a[i]);
    else printf(" %d",a[i]);
}

// [23,12,34,56,33]
#include<stdio.h>

int main(void) {
    vector<int> a(5, 0);
    scanf("[%d,%d,%d,%d,%d]", &a[0], &a[1], &a[2], &a[3], &a[4]);
    for(auto b:a) {
		cout << b << " ";
	}
    return 0;
}
// 23 12 34 56 33

// [23,12,34,56,33]
#include<stdio.h>

int main(void) {
    vector<int> a(5, 0);
    scanf("[%d,%d,%d,%d,%d]", &a[0], &a[1], &a[2], &a[3], &a[4]);
    printf("[%d-*,%d-*,%d-*,%d-*,%d-*]", a[0], a[1], a[2], a[3], a[4]);
    return 0;
}
// [23-*,12-*,34-*,56-*,33-*]

// 23，12，34，56，33
// 23,12,34,56,33
// 23-12-34-56-33
// 23 12 34 56 33
int main() {
	vector<int> a; //最终输出
	int tmp;
    while (cin >> tmp) {
        a.push_back(tmp);
        if (cin.get() == '\n') break;
    }
 
	for(auto b:a) {
		cout << b << " ";
	}
 
	return 0;
}
// 23 12 34 56 33

/*
6
0,2,200,0,1
1,4,330,2,1
2,3,400,3,1
3,3,310,1,1
4,3,320,8,1
5,3,330,0,1
*/
int main() {
	int M;
    cin >> M;
    vector<vector<int>> data(M, vector<int>(5, 0));	// M 行 5 列
        
    for (int i = 0; i < M; ++i) {
        int tmp;
        int idx = 0;
        while (cin >> tmp) {
            data[i][idx++] = tmp;
            if (cin.get() == '\n') break;
        }
    }
}

无脑法

cin>>ch>>age>>ch>>id>>ch>>a>>ch>>b>>ch>>c>>ch>>d;

// 23，12，34，56，33
// 23,12,34,56,33
// 23-12-34-56-33
// 23 12 34 56 33
int main() {
	vector<int> a(5); //最终输出
	char ch;
    
    cin >> a[0] >> ch >> a[1] >> ch >> a[2] >>ch >> a[3] >> ch >> a[4];
 
	for(auto b:a) {
		cout << b << " ";
	}
 
	return 0;
}
// 23 12 34 56 33

void stringSplit(string str, char split, vector<int>& nums)
{
    istringstream iss(str);	// 输入流
    string token;			// 接收缓冲区
    while (getline(iss, token, split))	// 以split为分隔符
    {
        if (token == "#") 
            nums.push_back(-1);
        else
            nums.push_back(atoi(token.c_str()));
        cout << token << endl; // 输出
    }
}

vector<int> nums;
stringSplit(data, ',', nums);

题中，常常要求读入一行字符串，而这串字符里面可能有空格、制表符等空白字符，如果直接用 %s 是不可以的

// "0:start:0"
// "1:start:2"
// "1:end:5"
// "0:end:6"

char type[10];
int idx, timestamp;
sscanf(log.c_str(), "%d:%[^:]:%d", &idx, type, &timestamp);

%[0-9] 表示只读入’0’到’9’之间的字符

%[a-zA-Z] 表示只读入字母

%[^a-z] 就表示读入小写字母之外的字符。 ^ 表示除XXX之外。

"%n[^=]" 读入"="号前的至多n 个字符

在符号前面加^，比如 “%[^:]” 就是除冒号其他字符都可以输入，唯独忽略冒号，可输入的字符是除去冒号的字符集补集。 '-' 是范围连接符，当然也可以直接列出需要读入的字符。

%c 一个单一的字符 %d 一个十进制整数 %i 一个整数 %e, %f, %g 一个浮点数 %o 一个八进制数 %s 一个字符串 %x 一个十六进制数 %p 一个指针 %n 一个等于读取字符数量的整数 %u 一个无符号整数 %[] 一个字符集 %% 一个精度符号

Nvidia & Google Style

当只有数据成员时使用 struct, 其它一概使用 class.

https://zh-google-styleguide.readthedocs.io/en/latest/google-cpp-styleguide/formatting/#section-7

• 命名

// 文件命名
- 全部小写
- 分割用下划线_
- .cpp 源文件
- .h   头文件    
- 内联函数尽量放在 .h 文件中
    
    
    
// 类型命名
- 首字母均大写
- 不包含下划线
- 先public 后private    
class UrlTable { ...
class UrlTableTester { ...
struct UrlTableProperties { ...
typedef hash_map<UrlTableProperties *, string> PropertiesMap;
using PropertiesMap = hash_map<UrlTableProperties *, string>;
enum UrlTableErrors {}
    

// 变量命名
- 一律小写
- 单词之间用下划线连接
- 类的成员变量以 "m" 开头不用接下划线，struct 不用
    
// 常量命名 具有静态存储类型的变量 静态变量或全局变量
- 命名时以 "k" 开头, 大小写混合

// 函数命名
- 大小写混合
- 取值和设值函数则要求与变量名

• 循环和条件语句

if (b) {          // if 条件语句和循环语句关键字后均有空格.
} else {          // else 前后有空格.
}

while (test) {}   // 圆括号内部不紧邻空格.
        
for (int i = 0; i < 5; ++i) {}

switch (i) {
  case 1:         // switch case 的冒号前无空格.
    ...
  case 2: break;  // 如果冒号有代码, 加个空格.
}

• 操作符

// 赋值运算符前后总是有空格.
x = 0; 

// 二元操作符也前后恒有空格, 不过对于表达式的子式可以不加空格.
v = w*x + y/z;
v = w * (x + z); // 圆括号内部没有紧邻空格.

// 在参数和一元操作符之间不加空格.
x = -5;
++x;
if (x && !y) {}

• 指针和引用表达式

句点或箭头前后不要有空格. 指针/地址操作符 (*, &) 之后不能有空格.

• 返回值

// 可以用圆括号把复杂表达式圈起来, 改善可读性.
return (some_long_condition &&
        another_condition);

• 比较

A．假设布尔变量名字为flag，它与零值比较的标准if语句如下。
1　if (flag)
2　if (!flag)
    
B．假设整型变量的名字为value，它与零值比较的标准if语句如下。
1　if (value == 0)
2　if (value != 0)

C．假设浮点变量的名字为 x，它与 0.0的比较如下。
1　if ((x >= -EPSINON) && (X <= EPSINON))
2　if ((x < -EPSINON) || (X > EPSINON))
其中，EPSINON是允许的误差（精度）。
    
D．指针变量 p与 0的比较如下。
1　if (p == NULL)
2　if (p != NULL)

• I/O

hacking C++

https://oi-wiki.org/graph/shortest-path/#_1

Data Structure Visualizations

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

VisuAlgo.net/zh 数据结构和算法动态可视化 (Chinese)

https://visualgo.net/zh

https://algorithm-visualizer.org/greedy/kruskals-minimum-spanning-tree

新手会归并排序，快排，翻转链表，前中后序二叉树，二分法，dfs和bfs各一道，加01背包，以及股票问题就够了。 不面头部四家，这个难度差不多够用了

主要我觉得国内公司考图的概率太小了，面试不考，笔试总有

笔试考图特别多，不过也基本上不涉及这些算法，都是用并查集来做

阿里手撸红黑树

真没听说过谁面阿里手撕红黑树代码的，插入删除讲个流程就差不多了

https://www.cxyxiaowu.com/7072.html

四个月 solve 约 550 道题 (难度分布大概是 4 : 6 : 1)

下面这篇文章是我通过大约五天时间训练完绝大部分 滑动窗口 类型的经典题后，再用 2 天时间归纳总结的一套思维框架。运用它可以很快秒杀绝大部分该类型中档题。而那些同类型的困难题，到头来你会发现也只是基于同一框架多加了几个 components (其他框架) 而已 ，其核心**依旧不变。 [滑动窗口真滴简单!] 闪电五连鞭带你秒杀12道中档题 (附详情解析)https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/

一段时间内 (一般是5 ~ 7天) 只做该类型题目, 结合其他质量高的题解以及自身的见解归纳总结出一套属于自己的框架。

一个齐全的板子

http://pepcy.cf/icpc-templates/003Graph/sssp.html

ACM/ICPC Tricks

一些基本算法和数据结构(队列 栈 树 图 并查集 堆 DFS BFS 最短路 最小生成树 拓扑排序 动态规划 贪心 搜索 KMP 哈希 Trie AC自动机 快速幂 逆元 费马小定理 欧拉函数 素数筛 分解质因数)

[kuangbin带你飞]专题一 简单搜索[kuangbin带你飞]专题四 最短路练习 [kuangbin带你飞]专题五 并查集 [kuangbin带你飞]专题六 最小生成树 [kuangbin带你飞]专题十二 基础DP1 [kuangbin带你飞]专题十四 数论基础 [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher [kuangbin带你飞]专题十七 AC自动机

一些进阶的算法以及复杂一些的数据结构（树状数组 线段树 平衡树 后缀数组 二分图匹配 网络流 费用流 割点 桥 强联通 双联通 最近公共祖先 四大DP(数位dp 区间dp 状压dp 概率dp) 博弈论SG函数 ）

[kuangbin带你飞]专题七 线段树[kuangbin带你飞]专题九 连通图 [kuangbin带你飞]专题十 匹配问题 [kuangbin带你飞]专题十一 网络流 [kuangbin带你飞]专题十五 数位DP [kuangbin带你飞]专题十八 后缀数组 [kuangbin带你飞]专题二十一 概率&期望 [kuangbin带你飞]专题二十二 区间DP

值得一提的是位运算，应当了解电脑中数据的存储方式，很多时候利用位运算帮助做题非常重要，如树状数组的lowbit，状压DP，快速幂等，每次我看到这些的时候都深深的感受到二进制的神奇。

基础的内容：

BFS、DFS、二分、三分、筛法求素数、快速幂、并查集、矩阵运算及快速幂、最短路相关（Dijkstra， floyd，ford，SPFA）、基础DP（LIS、LCS、记忆化搜索等）、网络流（EK、Dinic、ISAP+gap）、KMP、线段树、树状数组、二分图、最小生成树（Prim、Kruskal）、计算几何基础等

第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打

1.最短路(Floyd、Dijstra,BellmanFord)

2.最小生成树(先写个prim,kruscal要用并查集，不好写)

3.大数（高精度）加减乘除

4.二分查找. (代码可在五行以内)

5.叉乘、判线段相交、然后写个凸包.

6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)

7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.

8.调用系统的qsort, 技巧很多，慢慢掌握.

9.任意进制间的转换

第二阶段：练习复杂一点，但也较常用的算法。

1.二分图匹配（匈牙利），最小路径覆盖

2.网络流，最小费用流。

3.线段树.

4.并查集。

5.熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp

https://blog.csdn.net/u012139398/article/details/43346667

图论部分：(非常独立)

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

1. 图的邻接表存储（不需要学邻接矩阵，那个没用）: 邻接表存储

2. 图的深度优先搜索和广度优先搜索，网上资料实在太多啦！

3. 拓扑排序：拓扑排序

4. 最短路：SPFA算法和(堆优化的)Dijkstra算法，理解最短路图的概念，理解平面图最小割与最短路的关系：

5. 1. SPFA正式比赛慎用。
   2. 堆优化Dijkstra

6. 欧拉回路：欧拉回路

7. tarjan算法求强联通分量、求边的双联通分量、求割点、求桥：tarjan求强连通分量+缩点+割点/割桥（点双/边双）以及一些证明 - Styx-ferryman - 博客园

8. 二分图的概念，匈牙利算法和时间复杂度为(n^3)的KM算法：

9. 时间复杂度为n^3的KM算法可以只知道用途并且把代码抄到板子上，代码参考UOJ上面比较快的二分图最大权匹配的板子即可。

10. 匈牙利算法要熟悉原理及其变形：匈牙利算法

11. 用Dinic算法求网络流，费用流：[算法]网络最大流Dinic - LinZhengmin - 博客园

数论/数学部分：

1. 费马小定理、欧拉定理：费马小定理及欧拉定理，并且会：

2. 1. 利用它们在O(logn)的时间复杂度内计算一个数的逆元

3. 素数筛法，请务必掌握的是"线性筛"：线性筛筛积性函数 - yyys - 博客园

4. 1. 另外，请一定要记住"线性筛"强调的是"线性筛不仅能筛出素数，还能筛一些积性函数"。
   2. 上面说的这句话在"莫比乌斯反演"题目里尤为重要。

5. 容斥原理（基础）。

6. 辗转相除法，扩展欧几里得算法，会抄不互质的CRT的板子：

7. 1. 扩展欧几里得

8. Lucas定理等一系列组合数取模的计算：组合数取模方法总结

9. 解二次剩余：二次剩余Cipolla算法学习笔记 - bztMinamoto - 博客园

10. BSGS算法：BSGS算法 - 小蒟蒻yyb - 博客园

11. 线性基：线性基

12. 高斯消元：高斯消元，另外注意在模意义下高斯消元的时候把除法改为乘以逆元。

13. 莫比乌斯反演及一系列反演问题：

14. 1. 学会简单的莫比乌斯反演并推出式子，更深的就稍微放过吧。ACdreamer的博客

15. 多做点基于容斥的计数题，会抄FFT的板子。

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

https://www.cnblogs.com/twilight-sx/p/9064208.html

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

1. KMP算法：KMP算法

2. 扩展KMP：扩展KMP算法小记 - Dilthey - 博客园

3. 字符串HASH：字符串HASH

4. 1. PS: 关于hash类的题目有不少，比如奇怪的树hash，需要单独去学。
   2. 有概率配合哈希表(C++中的map)使用，比赛时智力记得上线。

5. Manacher：Manacher算法的详细讲解

6. 1. 知道manacher的回文半径有什么用，怎么用，稍微做两道题就行了。

7. Trie树/字典树：Trie（前缀树/字典树）及其应用 - bonelee - 博客园

8. AC自动机及Trie图：Trie图（DFA），AC自动机 - AC_Von - 博客园

9. 1. 学完Trie图之后对于AC自动机的用法会减少，基本都是用Trie图的。
   2. 意识到fail指针形成了一棵树，并学会在fail树/Trie图上进行DP
   3. 做几道相关的DP题

10. 后缀数组(SA)：后缀数组

11. 1. 其实下面的SAM可以求后缀数组，不想学就算了。(碰到出题人卡SAM就喷出题人)

12. 后缀自动机(SAM)：后缀自动机

13. 1. 依旧是需要学会SAM上的DP，并意识到parent树的niubi之处。多做题。
    2. 但一般SAM上面的DP就会比较难，甚至可以复合其它的数据结构，比如Link-Cut-Tree（LCT）：（据某毒瘤出题人说“我出的那道LCT+SAM的题被学军的同学A穿了，感觉OI选手还是强啊”）

14. 回文树：回文树算法，建议去看看论文。

动态规划(DP)：

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

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

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

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

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

1. 记忆化搜索：主要用于不是循环结构的递推表达式状态的计算

2. 背包dp：我的观点是没必要看背包九讲，之后自己刷题刷多了自然都会了。

3. 树形dp：树形DP入门学习 - seaupnice - 博客园

4. 1. 树形dp比较常见，虽然知道这一点并不能帮你做题。
   2. 一般是考虑子树/相邻儿子对于当前节点的贡献，需要多刷题总结。

5. 区间dp：入门题

6. 状态压缩dp：一些题目

7. 1. 一些另外的题目：为什么只有题目？……这个问题问得好啊，因为这个只能刷题QAQ

8. 插头dp：两篇文章: 插头dp && 基于连通性状态压缩的动态规划问题 - 百度文库

9. 1. 题目自己找咯~

10. 基于数据结构优化的dp：(ps：以后会稍微谈谈各种递推式的优化，优化套路差不多)

11. 1. 前缀和/前缀最大值/...优化dp：CF601C Kleofáš and the n-thlon(期望+前缀和优化dp)
    2. 单调队列优化dp：不太像dp的dp
    3. 树状数组/线段树优化dp：[noip科普]关于LIS和一类可以用树状数组优化的DP - liu_runda - 博客园
    4. 斜率优化dp：制糕神的算法工坊：动态规划的斜率优化——从入门到入土

12. 一个奇怪的dp**：管道取珠

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

1. 链表：链表实战（带图分析）

2. 哈希表(C++常用MAP)：制糕神的算法工坊：OI/ACM中的哈希表，一些哈希算法以及题目

3. ST表：ST表的原理及其实现 - 真是啰嗦 - 博客园

4. 堆：C++里的priority_queue……会用就可以啦，原理不是必须要懂。

5. 并查集：并查集

6. 1. 如果不会线段树分治，可以只学习路径压缩的并查集。
   2. 如果会线段树分治，"按大小启发式合并的并查集"非常合适。

7. 单调队列：简单数据结构总结--单调队列 - dreagonm - 博客园

8. 树状数组：树状数组详解 - Xenny - 博客园

9. 线段树：线段树 从入门到进阶 - Dijkstra·Liu - 博客园

10. 1. 线段树的动态开点形式：线段树 动态开点 - Lonely.Devil - 博客园

11. 平衡树：

12. 1. 旋转Treap&&非旋转Treap：旋转/非旋转treap的简单操作 - F.W.Nietzsche - 博客园
    2. Splay：Splay详解 - JSOI爆零珂学家yzhang - 博客园 (其实Splay不算是平衡树)
    3. 其实旋转的Treap用处不是太大……

13. 启发式合并：数据结构：启发式合并 - 静听风吟。 - 博客园

14. 1. 合并的对象不仅限于并查集，线段树，平衡树。
    2. 其基本**有点类似于贪心。

15. 树链剖分，可以用于求LCA，一般绑定线段树使用：树链剖分详解 - Ivanovcraft - 博客园

16. K-Dtree: K-D TREE算法原理及实现 - 采男孩的小蘑菇 - 博客园

17. 莫队算法：莫队算法--从入门到黑题 - WAMonster - 博客园

18. 可持久化数据结构：可持久化线段树总结（可持久化线段树，线段树） - Flash_Hu - 博客园

19. 1. 可持久化Treap - permui - 博客园

    2. 如果可以离线，请千万不要为了秀自己的代码能力而写可持久化，因为：

    3. 1. 写出来是在秀自己的代码能力
       2. 写不出来是在秀自己的智力

20. 线段树分治： [学习笔记]线段树分治 - Miracle - 博客园

21. CDQ分治：CDQ分治总结（CDQ，树状数组，归并排序） - Flash_Hu - 博客园

22. 1. 常用来解决3维偏序问题，离线+排序降一维，CDQ分治降一维，线段树降一维。

23. 放弃那些奇奇怪怪的树套树吧，比赛的时候没人愿意考也没人愿意写。

计算几何(非常独立)：

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

1. 基本的点积、叉积概念，基本向量代数运算，会推微积分的式子。

2. 凸包的计算(用叉积，尽量规避三角函数)：向量积&&凸包算法 - Go!Adela - 博客园

3. 1. 哪怕凸包不会求，凸壳也要会求，这句话是写给要学习"动态规划"的ACMer的。

4. 旋转卡壳: 旋转卡壳

5. 1. 利用旋转卡壳O(n)求极大三角形的算法已经被hack掉了，如果之后在网上看到请不要抄O(n)做法。

6. 半平面交:（先看4.1中的内容） 半平面交

7. 1. 半平面交与凸包表现出高度一致性：半平面交对偶转凸包问题 - 博客 - Trinkle的博客
   2. 心疼一秒做DP题的：上面的半平面交对偶转凸包的东西在斜率优化里依然需要用到。

8. k次圆覆盖问题：k次圆覆盖

9. 辛普森积分：辛普森积分暴力大法好

10. 模拟退火：浅谈玄学算法--模拟退火 - M_sea 的博客 - 洛谷博客