概念

分治，将较大规模的问题分解成几个较小规模的问题。
例子：猜数字游戏，从几楼扔下手机不会摔坏，查找C盘中最大的文件，黄页电话簿，翻字典。

快速排序(先找分界点再递归)

  1. // 学习目标：理解好分治的过程，讲解理论用处多，实际应用比较少
  3. void quick_sort(int q[], int l, int r)
  4. {
  5.     if (l >= r) return;
  7.     int i = l - 1, j = r + 1, x = q[l + r >> 1];
  8.     while (i < j)
  9.     {
  10.         do i ++ ; while (q[i] < x);
  11.         do j -- ; while (q[j] > x);
  12.         if (i < j) swap(q[i], q[j]);
  13.     }
  14.     quick_sort(q, l, j), quick_sort(q, j + 1, r);
  15. }

例题：输出前k大的数

归并排序(先递归再合并)

  1. // 学习目标：理解过程，实际应用会灵活多变
  3. void merge_sort(int q[], int l, int r)
  4. {
  5.     if (l >= r) return;
  7.     int mid = l + r >> 1;
  8.     merge_sort(q, l, mid);
  9.     merge_sort(q, mid + 1, r);
  11.     int k = 0, i = l, j = mid + 1;
  12.     while (i <= mid && j <= r)
  13.         if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
  14.         else tmp[k ++ ] = q[j ++ ];
  16.     while (i <= mid) tmp[k ++ ] = q[i ++ ];
  17.     while (j <= r) tmp[k ++ ] = q[j ++ ];
  19.     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
  20. }

例题：【例7.7】光荣的梦想

快速幂(拓展移位运算，二进制的理解)

求divide and conquer分治 - 图1模 divide and conquer分治 - 图2

分治的方法

  1. // 求：b^p
  3. // 思路：
  4. // 任意一个数p，可以表示成 p = 2 * p/2 + p%2
  5. // b^(2 * p/2 + p%2)，就可以拆开后，递归调用f(p/2)，递归终止边界是p == 0, return 1;
  1. // 求2^b
  3. #include <iostream>
  5. using namespace std;
  7. int f(int b)
  8. {
  9.     if (b == 0) return 1;
  11.     int t = f(b / 2);
  12.     if (b & 1) return t * t * 2;
  13.     else return t * t;
  14. }
  16. int main()
  17. {
  18.     int a, b;
  19.     cin >> b;
  21.     cout << f(b) << '\n';
  23.     return 0;
  24. }
  1. // 求a^b
  3. #include <iostream>
  5. using namespace std;
  7. typedef long long ll;
  9. int f(int a, int b)
  10. {
  11.     if (b == 0) return 1;
  13.     ll t = f(a, b / 2);
  15.     if (b & 1) return t * t * a;
  16.     else return t * t;
  17. }
  19. int main()
  20. {
  21.     int a, b;
  22.     cin >> a >> b;
  24.     cout << f(a, b) << '\n';
  26.     return 0;
  27. }

移位运算的方法

divide and conquer分治 - 图3
根据数学常识，每一个正整数可以唯一表示为若干个指数不重复的2的次幂的和。如果b在二进制下有k位，其中第i位的数字是divide and conquer分治 - 图4，那么
divide and conquer分治 - 图5
于是：
divide and conquer分治 - 图6
因为divide and conquer分治 - 图7向上取整，所以上式乘积项的数量不多于k个，
又因为
divide and conquer分治 - 图8
所以，通过k次递推求出每个乘积项，当divide and conquer分治 - 图9时，把该乘积项累积到答案中。
b & 1 运算可以取出 b 在二进制表示下的最低位， 而 b >> 1 运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历 b 在二进制表示下的所有数字 divide and conquer分治 - 图10。时间复杂度是 divide and conquer分治 - 图11。

  1. // 求 a^k mod p，时间复杂度 O(logk)
  2. // 模板请记忆
  4. int qmi(int a, int k, int p)
  5. {
  6.     int res = 1;
  7.     while (k)  //当k不是0的时候
  8.     {
  9.         if (k & 1) res = (LL)res * a % p;
  10.         k >>= 1;
  11.         a = (LL)a * a % p;
  12.     }
  13.     return res;
  14. }

例题：取余运算（mod）

  1. 输入b，p，k的值，求 b^p mod k 的值。其中b，p，k为长整型数。

