先从分数比较好拿的第二三四题开始

1. 能否用函数完成相同的操作，简化逻辑

第二题

排序

结构体，关键字operator<或者cmp，哈希映射，四舍五入round，精度问题1e-8，排名的双指针写法，首部或者尾部的哨兵优化代码，getline前cin输入要getchar去除空行，有序区无序区，插排，归并，快排，堆排的特点

链表

数组模拟，初始化，输入格式(先输入首地址)，st数组标记地址，vector存储地址简化操作(这里的next通过访问下一个元素的地址即可)

哈希表

1. 查询类问题，可能分为
   (1)已经预处理好哈希表
   (2)边输入查询边加入到哈希表(可能事先需要另一个预处理的哈希表)，此时枚举预处理好的数组元素是否已经在当前的哈希表中
2. 哈希冲突
   二次探测法(找到或者遇到空位为止)空位可以根据题目的数据进行设置，全是正整数，设空位为0。或者直接设置空位为INF
3. 映射类问题，string到结构体

并查集

1. 关于边与点，结构体存储边的两个端点，每次将边的两个端点进行合并
2. 根节点 + 信息数组维护当前联通分量的信息，如资产，人数等。以及合并时新根节点的选择
3. 遍历所有点找出每个连通分量的根节点，根节点的数量即为连通分量的数量，连通分量可以通过(1)该方法和(2)合并时num–求得
4. 以组为单位进行组内合并

基础算法 + 数据结构

1. 递归，参数定义
2. 归并， 二路 或者多路
3. 前缀和， 求的是区间和，区分好点与线段之间的关系。环状点之间距离的求法，(1)直接求k j间的距离(2)先求j到终点的距离， 再求起点到k的距离。记得最后作差时的边界
4. 双指针，i，j不会退，双重for循环的优化，使用条件：序列单调性，可以先排序再使用双指针
5. floodfill洪水灌溉bfs，(1)方向dx，dy，dz的确定，对应好代码中的坐标轴。(2)标记访问过的点，入队列时标记，第一个点容易忽略。(3)多个源点进行遍历，直接在多重for循环中，边标记，边进行遍历
6. 枚举，枚举答案进行验证
7. 栈(匹配类问题)，弹出序列，栈顶对应pop起始
8. 对顶堆得中位数(set维护实现1查询2删除3插入)，up，down。比较值之前需要进行非空判断，adjust进行调整，down>=up+1每次取down的顶即为中位数
9. 前缀和的单调性搭配双指针，实现ij不回退
10. 回文，中心扩散，区间DP

第三题

普通树

1. 存储方式， 建树，各个节点的值互不相等，哈希map按照值进行l，r的映射
2. dfs：逻辑顺序，返回值(深度，中缀表达式string)，参数(u，father，depth)，信息数组(每一层的节点数目，has_father[]数组找根借点)，回溯
3. 遍历的起点，唯一根节点01，每个点都做一次遍历
4. 叶子结点的标记

二叉搜索树

1. 注意题目中的定义，左右子树大于等于的说法
2. 中序遍历有序，先序数组的第一个元素x对应中序数组第一个与x相等的元素
3. 完全二叉搜索树，层次遍历即为下标从一开始顺序遍历到最后
4. 借助栈进行建树，看push的上一个操作确定当前push的是last的左孩子还是右孩子，last根据上一步确定，为push(x)则取x为last，为pop则取弹出的值
5. 根节点的确定，bool类型的has_father数组标记每一个节点是否有父节点
6. 完全二叉树的检验，根据最大节点的下标是否比标准更大
7. 插入法建立二叉搜索树，参数表中当前节点的编号传引用，当前节点编号为0表示为空，应该对编号u和w[u]进行赋值

AVL树

1. 几个操作，get_balance(int u), update_h(int u), insert(int &u, int x)，R(int &A)
2. 二叉搜索树的本质，插入的方法同上，找到空节点为止，插入后检查平衡因子。更新u的h(后序逻辑更新，即更新之前，左右孩子已经更新)
3. 4种不平衡状态，以及对应的调整操作，直接记住结论即可。
4. 左旋右旋的操作画图写出，更新AB的h
5. 层序遍历bfs要记录的值是节点编号，是下标，还是值
6. 红黑树，检查点(1)根节点为黑色(2)sum表示从叶子到u路径上的黑色节点数目，先检查子层，(3)当前节点为红色，子节点必须为黑色

供应商

1. p[]记录每个点的父节点，f[]到根节点的距离(记忆化赋值)
2. 从当前节点向根节点方向进行，自下向上递归
3. 对于根节点以及叶子节点的标记与查找

堆(完全二叉树的实现方式)

1. 叶子结点的判断，2 * u > n即没有左孩子
2. 下标从1开始计算

最低公共祖先

1. 爬山法：p记录当前节点的父节点，depth记录当前节点的深度，原理，公共祖先必然在同一层的同一个，不相等则更深的那个向根节点靠近
2. 区间法，针对元素在中序数组中的相对位置进行区间的折半查找

第四题

单源最短路Dijkstra

1. 根据点的数量选择邻接矩阵，邻接表进行图的存储(记得h初始化)
2. 选择朴素版本(n^2 + m)还是堆优化版本(mlogn)，点超过1e4直接堆优化，一般而言带入分析一下即可
3. 有向图还是无向图，重边取最小值
4. g[][]，c[]，w[]等点权或者边权，h[N]，e[M]，w[M]，line[M]，ne[M]等根据idx地址进行访问的属性
5. 多关键字的更新，dist，sum，cnt，pre，info表示从源点到达当前点的属性值
6. fill_zero对不足四位的进行填充
7. string哈希映射unordered_map<string, int> to_n;和string to_s[N * 2];，有时需要加离散化
8. dfs时bool数组st进行标记

一些特殊图的考察

1. 结构体Edge数组记录每条边的两个端点，st数组标记访问
2. dfs找信息
3. 有关记录一个编号或者数值出现位置的数组，拓扑排序，哈希排序的变式(图论解决)

第一题

1. 对于首个元素的特判方法，下标判断，变量初值(对于初始化为0或者INF)判断

字符串

1. 数字与字符串的转化，灵活使用stoi，to_string，substr
2. 输出格式，借助一些小变量cnt，success
3. 打表预处理
4. 维护最值变量
5. 字符串哈希，bool数组记录出现与否，record数组记录出现次数，当然建议直接unordered_set,unordered_map比较方便
6. 双指针

for (int i = 0,j = 0; i < str.size(); ++i) {
    string temp;
    if (check(str[i])) {
        j = i;
        while (j < str.size() && check(str[j])) {  // 强烈推荐使用
            temp += tolower(str[j]);
            j++;
        }
        record[temp]++;
        i = j;
    }
}

1. sscanf(“字符串”, “%d:%d…”, &a, &b, &c …)通过字符串对变量进行赋值
   sscanf("2013/02/13 14:55:34","%d/%d/%d %d:%d:%d",&year, &month, &day, &hour, &minute, &second);
2. sprintf(“”)变量生成格式化字符串
   sprintf(format_time, "%02d:%02d:%02d", day, hour, minute);

排名

时间处理，排队

1. 如果时间格式是统一的，可以按照string变量进行输入，按照字典序进行比较
2. 归一化处理，时间统一到同一个起点时间，然后根据需要将单位同一为minute或者second，熟练进行正向逆向的转化。
3. 格式化输入时间scanf(“”)
4. 关于时间点和时间段的理解和处理。尤其是时间点的边界点

数字处理

1. 科学计数法，系数和指数，找到小数点分割数字，并前移
2. 取k位和补零