Day 1 上午 —— 基础算法
模拟 + 枚举
小前言
碰到题目不会做 -> 先写个模拟压压惊（）
枚举法
枚举的思想是不断地猜测，从所有可能的集合中一一尝试，然后再判断是否符合题目的条件。
单独提到枚举时我们往往认为这是一个暴力做法，但事实上并非如此，恰当的枚举往往会是解题的关键步骤。
例题 1 ： 枚举优化 —— 质数判断
-
简要题面
给定一个数 \(x\)，判断 \(x\) 是不是质数。
-
朴素枚举算法
-
优化
-
其余优化
P1149 [NOIP2008 提高组] 火柴棒等式
-
题目链接
-
简要思路
for循环 +check判断。首先枚举计算所有的数所需要的火柴数量（设立数组 \(g\)，\(g_i\) 代表 \(i\) 这个数所需要的火柴数）。
注意到火柴数最多为 \(24\) 根，去掉加号和等号的 \(4\) 根火柴，所以我们最大的等式就是 \(1111 + 1111 = 2222\)，所以只需要枚举每个答案，然后验证答案即可。
-
完整代码
P1115 最大子段和
P1638 逛画展
-
方法
区间伸缩/尺取法
桶。
作业题 1：P3143 [USACO16OPEN] Diamond Collector S
模拟法
模拟就是用计算机来模拟题目中要求的操作。
模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。
P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
P1563 [NOIP2016 提高组] 玩具谜题
模拟题小技巧
做模拟题的步骤：
-
先看懂题意，过一下样例；
-
在动手写代码之前，在草纸上尽可能地写好要实现的流程；
-
在代码中，尽量把每个部分模块化，写成函数等；
-
对于一些可能重复用到的概念，可以统一转化，方便处理；
-
调试时分块调试。模块化的好处就是可以方便的单独调某一部分；
-
写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写。
作业题 2：P1042 [NOIP2003 普及组] 乒乓球
作业题 3：P2670 [NOIP2015 普及组] 扫雷游戏
作业题 4：P3952 [NOIP2017 提高组] 时间复杂度
二分
定义
在一个单调的有限数列上快速查找某一特定值的方法。
例题 2：二分基础题（1）
-
简要题面
给你一个单调递增的数组，给你一个数 \(x\)，问第一个 \(>x\) 和第一个 \(\geq x\) 的数分别是多少。
-
代码找茬
-
保守写法
例题 3：二分基础题（2）
-
简要题面
求一个正整数 \(X\) 开三次根后的结果，保留六位小数。
假设大家不知道
pow，只知道sqrt（）。 -
简要思路
二分答案（二分答案限制：假设一个数 \(x\) 满足性质，那么所有 \(\geq x\)/\(\leq x\) 的数都满足条件）。
左边界 \(l=0\)，右边界 \(r=x+1\)。
例题 4：二分基础题（3）
-
简要题面
有两个长度为 \(n\) 的数组 \(a\) 和 \(b\)，生成一个 \(n \times n\) 的数值表，表中第 \(i\) 行第 \(j\) 列的数为 \(a_i \times b_j\)，求表中第 \(k\) 小的数值是多少？