45.考前复习

Otori emu

2026-09-26 11:46:07

发布于：上海

0阅读

0回复

0点赞

结构体排序
筛法
枚举
贪心
二分查找与二分答案
双指针
前缀和与差分
STL数据结构
递归与深搜
广搜
递推与动态规划

结构体排序

概念：

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

核心要点

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

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

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

识别信号：

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

筛法

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

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

void 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[10005]//为ture时表示不是质数
int primes[100005],cnt;//存储质数
void sieve(int n){
    notP[0]=note[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]的和可以0（1）算出：s[r]-s[l-1]
差分：前缀和的逆运算。构造差分数组d[i]=a[i]-a[i-1]，对区间[l,r]在0(1)进行修改，只需要修改两个端点：d[l]+=v,d[r+1]-=v.最后对差分数组求前缀和还原

STL数据结构

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