CSP-J复赛算法指南

EasonH

2026-09-25 17:58:20

发布于：上海

15阅读

0回复

0点赞

结构体排序

一个对象有多个属性（学生：成绩，性别，身高），按照某个属性对不同对象进行排序。
通常代码：sort+cmp
例题：A30856.【结构体】【提高】final exam

#include <bits/stdc++.h>
using namespace std;
struct node{
    string name;
    int ac,time;
}s[8];
bool cmp(node x, node y){
    if(x.ac!=y.ac) return x.ac > y.ac;
    if(x.time!=y.time) return x.time < y.time;
    return x.name < y.name;
}
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= 6; i++){
        cin >> s[i].name;
        s[i].ac = 0;
        s[i].time = 0;
        for(int j = 1; j <= n; j++){
            string now;
            cin >> now;
            if(now[0]=='-'||now[0]=='0') continue;
            int num = 0, idx = 0, flag = 0;
            for(int k = 0; k < now.size(); k++){
                if(now[k]>='0'&&now[k]<='9'){
                    num = num*10+now[k]-'0';
                }
                else{
                    idx = k+1;
                    flag = 1;
                    break;
                }
            }
            s[i].ac += 1;
            s[i].time += num;
            num = 0;
            if(flag){
                for(int k = idx; k < now.size()-1; k++){
                    num = num*10+now[k]-'0';
                }
            }
            s[i].time += num*m;
        }
    }
    sort(s+1,s+7,cmp);
    for(int i = 1; i <= 6; i++){
        cout << left << setw(10) << s[i].name;
        cout << ' ';
        cout << right << setw(2) << s[i].ac;
        cout << ' ';
        cout << right << setw(4) << s[i].time;
        cout << endl;
    }
    return 0;
}

筛法（试除法优化&埃氏筛）

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

试除法优化

bool isPrime(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[1000010];//true不是质数
int primes[1000010], cnt;
void sieve(int n){//找1~n所有的质数
    notP[0] = notP[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!notP[i]){
            primes[++cnt] = i;
            for(long long j = (long long)i * i; j <= n; j += i){
            //for(int j = 2 * i; j <= n; j += i){
                notP[j] = 1;
            }
        }
    }
}

例题：
A30766.选数

#include <bits/stdc++.h>
using namespace std;
int n,k,ans;
int a[25];
bool vis[25];
bool isP(long long x){
    if(x<2) return 0;
    for(int i = 2; i * i <= x; i++){
        if(x%i==0) return 0;
    }
    return 1;
}
void dfs(int x){
    if(x==n+1){
        int num = 0;
        for(int i = 1; i <= n; i++) if(vis[i]==1) num++;
        if(num!=k) return;
        long long sum = 0;
        for(int i = 1; i <= n; i++) if(vis[i]==1) sum+=a[i];
        if(isP(sum)) ans++;
        return;
    }
    vis[x] = 1;
    dfs(x+1);
    vis[x] = 0;
    dfs(x+1);
}
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    dfs(1);
    cout << ans;
    return 0;
}

枚举

枚举三要素：
· 确定枚举对象：枚举什么？（答案？分割点？子集？）
· 确定枚举范围：循环从哪开始到哪结束
· 合法条件：满足哪些条件的枚举对象是我们需要的答案

识别信号：
· 枚举所有可能：所有方案、总共有多少个解、是否存在某种解……
· 数据范围很小（N<=100 或 N<=1000）

贪心

核心思想：每一步都做出当前的最优选择，并希望局部最优能推出全局最优。

常见的贪心思路：
· 排序后贪心
· 每次选择最大的/最小的
· 区间贪心（按开始/结束/时长排序）

识别信号：题目要求最值（最大，最小）

二分查找与二分答案

二分查找：在有序数组中查找目标值，每次比较中间元素，将搜索范围缩小一半。
二分答案：当答案具有单调性，不直接求答案，而是二分答案的范围，每次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;
}

双指针

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

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

特点：时间复杂度从O(n^2)降低到O(n)

前缀和与差分

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

识别信号：
· Q次询问区间和 -> 前缀和预处理
· Q次区间修改 -> 差分数组