CSP考前复习

呆

2026-09-26 11:48:19

发布于：上海

3阅读

0回复

0点赞

CSP-J算法：

结构体排序：

概念

当一个对象有多个属性（如学生：姓名，成绩，学号，性别）时，我们用结构体把他们打包在一起。排序的时候需要自定义比较规则，告诉sort函数“谁排前面”。

核心要点

用struct定义结构体，把相关数组组织在一起。
在写比较函数cmp时，返回true时表示第一个参数在前面。

struct stu{
    int id;//学号
    int score;//成绩
}
//先按成绩降序排序，再按学号升序排序
bool cmp(stu a, stu b){
    if(a.score | b.score) return a.score > b.score;
    else return a.id < b.id;
}

多关键字排序：先比较主关键字，主关键字相同时，比较次关键字

识别信号

“按X排序，若相同则按Y排序”：多关键字排序问题。
“输出排名”，“第k名”，“前m名"：先排序再取数据。

筛法：

概念

判断质数和批量求质数是两个完全不同的两个问题。

判断指数（试除法：枚举 2~n-1 ，看看是否有 n 的因子）

bool is_Prime(int n){
    if(n < 2) return 0;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

批量求质数（埃氏筛）（选修）

bool notP[100005];//notP 为true时，表示不是质数
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 = 2 * i; j <= n; j += i){
                   notP[j] = 1;
            }
        }
    }
}

枚举：

枚举三要素

确定枚举对象：枚举什么？（枚举答案，枚举分割点，枚举子集）。
确定枚举范围：循环从哪开始到哪结束。
合法条件：满足哪些条件的枚举对象是我需要的。

贪心：

贪心算法的核心思想是每一步做出当前最优的选择，希望局部最优能推导出全局最优。

常见贪心策略：

排序后贪心（按照某种规则排序后顺序处理）
选择当前可选中最大/最小的
区间贪心（按照开始/结束/时长排序）

二分查找与二分答案：

二分查找：在有序数组中查找目标值，每次比较中间元素将搜索范围缩小一半。
二分答案：当答案具有单调性时（即答案>=x可行，但<x不可行），不直接求答案，而是二分猜答案，每次check答案是否可行。

双指针：

双指针是一种用两个变量（代替指针）在数组上同时移动来解决问题的技巧，核心是避免不必要的重复计算

常见类型：

同向双指针（滑动窗口）：两个指针同向移动，维护一个窗口。用户最长/最短连续子序列问题。
粗向双指针（碰撞双指针）：一个从头，一个从尾向中间靠拢。用于有序数组上的查找。

前缀和与差分：

前缀和:预处理数组的前缀和 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] 在 ** $O(1)$ **进行修改，只需要修改两个端点： d[l] += v, d[r + 1] -= v。最后差分数组求前缀和还原。

STL数据结构：

容器	特点	用途
stack	后进先出	括号匹配，表达式求值
queue	先进先出	BFS
map	键值对，按键有序	计数，离散化
set	有序不重复集合	去重，查找