CSP 算法

刘思博

2026-09-25 18:01:29

发布于：上海

5阅读

0回复

0点赞

结构体排序
一个对象有多个属性（学生：成绩，身高. . .）按照莫格属性对不同对象进行排
通常代码：sort+cmp
例如：
A4758.奥特曼身高问题

    using namespace std;
    int n,Max=-100000;
    struct stu{
        string name;
        int x,h;
    }node[10000];
    bool cmp(stu a,stu b){
        return a.h<b.h;
    }
    int main(){
        cin>>n;
        for( int i=1; i<=n; i++ ) cin>>node[i].name>>node[i].x>>node[i].h;
        sort(node+1,node+n+1,cmp);
        for( int i=1; i<=n; i++ ) Max=max(Max,node[i].x);
        for( int i=1; i<=n; i++ ){
            if(node[i].x==Max){
                cout<<node[i].name<<" "<<node[i].x<<" "<<node[i].h;
            }
        }
    }

筛法（试除法优化，埃氏筛）
判断质数和批量求质数是两个完全不同的问题。
试除法优化:

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

    埃氏筛 (质数的倍数一定不是质数)：

bool notP[100005];
        int p[100005],cnt;
        void sieve(int n){
            notP[0]=notP[1]=1;
            for( int i=2; i<=n; i++ ){
                if(!notP[i]){
                    p[++cnt]=i;
                    for( int j=2*i; j<=n; j+=i ){
                        notP[j]=1;
                    }
                }
            }
        }

枚举
枚举三要素：
- 确定枚举对象：枚举什么？
- 确定枚举范围：循环从哪开始从哪结束
- 合法条件：满足那些条件的枚举对象是我们需要的答案
识别信号
- 列举所有可能：所有方案，总共多少个姐，是否存在魔种姐. . .
- 数据范围很小(N<=100 || N<=1000)

贪心
核心思想：每一步都做出当前的最优选择，并希望局部最优能推出全局最优。
常见的贪心策略：
- 排序后贪心
- 每次选择最大的/最小的
- 区间贪心（按开始/结束/时长排序）
识别信号：题目要求最值（大，小）
2分查找与2分答案
2分查找：在有序数组中查找目标值，每一次比较中间元素，将搜索范围缩小一半。
2分答案：当答案具有单调性，不直接求答案，然是2分的范围，每次check当前猜测是否可信。

int main(){
    . . .
    int l= . ,r= . ;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
            //l=mid+1;
        }else{
            //r=mid-1;
            l=mid+1;
        }
    }
    return 0;
}

双指针
双指针是一种用两个变量代替指针在数组上同时移动来解决问题的技巧，核心是避免不必要的重复计算。
常见类型：
-同向双指针（滑动窗口）：两个指针通向移动，维护一个窗口。用于“最长/最短连续子序列”问题。
-相向双指针（碰撞双指针）：一个从头，一个从未向中间靠拢。用于有序数组上的查找。
特点：时间复杂度从O(n^2)降到O(n)

前缀和
前缀和：预先处理前缀和数组（s[i]=s[i-1]+a[i]),之后任意区间[l,r]的查询可以在0（1）的时间复杂度算出。

STL(数据结构）