Algorithms

应该用基本的算法去解题: 利用算法的思想， 而不应该不设置边界， 用模拟，特例, 分步骤的方式去解题。 基本的算法就几种：（利用下面中的基本方法去解题，思考， 而不应该去分步骤讨论）

1. 枚举 (for loop, 枚举端点，枚举范围。 看似自由度极高，其实套路无非几种，不应该有自由度)
2. 递归和分治
3. 排序
4. 二分和倍增
5. 前缀和差分
6. 贪心
7. 构造（ 这个才是真正有自由度的地方，发现题目规律的地方，但是题目之间没有通用模板。 还没接触到，基础算法都熟练了之后，去锻炼）

数据规模	时间复杂度	算法举例
10	O(n!)	permutation 排列
20~30	O(2^n)	dfs+剪枝，状态压缩DP，组合
100	O(n^3)	floyd, DP, 高斯消元
1000	O(n^2)	朴素Dijkstra、朴素Prim, Bellman-Ford, DP, 二分
10000	O(n*sqrt(n))	块状链表，分块，莫队
10^5	O(nlog n)	排序，堆，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
10^6	O(n)以及常数小的O(nlogn)	单调队列，hash, 双指针扫描，BFS，并查集，kmp, AC. nlogn(sort, BIT, heap, dijkstra, spfa)
10^7	O(n)	双指针扫描，滑动窗口, kmp, AC自动机, 线性筛素数
10^9	O(sqrt(n))	判断素数、求平方根
10^10	O(log n)	二分搜索, 快速幂，数位DP
+∞	O(1)	数学相关算法, 高精度加减，FFT/NTT