【算法2-3】分治与倍增

如果想知道我国的人口数量,就需要进行人口普查。让每一个省份都去统计本省有多少人,然后将各省人口累加起来,就可以获得全国的人口数量。而要想知道某一个省的人口数量,可以让省里的每一个城市统计本市有多少人,然后将各市人口累加起来,就可以获得这个省的人口数量……以此类推,层层细分,最后统计一个村子或者一个小区有多少人,这个任务就很简单了。 把一个复杂的问题细分成若干结构相同但规模更小的子问题,然后将每个子问题的解合并起来,就得到了复杂问题的解,就是本章将会介绍的分治策略。

本章的最后还介绍了倍增算法。将一个较大的数字分为若干个 2^i 的和,同时维护所有长度为 2^i 的区间,可以解决一些特定的问题,例如区间求最值的问题。

对应进阶篇第 3 章。


  1. P1177 - 【模板】排序
  2. P1908 - 逆序对
  3. P1966 - [NOIP 2013 提高组] 火柴排队
  4. P1226 - 【模板】快速幂
  5. P1045 - [NOIP 2003 普及组] 麦森数
  6. P1115 - 最大子段和
  7. P2880 - [USACO07JAN] Balanced Lineup G
  8. P7167 - [eJOI 2020] Fountain (Day1)
  9. P2415 - 集合求和
  10. P1257 - 平面上的最接近点对
  11. P1228 - 地毯填补问题
  12. P2345 - [USACO04OPEN] MooFest G
  13. P3509 - [POI 2010] ZAB-Frog
  14. P3517 - [POI 2011] WYK-Plot
  15. P4155 - [SCOI2015] 国旗计划
  16. P1816 - 忠诚
  17. P6648 - [CCC 2019] Triangle: The Data Structure
  18. P7562 - [JOISC 2021] イベント巡り 2 (Event Hopping 2) (Day4)