C++模板库的使用
主要包括：
- 序列式容器：array（定长），vector（单向插入），deque（双向插入），list（双向链表），forwardlist（单向链表）
- 关联式容器（节点组成的红黑树）：set（集合，有序存储互异元素），multiset（允许相等），map（键值对，字典/hashmap），multimap（允许key相等）
- 无序（关联式容器）：unordered_set/multiset, unordered_map/multimap，无序，只关心存在
基础，熟悉输入输出
-
size clear等基本方法
-
迭代器
1 | for (vector<int>::iterator iter = data.begin(); iter != data.end(); iter++) |
-
scanf输入 printf输出 在C++中使用他们也更好
-
长字符串换行
-
开double 开longlong
基础算法
main函数必须是int返回必须return0
暴力破解
枚举骗分
包含头文件#include<algorithm>，里面有常用的容器算法，包括排序，查找等等，不用造轮子。
头文件#include<ctype.h>包含大小写转换，字母数字判断
打表，用事先写好的常量字符串优化程序
模拟
课堂算法分析笔记Lesson1
背包问题的求解
贪心
多项式时间算法
输入长度翻倍，运行时间最多会慢常数倍。也就是说，我们不希望随着n的增长，多消耗的时间被n影响太多。1：1的增长已经很好了。多项式算法中，a和b通常不会太大
渐进分析
-
渐进上界：$O(g(n))$意味着，对于fn来说，存在一个足够大的c和n0，满足任意的$n>=n_0$，$0<=f(n)<=cg(n)$。“最差情形”
-
渐进下界：同理的说法，存在c在n足够大的时候…
-
渐进紧界：既是又是，例子：fn=32n2+17n+1，n2既是上界又是下界
任何基于比较的排序算法最差情况下都需要比较至少$O(nlogn)$次 —-这是错的时间复杂度的限制并不限制做几遍，logn我二分查10次也是logn
循环数组查找：可以确定拐点加左右二分
Lesson2 图
-
连通性问题
-
最短路径
-
搜索
BFS树：按BFS搜索顺序（每一层Li画树的一层），中间连虚线（可以不画）
结论：原图中有边的两个点在BFS树中层数至多相差1
停止：所有当前轮次的点的邻居都已经出现在已搜索过的点集里
事实上，只要通过一个确定性的步骤（未必是BFS,DFS），每次找邻居，总能找到所有点。只是代码逻辑会清晰
连通分支：一个点集而非一个子图。包含S的连通分支指从s出发能到达的点集
DFS树
有向图，强连通（相互可到达）——强连通的判断（Kosaraju算法，反向边两次BFS）为什么？
有向无环图（DAG）和拓扑排序：如果g中包含一个拓扑排序，则G必定是一个有向无环图
如何选择数据结构：看我们在干嘛，增删查改哪个更多，不同的数据结构擅长不同的操作 如DAG的拓扑排序：总是查找某个（入边）量最小的点–优先队列
Lesson3 贪心
大方向只有 贪心 分治 动态规划
按某种顺序排序，贪心的关键是确定比较的依据
区间调度问题
记一下最少冲突区间的反例图
算法反例 必考
反证最早完成时间是最优策略：假设它不最优然后和最优对比，找最开始不一样的一项
保持领先证明贪心算法的任意性/最优解：和一个假想的”最优解”相比，采用该算法在每一步都不会获得更差的结果，即可说明该算法最优，递推证明，第一步…第k步都对了，第k+1步也是对的
最小化延迟调度倒置？
如果有倒置那么必定有相邻倒置：反证，对任意一个不相邻的倒置a和b,那么两者之间夹的任务要么和a倒置要么和b倒置，要么，c比a早和a出现倒置，要么c比a晚和b倒置然后，交换两个相邻倒置，不会对延迟有任何增大的变化并且会减少倒置
交换论证证明贪心算法的任意性/最优解: 和一个任意序列相比，通过按照我们的贪心指标交换两个该序列的元素让结果更靠近我们的算法而且结果并不会更差。反复交换即可说明我们的算法是最优解。反证证明，对任意序列按指标两两交换直到结果是我们的贪心策略。
Lesson4 分治
递推 f(n)=2f(n/2)+O(n) nlogn的来历每层的“治”都是On合并，一共有logn层，画递归树
不同的a和b要会算总的复杂度 f(n)=af(n/b)+O(n)，递推
如果是f(n)=T(n)+O(n2)，那么结果是n方而非n方logn
逆序对计算
暴力:n^2扫描
分治：拆开算之后，关键是统计合并起来有多少逆序对。先排序之后然后指针扫描一遍，因为排好了所以右侧的全部逆序，扫一遍On即可。
归并排序
最近点对问题
主定理
常见分治递归的通解：三个分治算法的参数abf$T(n)=aT(n/b)+f(n)$，分别对应子问题数量，大小减小规模，组合子问题的复杂度
通项公式——几何级数求和（等比数列）。见ppt，判断r和1的大小关系，只对n的c次幂适用
分治乘法
Lesson5 动态规划DP
解过的不要再解
加权区间调度
找最大权重子集。我们没有通项，但是希望能用目标结果的更小下标的递推式表示
选择第j项？不选第j项？逐个缩减问题规模。我们总是希望将OPT(n)用1-n-1表示，然后对n讨论。
暴力
本质是有一些顺序的枚举。最好最坏情况？能缩减更多规模的机会 最差$2^n$，递归二叉树
自顶向下动态规划（备忘录）
模拟一次递归返回的过程。暂存子问题j的结果在M[j]中，瓶颈在排序，最后就遍历一遍就行了。
背包问题
贪心的核心是排序指标，DP的核心是定义重叠子问题
同时考虑物品和包重量。如果不选i,那就是OPT(i-1,w)，如果选了，就对应缩小包的空间OPT(I-1,w-wi)+Vi。填一张二维的表
回溯看来源，时间复杂度$O(nW)$，W是输入的变量，不代表他关于n是多项式时间。但是算法严重依赖于重量是整数的假设。
字符串对齐
Lesson6 最小流和最大割
并查集？？唉
LessonN 线段树
堆式存储 查询2logn求和
Lazy Tag 对上负责？
每一行最多只有两个蓝色区间和2个红色区间
批量修改会在能覆盖的地方就停，然后直到下次查询再修改。
多个lazy tag,优先高的先下传
统计量可合并可以使用
树状数组
无需额外空间 长度仍然n
修改对应位置 线段树加前缀
Lesson N+1 kmp算法——字符串匹配
依据一张部分匹配表快速跳过$O(m+n)$