算法复习
2026-10-05 22:42:33
发布于:上海
结构体排序
一个对象有多个属性,按照某个属性对不同对象进行排序
通常代码:sort+cmp
a4758.奥特曼身高问题
a30856.【结构体】【提高】final exam
筛法(试除法优化,埃氏筛)
判断质数和批量求质数完全不同
试除法优化
bool isPrime(int n){
if(n<=1) return false;
for(int i = 2;i*i<=n;i++){ // i<=sqrt(n)
if(n%i==0) return 0;
}
return 1;
}
埃氏筛(质数非自己的倍数一定不是质数)
bool notP[100005];
int primes[100005],cnt;
void sieve(int n){ // 找1-n所有的质数
notP[0] = notP[1] = 1;
for(int i = 2;i<=n;i++){
if(!notP[i]){
primes[++cnt] = i;
for(int j = i*2; j<=n; j+=i){
notP[j] = 1;
}
}
}
}
a30766.选数
枚举
枚举三要素
· 确定枚举对象:枚举什么?(答案,分割点,子集......)
· 确定枚举范围:循环从哪开始,到哪结束
· 合法条件:满足哪些条件的枚举对象时我们需要的答案
识别信号
· 列举所有可能:所有方案,总共有多少个解,是否存在某种解......
· 数据范围很小(n<=100 or n<=1000)
贪心
核心思想:每一步都做出当前的最优选择,并希望局部最优能推出全局最优
常见的贪心策略
· 排序后贪心
· 每次选择最大/小的
· 区间贪心(按开始/结束/时长 排序)
识别信号:题目求最值(最大、最小)
二分查找 & 二分答案
二分查找:在有序数组中查找目标值,每次比较中间元素,将搜索范围缩小一半
二分答案:当答案具有单调性时,不直接求答案,而是二分答案的范围,每次check当前猜测是否可行
二分答案
int l = (下界),r = (上界),ans = -1;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
ans = mid;
r = mid-1; // l = mid+1;
}
else{
l = mid+1; // r = mid-1;
}
}
双指针
双指针是一种由两个变量代替指针在数组同时移动来解决问题的技巧,核心是避免不必要的重复计算
常见类型
· 同向双指针(滑动窗口):两个指针同向移动,维护一个窗口。用于“最长/最短连续子序列”问题
· 相向双指针(碰撞双指针):一个从头,一个从尾,向中间靠拢。用于有序数组上的查找
特点:时间复杂度从O(n^2)降低到O(n)
前缀和 & 差分
前缀和:预先处理前缀和(s[ i ] = s[ i - 1] + a[ i ])
以在O(1)的时间计算出区间和:s[ r ] - s[ l -1 ]
差分:前缀和的逆运算
构造差分数组 d[ i ] = a[ i ] - a[ i-1 ]
对区间[ l , r ]整体加减一个值,只需修改两个端点:d[ l ]+=v,d[ r+1 ]-=v
识别信号
· q次询问区间和->前缀和预处理
· q次区间修改->差分数组
STL(数据结构)
| 容器 | 特点 | 用途 |
|---|---|---|
| stack 栈 | 后进先出 | 括号匹配,表达式求值 |
| queue 队列 | 先进先出 | bfs |
| map | 键值对 | 计数,离散化 |
| set | 有序不重复集合 | 去重,排序,查找 |
递归 & 深搜
递归:函数自己调用自己的编程技巧,本质是把大问题分解为相同的子问题
dfs:是递归最重要的应用之一,从一个状态出发,沿着一条路径走到底,走不动了就回溯到上一个状态,尝试其他路径
识别信号
· 所有排列,所有组合,所有方案
· 连通块
· 数据范围很小(n<=20)
广搜
广搜:一种逐层展开的搜索方式,先访问距离起点为1的所有状态,在访问距离为2的,以此类推
核心特性:bfs在无权图上能找到最短路径
递推 & 动态规划
递推:通过已知的数学公式,规律,由小到大,计算出每一项的值
动态规划:划分不同的子问题,用状态数组描述子问题,通过状态转移方程计算不同状态的值,从而得出答案
2026.9.25
全部评论 1
6
1周前 来自 广东
0
























有帮助,赞一个