j组算法

黄

2026-09-26 20:31:39

发布于：上海

11阅读

0回复

0点赞

目录
1.排序（结构体）
2.筛法
3.枚举
4.贪心
5.二分
6.双指针
7.前缀和差分
8.stl容器
9.递归dfs
10.bfs
11.递推dp
12.文件输入输出

结构体排序

当一个对象有多个属性（name,id,score）,我们用结构体把它们打包在一起。排序时要自定义比较规则；告诉sort函数谁在前面

struct stu{
    string name;
    int score;
    int id;
};
bool cmp(stu x,stu y){
    return x.score>y.score;
}

核心：

比较函数中，返回ture表示第1个参数排在前面
多关键字：当第1关键字不等时比较第2关键字，以此类推
用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];
            //标记质数的倍数
            for(int j=2*i;j<=n;j+=i){
                notp[j]=1;
            }
        }
    }
}

枚举

枚举三要素：
确定枚举对象：要枚举社么？（枚举答案，枚举分割点，枚举子集）
确定枚举范围：循环从哪里开始到哪结束？
合法条件：社么样的枚举对象是题目要求的答案？
识别信号
枚举的数据范围通常不大（n>=1000)
所有方案,有多少种可能,恰好满足

贪心

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

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

二分查找与二分答案

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


//第1个大于等于的位置
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;
    }
}

双指针

概念：双指针是一种用两个指针（变量）在数组或序列上同时移动来解决问题的技巧，核心思想是避免不必要的重复计算。
常见类型：

同向双指针（滑动窗口）：两个指针同向移动，维护一个窗口。用于“最长/最短连续子序列”问题。
相向双指针：一个从头、一个从尾向中间靠拢。用于有序数组上的查找。
识别信号：
暴力要o(n2)的双重循环，且内层循环的起点随外侧单调移动。

前缀和差分

前缀和：预处理前缀和数组是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
识别信号：