CSP-J考前复习((GAY))米缸

编程_Hyfield_Dusk‌

2026-09-26 11:45:55

发布于：上海

0阅读

0回复

0点赞

CSP-J考前复习：

结构体排序：
当一个对象有多个属性(学生，成绩，性别，学号)，我们用结构体排序把它们打包在一起。排序的时候要自定义比较规律，告诉sort函数"谁排前面"。

struct node{
      int a;
      int b;
}
bool cmp(node x , node y){
        if(x.b != y.b) rerturn x.b > y.b;
        else return x.a < y.a;
}

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

判断质数(试除法：枚举2到n-1,看看是否有n的因子)

bool isPrime(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[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;
        }
    }
}

双指针：

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

常见类型：

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

特点

时间复杂度从O(n^2 )降低到O(n)

前缀和与差分：

前缀和：预先处理前缀和数组

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(集合)	有序不重复集合	去重、排序、查找