低年级组集训 第一周：基础算法（一）

## 一、模拟 模拟，顾名思义，你只需要用代码来“模拟”出题目希望你所完成的行为即可。 模拟题一般不依赖算法来实现，但它依旧是所有算法竞赛选手的基本功：再天马行空的算法，也要落实到代码上才有意义。 题单： * [P1563 【NOIP2016 提高组】 玩具谜题](https://www.luogu.com.cn/problem/P1563) * [P1328 【NOIP2014 提高组】 生活大爆炸版石头剪刀布](https://www.luogu.com.cn/problem/P1328) * [P3952 【NOIP2017 提高组】 时间复杂度](https://www.luogu.com.cn/problem/P3952) * [P2615 【NOIP2015 提高组】 神奇的幻方](https://www.luogu.com.cn/problem/P2615) ## 二、排序与离散化 为了将无序的数据转变为有序，无数层出不穷的排序算法应运而生。当你在懒懒的调用一行 `sort(a+1,a+n+1)` 前，不妨想一想它背后的秘密。 排序算法在算法竞赛中一般不单独考察（除非思维题），而是与其他算法相混合，其中比较出名的莫过于离散化。如果你发现最终答案只取决于元素之间的大小关系而非具体的值（而且值大到了难以正常处理的程度），那就是离散化大显身手的时候了。 推荐学习链接：[OI-Wiki 排序](https://oi-wiki.org/basic/sort-intro/)，[OI-Wiki 离散化](https://oi-wiki.org/misc/discrete/) 题单： * [P1059【NOIP2006 普及组】 明明的随机数](https://www.luogu.com.cn/problem/P1059) * [P1051【NOIP2005 提高组】 谁拿了最多奖学金](https://www.luogu.com.cn/problem/P1051) * [P1908 逆序对](https://www.luogu.com.cn/problem/P1908) * [CF670C Cinema](http://codeforces.com/problemset/problem/670/C) ## 三、枚举 计算机的运算速度百万倍于人脑，因此在面对一些棘手的问题时，我们可以让电脑尝试穷举出所有的答案（打个比方，电脑可以在1s内枚举出所有的八位纯数字密码）。 不过，电脑的速度再快，往往也无法超过问题增长的速度，因此我们需要针对问题进行时空复杂度分析，来判断何时进行枚举，哪里需要优化。 枚举方式各种各样，除了最朴素的循环枚举，我们也常常见到子集枚举和排列枚举。 学习链接：[OI-Wiki 枚举](https://oi-wiki.org/basic/enumerate/) 题单： * [P3392 涂国旗](https://www.luogu.com.cn/problem/P3392) * [P1217 [USACO1.5]回文质数 Prime Palindromes](https://www.luogu.com.cn/problem/P1217) * [P1706 全排列问题](https://www.luogu.com.cn/problem/P1706) * [P1157 组合的输出](https://www.luogu.com.cn/problem/P1157) * [P1036 [NOIP2002 普及组] 选数](https://www.luogu.com.cn/problem/P1036) * [P1311 [NOIP2011 提高组] 选择客栈](https://www.luogu.com.cn/problem/P1311) ## 四、搜索 从本质上讲，搜索就是另一种形式的枚举：他们都在限定的解空间内寻求答案，并验证是否优秀。（如果愿意，上面的一些题目是可以使用搜索来解决的）尽管其时间复杂度巨大无比，但是他依旧是很多问题的唯一解法。 搜索一般分为深度优先搜索（DFS）和广度优先搜索（BFS），它们各自还有各式各样的变形，但我们现在只要能够掌握朴素的搜索及其基础优化即可。 学习链接：[OI-Wiki 搜索](https://oi-wiki.org/search/) 题单： * [P1219 [USACO1.5]八皇后 Checker Challenge](https://www.luogu.com.cn/problem/P1219) (本题n=13的点比较卡常数，大家可以本机计算出结果后直接打表) * [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) * [P1141 01迷宫](https://www.luogu.com.cn/problem/P1141) * [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443) * [P1025 [NOIP2001 提高组] 数的划分](https://www.luogu.com.cn/problem/P1025)