低年级组集训 第一周：基础算法（二）
题单介绍
## 五、贪心
局部最优=全局最优，它并非真理，但是在很多问题上确实管用（在优化算法上，它很多时候甚至比写的不优秀的正解还要出色）。
学习链接：[OI-Wiki 贪心](https://oi-wiki.org/basic/greedy/)
题单：
* [P1223 排队接水](https://www.luogu.com.cn/problem/P1223)
* [P2240 【深基12.例1】部分背包问题](https://www.luogu.com.cn/problem/P2240)
* [P1012 [NOIP1998 提高组] 拼数](https://www.luogu.com.cn/problem/P1012)
* [P2869 [USACO07DEC]Gourmet Grazers G](https://www.luogu.com.cn/problem/P2869)
* [P1803 凌乱的yyy / 线段覆盖](https://www.luogu.com.cn/problem/P1803)
* [P1090 [NOIP2004 提高组] 合并果子](https://www.luogu.com.cn/problem/P1090)（它会需要使用一个偏高级的数据结构，当你感觉策略没有问题，但是只能拿到50分的时候就可以去题解里面学习它了）
## 六、分治
1. 将问题分成若干小的同性质子问题
2. 递归解决子问题
3. 将子问题进行合并，得到原问题的解
“分——治——合”三步走，这就是分治算法的核心逻辑。
题单：
* [P1226 【模板】快速幂||取余运算](https://www.luogu.com.cn/problem/P1226)
* [P1010 [NOIP1998 普及组] 幂次方](https://www.luogu.com.cn/problem/P1010)
* [P1908 逆序对](https://www.luogu.com.cn/problem/P1908)（即使你已经AC了它，也请重新回头思考一下它的算法流程与思想）
## 七、前缀和与差分
给定长度为 $n$ 的序列 $\{a_n\}$，要求多次查询区间 $[l,r]$ 上的元素和，你会每次都埋头算一遍吗？
利用信息的可叠加+可逆性质，我们能够应用前缀和/差分来优化程序，将区间操作转化为单点操作。
不只是序列，我们也可以在树上应用该算法。
学习链接：[OI-Wiki 前缀和 & 差分](https://oi-wiki.org/basic/prefix-sum/)
题单：
* [P8218 【深进1.例1】求区间和](https://www.luogu.com.cn/problem/P8218)
* [P2004 领地选择](https://www.luogu.com.cn/problem/P2004)
* [P3397 地毯](https://www.luogu.com.cn/problem/P3397)
* [J - Stall Reservations 专用牛棚](https://vjudge.csgrandeur.cn/problem/黑暗爆炸-1651)（本题的洛谷版本需要输出方案，而DarkBZOJ的版本只需要输出数量即可。从考察的知识点考虑，你进需要完成后者这个简单版即可）
* [P8200 [传智杯 #4 决赛] 生活在树上（easy version）](https://www.luogu.com.cn/problem/P8200)（如果你对树和图还不够了解，建议学习完毕后再来回头看本题）
## 八、二分
大家一定都玩过这样的游戏：让你猜一个1-1000以内的数，每次会告诉你大了还是小了，只要10次就可以猜到它是多少。
当问题具有明显的单调性质和简易的判定方式时，我们就可以使用二分法求得答案。
学习链接：[OI-Wiki 二分](https://oi-wiki.org/basic/binary/)
题单：
* [P2249 【深基13.例1】查找](https://www.luogu.com.cn/problem/P2249)
* [P1873 [COCI 2011/2012 #5] EKO / 砍树](https://www.luogu.com.cn/problem/P1873)
* [P1182 数列分段 Section II](https://www.luogu.com.cn/problem/P1182)
* [P2678 [NOIP2015 提高组] 跳石头](https://www.luogu.com.cn/problem/P2678)
* [P1733 猜数（IO交互版）](https://www.luogu.com.cn/problem/P1733)