Day1（基础算法）
讲师：余快
枚举法
例题1
给定一个数 \(x\)，判断 \(x\) 是不是质数。
朴素算法：枚举 \([2,x−1]\) 之间所有的整数 \(i\)，逐个判断 \(x\) 是否被 \(i\) 整除，若都不能整除则 \(x\) 是质数，时间复杂度 \(O(x)\)，搞个 \(10^9\) 直接卡过。该怎么优化呢？
优化枚举范围：只需枚举到 \(\sqrt{x}\) 即可
例题2
简要思路
for 循环 + check 判断。
首先枚举计算所有的数所需要的火柴数量（设立数组 \(g\)，\(g_i\) 代表 i 这个数所需要的火柴数）。
例题3
暴力枚举（\(0\text {pts}\)）：
枚举区间的左端点，右端点，然后从左端点开始到右端点逐个加起来。
时间复杂度 \(O(n^3)\)
前缀和优化的朴素算法（\(40\text {pts}\)）：
先处理 \(s_i=a_1+a_2+ \dots +a_i\)
枚举区间的左端点 \(i\)，右端点 \(j\)，这段区间的和就是\(s_j − s_{i−1}\)
时间复杂度 \(O(n^2)\)
优化枚举范围（\(100\text {pts}\)）：
如果我们固定右端点 \(i\) ，那么我们选择的左端点 \(j\) 一定满足 \(s_{j −1}\) 最小，这样的 \(s_i−s_{j−1}\) 是最大的。
于是我们从左到右枚举右端点 \(i\)，维护 \([1,i]\) 里满足 \(s_{j−1}\) 最小的 \(j\)，然后直接选择 \(j\) 作为左端点。
时间复杂度 \(O(n)\) 。
悄悄说一下，其实这道题正解是 dp。
例题4
模拟算法
模拟就是用计算机来模拟题目中要求的操作。
模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。
例题1
洛谷 P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
例题2
技巧
写模拟题时，遵循以下的建议有可能会提升做题速度：
在动手写代码之前，在草纸上尽可能地写好要实现的流程。
在代码中，尽量把每个部分模块化，写成函数、结构体或类。
对于一些可能重复用到的概念，可以统一转化，方便处理。
调试时分块调试。模块化的好处就是可以方便的单独调某一部分。
写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写。
实际上，上述步骤在解决其它类型的题目时也是很有帮助的。
习题
P1042 [NOIP2003 普及组] 乒乓球
P2670 [NOIP2015 普及组] 扫雷游戏
P3952 [NOIP2017 提高组] 时间复杂度
二分法
定义
二分的定义：在一个单调的有限数列上快速查找某一特定值的方法。
例题1
给你一个单调递增的数组，给你一个数x，问 $ > x, \ge x$的第一个数分别是什么？
可以用 STL 中的 lower_bound 和 upper_bound 轻松解决，不过在这里不讲。
事实上有不同二分的实现方法，刚刚接触二分的OIer经常在这个地方写错，进入死循环
//找第一个>q
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if (a[mid]<=q)l=mid+1;
else r=mid;
}
std::cout<<r;
//找第一个>=q
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if (a[mid]>=q)r=mid;
else l=mid+1;
}
std::cout<<r;
其实我们有最保守的写法
就是l=mid+1;r=mid-1
而答案直接考虑mid
例题2
求一个正整数X开三次根后的结果，保留六位小数。
因为我们这里要二分实数，所以
解法1：
直接输出 pow(x,1/3)
假设我们不知道 pow 函数，只知道二分和 sqrt 函数
01分数规划
分治
快速幂
CSP-S2023第一轮 著名题目：
现在用如下程序来计算x^n，其时间复杂度为（ ）。
Quick_power(x,k):
if k==1 return x;
else return Quick_power(x,k/2)*Quick_power(x,k/2)*(k&1)?x:1;
A.O(n)
B.O(1)
C.O(log n)
D.O(n log n)
答案选A
我们在六年级的时候学过同底数幂的乘法法则，得知 \(x^a \times x^b = x^{a + b}\)，因此 \(x^{\frac{y}{2}} \times x^{\frac{y}{2}} = x ^ y\)，所以我们可以分治，直到指数为 \(0\)。记当前的结果为 \(z\)，底数为 \(x\)，指数为 \(y\)，按照 \(z^y = z^{\frac{y}{2}} \times z^{\frac{y}{2}}\) 来计算。如果当前递归到的 \(y\) 为偶数，直接返回计算的结果；如果 \(y\) 为奇数，就要把刚才得到的结果再乘上一个 \(x\)，再返回。