一颗任性的宇宙星星

2026-09-26 11:59:21

发布于：上海

7阅读

0回复

0点赞

总复习

结构体排序

当一个对象有多个属性（如：名字、成绩、学号、性别等）时，我们用结构体把他们排在一起

排序的时候需要自定义比较规则，告诉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 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]; // notPei为true时，表示不是质数
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 i = 2*i ; j <= n ; j += i){
        notP[j] = 1;
      }
    }
  }
}

枚举

枚举三要素：确定枚举对象：枚举什么？（枚举答案、枚举分割点、枚举子集）
........................确定枚举范围：循环的范围是从哪里来的、到哪里
........................枚举条件：什么样的枚举对象是我需要的

贪心

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

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

二分查找 & 二分法案

二分查找：当有序数组中查找目标值，每次比较中间元素，将范围缩小至一半

二分答案：当答案具有单调性时（即答案>=x可行，但<x不可行），不直接求答案，而是二分猜答案，每次check答案是否可行

双指针

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

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

前缀和 & 差分

前缀和：预处理数组的前缀和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`	有序不重复集合	去重、查找