基本算法思路

algorithm

基本思路

广搜 猜想(重构问题)
深搜 推理(基于性质，选择工具)
启发式搜索 根据当前推理的流程，但往往无法得到一个正确的全局函数（Intuition）

数据结构

允许存在待处理的元素，添加一个标记位，最后再处理(懒更新)
其中包括线段树的懒更新，保存index的单调队列，存在冗余项的优先队列

数组结构

1. 双向链表 + 哈希表
   hashmap O(1) 寻址（！性能可能退化）
   O(1)删除 链表
   如: LRU / LFU

2. 栈 | 双向队列
   维护一个距离上的关联, 只能增加修改两侧元素
   ! 对于弹出的元素，当前元素代表真正的解的位置，对于当前元素，栈内的元素代表解的空间
   可用于递归调用的实现
   用于运算符等涉及空间逻辑关系
   在0－1BFS中双向队列可以完成最小路径的寻找

3. 双指针
   快慢指针可以判断链表的环
   滑动窗口维护单调性
   T-F问题 区间有唯一性

4. 单调队列
   可以logn寻址，但只能增加/修改元素，或只需要弹出一侧的元素
   ! 对于弹出的元素，当前元素代表真正的解的位置，对于当前元素，栈内的元素代表解的空间
   ! 解的单调性证明：逆向考虑，若解中存在递减元素，则一定不符合条件，因此队列递增
   若弹出条件是否等于，确定弹出元素的解是否为严格小于，而当前元素可以选择严格小于，也可以选择小于等于
   在最大递增子串中可以用来更新维护贪心的状态

   数据的变化具有单调性，只需要记录当前位置即可 可以结合二分方便状态转移。

5. 离散化区间

树类结构

1. Set(红黑树)
   可以O(logn)删除，O(logn）寻址
   multiset 多个元素
   难以进行区间处理
   注意求指针距离的复杂度为O(n)， 不同于vector
   出现区间选择，删除的时候，不一定要用线段树，红黑树可以在没有元素的时候节省时间复杂度。
2. 堆 | 优先队列
   O(logn)插入
   堆无法寻址删除 但可以维护一个贪心状态
   两个堆(对顶堆)可以维护一个中位数的值
   
3. 线段树
   基于已有的区间范围，维护每个区间数值上的关系
   
4. 并查集
   logn合并集合，但不能拆集合
   通过排序，根据单调性合并，二维接雨水
   带权值的路径压缩 / 也可以bfs 蓝桥杯 查询累和

数理性质

数论

1. 组合相关
   卢卡斯定理快速计算组合
   生成next permulation
   C(n, m) = C(不包含当前元素) + C(包含当前元素) = C(n - 1, m) + C(n - 1, m - 1)
   1. 累加求和，从杨辉三角可以看出，若C(n, m)中m不变，求和可以合并
      
   2. 通过dp思想枚举最后一个元素, 防止元素重复
      
   3. 经典组合模型,小球放入箱子的组合数问题, 如存在一定需要放的无区别小球，考虑隔板法, 对于可放可不放的小球
      
2. 因子类 对于乘法逆元，egcd gcd log(n)(欧拉 需要知道质因子个数) \(a^{p - 1}\)
   对于同余问题，注意加减乘都不改变同余的特性, 整除运算会改变, 其中组合数需要用到卢卡斯定理
   对于提取公因子个数 nsqrt(n) 提取质因子nsqrt(n)
   质因数分解中剩余项为质数

图

1. 与直径相关的最长路问题
2. 删边得到最小环

函数

1. 绝对值函数，\(|x - x_1| + |x - x_2| ... + |x - x_n|\) 取中位数即可

几何

1. 求K值
2. 凸包

数值计算

1. 快速乘/幂 乘法 - 指数

2. 异或的性质 不具备分配律...

博弈论

1. 逐步贪心讨论必胜态 - 注意奇数偶数 记忆化搜索判断是否有必胜态

信息论

1. 信息量 熵 设计实验
2. 随机数的生成

算法

重新组织问题

1. 数理等价

   蚂蚁的相遇问题 - 改变身份
   根据子集还原数组 - 每次删除施加影响的数值的集合
   从Hash mask角度考虑

   子序列内不存在频次超过n/2即可删...
   证明必要/充分性 - 蓝桥杯青蛙跳

2. 预处理/枚举

   先考虑第一个或最后一个值或整体特性
   确认一种顺序 （拓扑 数值...) 考虑

   x, y选择较小的数，枚举值域 例题 Atcoder 蓝桥杯 分果果

