CSP-J复习
2026-09-25 17:56:25
发布于：上海
结构体排序
A4758(奥特曼~~):
#include <bits/stdc++.h>
using namespace std;
struct atm{
string name;
int high,begin;
};
bool cmp(atm a,atm b){
if (a.high!=b.high){
return a.high>b.high;
}else{
return a.begin<b.begin;
}
}
int main(){
atm atmm[1005];
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> atmm[i].name >> atmm[i].high >> atmm[i].begin;
}
sort(atmm+1,atmm+n+1,cmp);
cout << atmm[1].name << ' ' << atmm[1].high << ' ' << atmm[1].begin;
return 0;
}
筛法（试除法优化，埃氏筛）
判断质数和批量求质数是两个完全不同的问题。
试除法优化：
bool isPrime(int n){
int (n<2){
return false;
}
for(int i=2;i*i<=n;i++){
if (n%i==0) return false;
}
}
埃氏筛（质数的倍数一定不是质数）：
bool notP[100005];
int primes[100005],cnt;
void sieve(int n){
notP[0]=notP[1]=1;
for(int i=2;i<=n;i++){
if (!notP[i]){
primes[++cnt]=i;
for(int j=2*i;j<=n;j+=i){
notP[j]=1;
}
}
}
}
例题：A30766.选数
枚举
枚举三要素：
·确定枚举对象
·确定枚举范围：循环从哪里开始都哪里结束
·合法条件：满足哪些条件的枚举对象是我们需要的答案
识别信号：
· 列举所有可能:所有方案，总共有多少解
· 数据范围很小（n<=100或n<=1000）
贪心
核心思想：每一步都做出当前的最优选择，并希望局部最优推出全局最优。
常见的贪心策略：
· 排序后贪心
· 每次选择最大的/最小的
· 区间贪心
识别信号：题目要求最值(最大/最小)
二分查找与二分答案
二分查找：在有序的数组中查找目标值，每次比较中间的元素，将搜索范围缩小一半。
二分答案：当答案具有单调性，不直接求答案，而是二分答案的范围，每次check当前猜想是否可行。
int main(){
......
int l=下界,r=上界,ans=-1;
while(l<=r){
int mid=(l+r)/2;
if (check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
}
双指针
双指针是一种用两个变量代替指针在数组上同时移动来解决问题的技巧，核心是避免不必要的重复计算。
常见类型：
· 同向双指针（滑动窗口）：两个指针同时移动，维护一个窗口。用于“最长/最短连续子序列”问题。
· 相向双指针（碰撞双指针）：一个从头，一个从尾向中间靠拢。用于有序的数组。
特点：时间复杂度从O（n^2）降到O（n）
前缀和与差分
前缀和：预先处理前缀和数组（s[i]=s[i-1]+a[i]）,之后任意区间[l,r]的查询可以在O（1）的时间计算出：s[r]-s[i-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的点。
核心特性：BFS在无权图上找到的最短路径
递推与动态规划
递推：通过已知的数学公式，规律，计算出每一项的值。
动态规划：用状态数组描述子问题，通过状态转移方程计算不同状态的值。
这里空空如也
有帮助，赞一个