例题：1234：2011

  1. 通过测试发现，2011的n次方的结果，每500个数一循环。1次方、501次方、1001……结果一样。
  2. 2次方，502次方，1002次方……结果一样。所以，尽管指数可能有200位，只需要考虑最后的3位指数就可以了。如果指数n不足3位，直接计算2011的n次方结果mod 10000就行了。

快速乘

快速乘法的说法来源于快速幂，因为两者的思想一致。快速幂是为了计算计算取模结果，的确是快的。而快速乘法主要是模数超过九次方时使用，因为两数相乘会longlong溢出，会比直接乘法慢，但是保证了正确性。所以说快速乘法并不快，想要比正常乘法快也是不现实的，快速乘法本来就是为了保证正确性而牺牲效率，自己实现了一遍乘法。要说快的话只能去和直接累加相比，就像快速幂比直接累乘取模快。

  1. // 类似快速幂
  2. // log(n)
  4. int qmul(int a, int b, int p){
  5.     int ret = 0;
  6.     while (b){
  7.         if (b & 1) ret = (ret + a) % p;
  8.         b >>= 1;
  9.         a = (a + a) % p;
  10.     }
  12.     return ret;
  13. }

STL的使用(下标问题和避免SE)

  1. //STL
  2. int pos = lower_bound(a, a + n, x) - a;
  3. int pos = upper_bound(a, a + n, x) - a;
  5. //lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。
  7. //upper_bound() 函数的功能和 lower_bound() 函数不同，前者查找的是大于目标值的元素，而后者查找的不小于（大于或者等于）目标值的元素。

例题：和为给定数

binary search二分查找(有序序列中查找元素)

二分的基础用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定。其实，写二分的时候并不容易，写check函数的时候，有很多细节之处需要仔细考虑。

  • 对于整数域上的二分，需要注意终止边界、左右区分取舍时的开闭请，避免漏掉进入死循环。
  • 对于实数域上的二分，需要注意精度问题。

二分的实现模板有很多种，以下给出的模板是yxc的，非常好用。

  1. //模板请记忆
  3. //整数二分
  4. bool check(int x) {/* ... */} // 检查x是否满足某种性质
  6. // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  7. int bsearch_1(int l, int r)
  8. {
  9.     while (l < r)
  10.     {
  11.         int mid = l + r >> 1;
  12.         if (check(mid)) r = mid;    // check()判断mid是否满足性质
  13.         else l = mid + 1;
  14.     }
  15.     return l;
  16. }
  18. // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  19. int bsearch_2(int l, int r)
  20. {
  21.     while (l < r)
  22.     {
  23.         int mid = l + r + 1 >> 1;
  24.         if (check(mid)) l = mid;
  25.         else r = mid - 1;
  26.     }
  27.     return l;
  28. }
  30. //注意，分析题意，画数轴，看mid的右边是答案，还是mid的左边是答案
  1. //模板请记忆
  3. //浮点数二分，还有循环50次的写法
  4. bool check(double x) {/* ... */} // 检查x是否满足某种性质
  6. double bsearch_3(double l, double r)
  7. {
  8.     const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
  9.     while (r - l > eps)
  10.     {
  11.         double mid = (l + r) / 2;
  12.         if (check(mid)) r = mid;
  13.         else l = mid;
  14.     }
  15.     return l;
  16. }
  18. double bsearch_4(double l, double r)
  19. {
  20.     int T = 50;
  21.     while (T--)
  22.     {
  23.         double mid = (l + r) / 2;
  24.         if (check(mid)) r = mid;
  25.         else l = mid;
  26.     }
  27.     return l;
  28. }

例题：和为给定数

例题：查找最接近的元素

二分答案(check函数的模拟)

一个宏观的最优化问题也可以抽象为函数，其“定义域”是该问题下的可行方案，对这些可行方案进行评估得到的数值构成函数的“值域”。假设评估得到的数值最高值是 s，对于大于 s 的都不合法，对于小于等于 s 的都是合法的，这样问题的值域就有一种特殊的单调性，在 s 的一侧合法，在 s 的另一侧不合法。借助二分，我们把求最优解的问题，转化为给定一个值 mid，判定是否存在一个可行方案评分达到 mid 的问题。

二分答案可以用来处理“最大的最小”或“最小的最大”问题。

常见问题：记录答案的二分写法，判断答案在哪边，check()函数经常写不准确的问题。

