我想在这里把一些好玩的东西写上。
next_permutation
这个函数不错，是枚举全排列的，在algorithm库中。
fill
这个过程可以说是memset的扩展，使用方法：fill(a, a + n, 100);
DP的简单优化
一句话概括：
利用已经计算的结果。
经典的例题就是完全背包问题。还有去年noip的飞扬的小鸟以及poj 2392。
greater<>
这个用于priority_queue的最小堆，用法priority_queue<int, vector<int>, greater<int> >。
并查集记录rank
\(rank\)即是树的高度，每次合并将小的向大的合并。
二分图的定义
最小着色点是\(2\)的图称作二分图。
Prim算法
首先，假设有一棵只包含一个顶点\(v\)的树\(T\)。然后贪心的选取\(T\)和其他顶点之间相连的最小权值的边，并把它加到\(T\)中。
基于Dijikstra算法的“动态规划”
这个方法不得了，以前好像做过类似的题。
每次找一个不可能被别人更新的点来更新别人！
差分约束系统
如果要最大化答案，那就是求最短距离（也就是最大值对应着的最短距离）。
最短路对于每条权值为\(w\)的边\((v,u)\)，满足\(d(v) + w \geqslant d(u)\)，即\(d(v) - d(u) \geqslant w\)。
天大的疑问：如果是\(d(v) + d(u) \geqslant w\)能做吗？
gcd的形象理解
用最小的正方形可以无缝隙地填满整个大正方形！
ax+by=gcd(a,b)的解的大小
一直写ext_gcd都提心吊胆，不知道会不会爆掉，事实上\(|x| \leqslant b ,|y| \leqslant a\)。
证明（归纳法）：
在\(b=0\)的前一步，显然成立。假设调用extgcd(b, a % b, y', x')后有\(|x'| \leqslant b, |y'| \leqslant a % b\)，那么
\[ |x| = |x'| \leqslant b, |y|=|y' - (a \div b) \cdot x'| \leqslant |y'| + (a \div b) \cdot |x'| \leqslant a % b + (a \div b) \cdot b = a \]
一个脑筋急转弯
求\([a,b)\)中有多少个素数？\(a,b(10^{12}),b-a(10^6)\)
在筛\([2, \sqrt {b} )\)的表时，将\([a,b)\)也筛掉。因为\([a,b)\)中的数的最小质因数不超过\(\sqrt {b}\)！
素数判定
现在终于知道为什么要用二次探测定理了，因为有Carmichael Number的存在。
但是，这一章的最后一个问题难倒我了！
有\(O( \sqrt {n} )\)的算法判断
Carmichael Number。