J组算法总复习（all）

写注释写思路九字真言马马辰

2026-09-26 20:29:12

发布于：上海

5阅读

0回复

0点赞

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

结构体排序

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

struct stu{
    string name;
    int score;
    int id;
};
bool cmp(stu a,stu b){
    if(a.score != b.score) return a.score > b.score;
}

核心要点：

比较函数中，返回true表示第一个参数排在前面。
多关键字排序：当第一关键字不等时，再比较第二关键字，以此类推。
用struct定义结构体，把相关数据组织在一起。
识别信号：
“按X排序，若相同则按照Y排序”
“输出所有人的排名”，“第K名”，“前M名”
稳定排序需要用stable_sort

筛法

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

判断质数（试除法）：判断单个数n是否是质数，只需要从2到√n遍历查看是否有n的因子即可。
批量求质数（埃氏筛）：批量求1-n内所有质数，从2开始，每找到一个质数就把它的所有倍数标记为和数，时间复杂度是O(n log log n)。

埃氏筛代码：

bool notP[100005];//notP[i] = 1 表示不是质数
int primes[100005], cnt;
//把1~n的质数都存下来
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;
            }
        }
    }
}

枚举

枚举三要素：

确定枚举对象：要枚举什么？(枚举答案、枚举分割点、枚举子集)
确定枚举范围：循环从哪开始到哪结束？
合法条件：什么样的枚举对象是题目要求的答案？

识别信号：

枚举算法的数据范围通常都不大 (N $\le$ 1000)。
"所有方案"，"有多少种可能"，"恰好满足"

贪心

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

使用条件：

排序后才能选择
区间贪心（按开始时间/结束时间/时长排序）

二分查找与二分答案

二分查找：在有序数组中查找目标值，每次比较中间元素，将搜索范围缩小一半。时间复杂度： O(logn)。
二分答案：要求解最大值最小或最小值最大时，不直接求答案，而是二分猜答案，每次check当前猜测是否可行。

//找第一个大于等于 X 的位置
int l = 1, r = n, ans = n + 1;
while(l <= r){
    int mid = (l + r) / 2;
    if(a[mid] >= x){
        ans = mid;
        r = mid - 1;
    }
    else{
        l = mid + 1;
    }
}