复赛

小明

2026-09-26 11:45:49

发布于：上海

2阅读

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排序：多关键字排序问题。
输出排名，第k名，前m名：先排序再取数据。

筛法

概念

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

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

bool is_prime(int n){
    if(n <= 1) return false;
    for(int i = 2; i * i <= n - 1; i++){
        if(n % i == 0) return false;
    }
    return true; 
}

批量求质数(埃式筛)

bool notp[10000005];
int primes[10000005];
void sieve(int n){
    notp[0]=notp[1]=1;
    for(i=2;i<=n;i++){
        if(!notp[i]){
            prime[++cnt]=i;
            for(int j=2*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;
            //r = mid - 1;
        }else{
            r = mid - 1;
            //l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

双指针

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

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

前缀和与差分

前缀和：预先处理前缀和数组（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）。