3. 生成数据结构 建图分析 前缀和分析 区间分析

4. 逆向考虑
   给定解 判断参数的范围 / 是否满足
   (加密密码本匹配源码)

5. 计算时间复杂度 \(\sum \frac{1}{n} \sim \log n\) 实际的时间度较小

冗余/懒更新

本质在于错开处理的时间，借助一些标记后面再处理。 对于复杂计算，考虑先计算再回退 懒更新的思路 后面再解决

二分

1. f(x)的二元性
   
2. 边界的讨论

状态转移

基于一组最难满足的解

1. 转移思路
   可以通过遍历增加限制，或多求几遍值
   对存在单调条件，可以尝试多次或逆向更新
   对不满足拓扑顺序, 增加一个以当前元素结尾的条件，或预先进行一次拓扑排序
   对环的处理 - 倍增数组，限定长度为n
   对于重复数，合并反而减少了信息量（总长度有限制），单个元素的转移更加灵活，删与被删，不需计数
   对于数据量少，考虑状态压缩，枚举子集，并判断转移的有效性
   对于组合数，使用限定最后元素来定义dp，否则会重复计数, 结合组合公式，优化DP
   对涉及到多个主体的问题，需要设置步数/轮数，防止重复更新
   对于涉及多个元素联系的问题，考虑枚举还没发生的状态

2. 检验 | 优化
   画出状态转移矩阵
   最佳转移点是否离散或有单调性
   重新排列合并公式 前缀和
   转化为记忆化搜索剪枝

3. else
   注意对遍历过而不能完成的状态 -1（未遍历） - INF（失败） 区分
   可以使用map防止溢出

搜索

1. 递归搜索 (dfs)
   condition - receive - execution - return
   搜索每个子状态 - 可以结合记忆化
   汉诺塔拆分状态
   
2. 队列搜索
   dijkstra 优先队列 以单调递增量作为距离即可
   0-1 bfs有隐含条件
   
3. 基于DP的搜索
   spfa floy...
   
4. 基于贪心简化循环
   bit角度, ++ - lowbit(i)
   几何性质, 考虑两条相邻直线的k值即可

经典问题

字符串处理

1. 子串匹配类

   KMP hash trie 分隔符哈希...

2. 回文

图/树

1. 距离类
   聚点 - 源点 网络流 dijkstra spfa floy bfs dfs 剪枝
   直径等 多次dfs

2. 拓扑/分类
   拓扑排序/染色
   并查集

3. DP类

   binary lifting LCA

区间

1. 数据结构+
   优先队列 | 单调栈 | 双指针 | 线段树
   
2. 预处理
   pre/suf计算
   
3. 区间DP

编程实现

数据类型

1. 函数的返回值类型是int... 改为long long
   
2. 初始化，d[0] = 0 - d[s]
   
3. 位运算优先级低

逻辑顺序

1. 提前break and continue 影响了后面的结果
   cin / cout cur[k] = cur[k - 1]
   dp同理需要注意 dp[k] = dp[k - 1]
   
2. 注意复用的值
   链表的指向
   ! a[2] -= d 范围a[1] + a[2]

else

1. 输入输出 ? break会影响cin
   
2. 数据逻辑，存在不属于链表中的点。
   
3. auto in lambda 是c++14的特性 decltype
   
4. trick assert 小数据暴搜 大数据优化 分开两个算法
   
5. 对空间、时间、数值范围的估计