CSP - J组复赛算法
2026-09-27 17:47:22
发布于:上海
结构体排序
一个对象有多个属性(学生:成绩,性别,身高),按照某个属性对不同对象进行排序
通常代码
sort(a + 1, a + n + 1, cmp);//cmp为比较函数
历年考试概率:★
A4758.奥特曼身高问题
筛法(试除法优化,埃氏筛)
判断质数和批量求质数是两个完全不同的问题
试除法优化
bool isPrime(int n){
if(n < 2) return false;
for(int i = 2 ; i*i <= n; i++){
if(n % i==0) return false;
}
return true;
}
埃氏筛
bool notP[10000005];//ture表示不是质数
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(long long j = (long long) 2 * i; j<=n; j+=i){
notP[j] = 1;
}
}
}
}
历年考试概率:★
枚举
枚举三要素:
- 确定枚举对象:枚举什么?(枚举答案?枚举分割点?枚举子集?)
- 确定枚举范围:循环从哪开始到哪结束
- 合法条件:满足哪些条件的枚举对象是我们需要的答案
识别信号
- 列举所有可能:所有方案、总共有多少个解、是否存在某种解...
- 数据范围很小
历年考试概率:★★★
贪心
核心思想:每一步都做出当前的最优选择,并希望局部最优能推出全局最优
常见的贪心策略:
- 排序后贪心
- 每次选择最大的/最小的
- 区间贪心(按开始/结束/时长排序)
识别信号
题目要求最值(最大,最小)
历年考试概率:★★
二分查找与二分答案
二分查找
在有序数组中查找目标值,每次比较中间元素,将搜索范围缩小一半
二分答案
当答案具有单调性,不直接求答案,而是二分答案的范围,每次check当前猜测是否可行
int main(){
......
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;
}
}
}
历年考试概率:★
双指针
双指针是一种用两个变量代替指针在数组上同时移动来解决问题的技巧,核心是避免不必要的重复计算
常见类型:
- 同向双指针(滑动窗口):两个指针同向移动,维护一个窗口。用于"最长/最短连续子序列”问题
- 相向双指针(碰撞双指针):一个从头、一个从尾向中间靠拢。用于有序数组上的查找
特点
历年考试概率:★
前缀和与差分
前缀和
预先处理前缀和数组
s[i] = s[i - 1] + a[i]
......
//之后任意区间[l,r]的查询可在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
是递归最重要的应用之一,从一个状态出发,沿着一条路径走到底,走不动了就回溯到上一个状态,尝试其他路径
识别信号
- 所有排列、所有组合、所有方案
- 连通块
- 数据范围很小
历年考试概率:★★
广搜
一种逐层展开的搜索方式,先访问距离起点为1的所有状态,再访问距离为2的,以此类推
核心特性
BFS在无权图上能找到最短路径
历年考试概率:★★★
递推与动态规划
递推
通过已知的数学公式、规律,由小到大,计算出每一项的值
动态规划
划分不同的子问题,用状态数组描述子问题,通过状态转移方程计算不同状态的值,从而得出答案
历年考试概率:★★★★
如有疏漏,欢迎补充
全部评论 6
D
1周前 来自 江苏
0新增了算法历年的概率,供大家优先复习
1周前 来自 上海
0嗯,对我很有帮助
1周前 来自 新疆
0祝你看了我的文章J1好吧
1周前 来自 上海
0感谢,互关呗
1周前 来自 新疆
0
建议补充各类图论算法
1周前 来自 浙江
0oooooooooooooook
1周前 来自 上海
0
全体目光向我看齐
1周前 来自 上海
0顶
1周前 来自 上海
0































有帮助,赞一个