JJJ复赛复习JJJ

AAA蓝室老师傅

2026-09-26 11:44:26

发布于：上海

3阅读

0回复

0点赞

JJJ复赛复习JJJ

结构体排序

概念

当一个对象有多个属性(学生：姓名，成绩，学号，性别) 时，我们用结构体把把他们打包在一起，排序需自定义比较规则，告诉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排序，多关键字排序问题

筛法

概念

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

判断质数（试除法，枚举`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 0;
    } 
    return 1;
}

批量求质数（埃氏筛）

bool notP[1000010]; //true不是质数
int primes[1000010], 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)i * 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;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

双指针

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

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

特点：时间复杂度从 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次区间修改 ==> 差分数组