例题：网线主管

例题：月度开销

分形(找规律)

例题：循环比赛日程表

  1. 8位选手的循环比赛表可以由四名选手的循环比赛表根据对称性“生成出来”
  2. 分治思想：不断的把一个规模为n的问题分成4个规模为n/2的子问题
  4. //左上角(a1,b1)，右下角(a2,b2)，[begin, end]的数字组成
  5. void makelist(int a1, int b1, int a2, int b2, int begin, int end)
  6. {
  7.     //问题的边界
  8.     if (begin == end){
  9.         a[a1][b1] = begin;
  10.         return ;
  11.     }
  13.     //求解子问题
  14.     //分成四个区域，左上角区域的右下角坐标是(a3, b3)
  15.     int a3 = (a1 + a2) / 2, b3 = (b1 + b2) / 2; 
  16.     int mid = (begin + end) / 2;
  17.     makelist(a1, b1, a3, b3, begin, mid);  //左上角区域
  18.     makelist(a1, b3+1, a3, b2, mid+1, end); //右上角区域
  19.     makelist(a3+1, b1, a2, b3, mid+1, end); //左下角区域
  20.     makelist(a3+1, b3+1, a2, b2, begin, mid); //右下角区域
  21. }
  23. //函数调用
  24. makelist(1, 1, n, n, 1, n); //左上角(1,1)，右下角(n,n)，由1~n数字组成
  27. // 这道题目也可以用从小大到递推出来整个地图

例题：Fractal Streets

  1. //分形，著名的通过一定规律无限包含自身的“分形”图。

进阶的有，三分，0/1分数规划

  1. //  提高组再学

《一本通》题目

【例7.4】 循环比赛日程表
  1. //分形

【例7.5】 取余运算（mod）
  1. //快速幂

【例7.6】黑白棋子的移动
  1. //这道题目研究很长时间。找规律，写代码都花费了较长时间

【例7.7】光荣的梦想
  1. //逆序对

2011
  1. //快速幂
  2. //2011的幂次有一个规律，2011^1 和2011^501 是相同的，每500一个循环

输出前k大的数
  1. //排序

区间合并
  1. //读懂题意后，排序，从左往右贪心

求排列的逆序数
  1. //逆序对

一元三次方程求解
  1. //check函数是f(x) * f(mid) < 0， 而不是f(mid) == 0之类的

统计数字
  1. //不能用STL，排序一下，双指针就行了

查找最接近的元素
  1. //数列上进行二分查找，找边界

二分法求函数的零点
  1. //二分答案（浮点数二分模板，写check函数）

网线主管
  1. //二分答案（整数二分模板，写check函数）

月度开销
  1. //二分答案，根据题意写check函数，这块经常写不好。
  2. //理解一下，数轴上表示单调性的图，右侧区间都是答案。（如果月度开销小了话，就会需要超过M个预算周期，就不满足条件了）

和为给定数
  1. //数轴上二分查找就可以了，唯独这道题目不能用STL

不重复地输出数
  1. //直接用set<int>处理了

膨胀的木棍

花费了很长时间的题目，不太了解几何概念。

  1.     //公式，弧度，角度，PII，acos(-1)=PII，弧长= 半径*弧度
  2.     //l = degree * r    圆心角弧度数 * 半径
  3.     //r * sin(degree) * 2 = d;  弦长
  4.     //so, 2 * sin(degree) * l = d * degree
  6.     double L2 = (1 + N * C) * L; //弧长
  7.     double l = 0.0, r = acos(-1.0), ans = 0.0;  //0, 180度
  8.     while (r - l > eps){
  9.         double mid = (l + r) / 2;
  10.         if (L * mid + eps < 2 * sin(mid/2) * L2) l = mid, ans = mid;
  11.         else r = mid;
  12.     }
  14.     double banjing = L2 / ans;
  15.     double x = banjing - banjing * cos(ans / 2);
  16.     printf("%.3lf\n", x);

河中跳房子
  1. //noip2015tg
  2. //二分答案，这道题目做的时候，还是输在了写check函数上
  3. //1.怎么去表达搬走石头的操作 2.求的是最长的最短距离，也就是mid左侧都是答案，注意边界的写法
  4. //我做的时候，最初的时候，理解成了mid的右侧是答案，造成了很多迷惑。后来发现mid左侧是答案后，就迎刃而解了