主定理可以用来分析递归算法的时间复杂度（也叫渐进复杂度）。在以前，我们知道快速排序的时间复杂度是 $ \Theta (N \ast \log_2 N )$ ，我们也知道它不稳定，但是我们仿佛不知道这个 $ \Theta (N \ast \log_2 N )$ 是怎么来的……学习了主定理，我们就可以证明了～
这个“主定理”名字真的十分霸气：Master Theorem……
主定理与递归程序时间复杂度的计算
POJ 3465 Battle 题解：可“反悔”的贪心
很多题目的贪心想法都是一个简单粗暴的贪心加上可“反悔”的操作。这样可以确保答案的正确性。
Description
You're Zhu Rengong, a formidable hero. After a number of challenging missions, you are finally facing the final Boss – a black dragon called Heilong. Due to his overwhelming power, you have to plan your actions carefully.
POJ 3244 Difference between Triplets 题解：（线段树或树状数组）或（排序 + 前缀和）
坠痛苦的是，POJ 的辣鸡 G++ 编译器不支持 long long，害得我调试调了半天……
Description
For every pair of triplets, $T_a = (I_a, J_a, K_a)$ and $T_b = (I_b, J_b, K_b)$, we define the difference value between $T_a$ and $T_b$ as follows:
$$ D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b) $$
Now you are given $N$ triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?
POJ 3977 Subset 题解：折半搜索+二分查找
HDU 6447 YJJ's Salesman 题解：排序+离散+树状数组
Problem Description
YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city $A$ to southeastern city $B$. Let us assume that A is $(0,0)$ on the rectangle map and $B (10^9,10^9)$. YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at $(x,y)$ now $(0\leqslant x\leqslant 10^9,0\leqslant y\leqslant 10^9)$, he will only forward to $(x+1,y)$, $(x,y+1)$ or $(x+1,y+1)$.
HDU 5626 Clarke and points 题解：一道巧妙的贪心
斜率优化小结
在一维线性动态规划里，我们经常见到形如 $f(i)=min/max(f(j)+c_i)$（其实可以看成 $f(i)=min/max(a_i+b_j)$ ）这样形式的转移方程。朴素做法是 $\Theta (N^2)$。显然这样的形式可以用单调队列维护，优化到 $\Theta (N)$。但是如果遇到 $f(i)=min/max(a_i\ast b_j+c_i+d_j)$ 这样的，似乎用单调队列就难以维护了……因为 $a_i\ast b_j$ 既与 $i$ 有关，又与 $j$ 有关。这时候就要用到另一种优化方式：斜率优化。
C++ 终极时间优化模板
今天考试的时候遇到一题背包题目，我直接打了暴力的 0/1 背包，理论复杂度是 $\Theta (N^3\ast W)$，大概是 $10^9$ 这个级别……时限 1s，交上去就全部 TLE 了……然后我就想起了这个终极优化模板，加上以后居然全 A 了！时间居然只有 200ms 左右……
$10^9$ 级别居然都可以压过去！！！
Topcoder SRM 634 Div2 T3 SpecialStrings 题解
Topcoder Single Round Match 634 Div 2 T3 SpecialStrings 题解
Topcoder SRM 635 Div2 T3 LonglongestPathTree 题解
Topcoder Single Round Match 635 Div2 T3 LonglongestPathTree 题解