信息学奥赛C++核心算法课堂笔记

一、基础工具函数

1.1 回文字符串判断函数

【功能】判断字符串是否为回文（正读与反读完全一致） 【核心原理】双指针首尾向中间逼近，逐位对比字符 【模板代码+逐行注释】

#include<bits/stdc++.h>
using namespace std;

// 功能：判断字符串s是否为回文，是返回true，否返回false
bool isPalindrome(string s){
    int l = 0, r = s.size() - 1; // 左指针指向开头，右指针指向结尾
    while (l < r){ // 两指针未相遇时循环
        if (s[l] != s[r]) return false; // 字符不匹配，直接判定非回文
        l++, r--; // 匹配成功，指针向中间移动
    }
    return true; // 全部匹配完成，判定为回文
}

int main(){
    string s;
    cin >> s;
    if(isPalindrome(s)) cout << "是回文字符串" << endl;
    else cout << "不是回文字符串" << endl;
    return 0;
}

【适用场景】回文子串判定、回文数校验、回文构造题 【易错提醒】字符串下标从0开始，右指针初始值必须为s.size()-1，避免数组越界

---

1.2 质因数计数模板

【功能】统计一个整数中，指定质因子出现的次数（示例为统计因子2的个数） 【核心原理】循环对数值做除法，每整除一次计数+1，直到无法整除为止 【模板代码+逐行注释】

#include<bits/stdc++.h>
using namespace std;

int main(){
    int x, cnt = 0;
    cin >> x;
    // 统计x中质因子2的出现次数
    while (x % 2 == 0){
        cnt++; // 能整除，计数+1
        x /= 2; // 除去一个因子2
    }
    cout << "因子2的个数：" << cnt << endl;

    // 通用模板：统计任意质因子p的个数
    // int p, cnt = 0;
    // cin >> x >> p;
    // while(x % p == 0){
    //     cnt++;
    //     x /= p;
    // }
    return 0;
}

【适用场景】阶乘质因数分解、倍数统计、数论构造题 【易错提醒】必须先判断整除再做除法，避免数值变为0后出现死循环

---

二、离散化算法

2.1 算法核心概述

【定义】在不改变数据相对大小关系的前提下，将大范围、稀疏的数值映射到小范围、连续的数值区间，解决数组下标越界、空间浪费的问题 【核心思想】保序映射：原数值的大小关系映射后完全不变；原数值相同，映射后数值也相同 【适用场景】

1. 数值范围极大（如1e9），但数据总量很小（如1e5），无法直接用数组下标计数
2. 只关注数据相对大小，不关注绝对数值的场景（排名、种类统计）
3. 常与尺取法、线段树、树状数组等算法结合使用

2.2 标准实现步骤

1. 把所有待离散化的数值存入辅助数组
2. 对辅助数组进行排序
3. （可选优化）对排序后的数组去重，避免重复数值占用多个下标
4. 用二分查找，将原数值映射为其在排序后数组中的下标（离散化完成）

2.3 完整模板代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10; // 数据最大规模

int n;
int b[MAXN]; // 统计离散化后每个数值的出现次数
int c[MAXN]; // 离散化辅助数组
struct Node {
    int val, id; // val:业务数值，id:待离散化的原编号
}s[MAXN];

// 排序规则：按业务数值从小到大排序
bool cmp(Node s1, Node s2){
    return s1.val < s2.val;
}

// 手动实现二分查找：找到c数组中第一个大于等于x的元素下标
// 功能：完成原数值到离散化下标的映射
int getDiscreteId(int x){
    int l = 1, r = n, ans = n;
    while (l <= r){
        int mid = (l + r) / 2;
        if(c[mid] >= x) {
            ans = mid;
            r = mid - 1; // 找第一个符合条件的位置，向左收缩
        }
        else l = mid + 1; // 数值过小，向右查找
    }
    return ans;
}

int main(){
    // 1. 输入数据
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s[i].val >> s[i].id;
        c[i] = s[i].id; // 待离散化数值存入辅助数组
    } 

    // 2. 辅助数组排序，为二分映射做准备
    sort(c + 1, c + 1 + n);
    // 可选优化：去重，去重后二分右边界改为去重后的长度
    // int len = unique(c + 1, c + 1 + n) - (c + 1);

    // 3. 完成离散化映射，统计数值种类
    int typeCnt = 0; // 不同数值的总种类数
    for (int i = 1; i <= n; i++){
        s[i].id = getDiscreteId(s[i].id); // 离散化核心映射
        // STL快捷写法：s[i].id = lower_bound(c+1,c+1+n,s[i].id) - c;
        b[s[i].id]++;
        if(b[s[i].id] == 1) typeCnt++; // 首次出现，种类数+1
    } 

    // 后续业务逻辑（示例：排序后配合尺取法使用）
    sort(s + 1, s + 1 + n, cmp);

    return 0;
}

【易错提醒】

1. 下标一致性：注意数组是从1开始还是0开始，lower_bound返回指针，减去数组首地址得到下标
2. 去重必要性：存在重复数值时必须去重，否则相同数值会映射到不同下标，导致逻辑错误
3. 二分边界：手动实现二分必须保证能找到第一个符合条件的位置，避免返回无效值

---

三、尺取法（双指针）算法

3.1 算法核心概述

【定义】通过两个指针l（左指针）和r（右指针）维护一段连续区间，根据当前区间是否满足题目要求，动态移动指针调整区间，在O(n) 时间复杂度内解决区间统计问题 【核心优势】一次遍历完成计算，时间复杂度远优于暴力枚举的O(n²) 【适用前提】

1. 答案一定是一段连续的区间
2. 区间满足单调性：当区间[r]满足条件时，所有包含[r]的更大区间也满足条件（反之亦然） 【经典适用场景】区间元素种类统计、满足条件的最短/最长区间、有序数组多数之和、子串匹配

3.2 标准实现步骤

1. 初始化左指针l=1、右指针r=1，初始化区间统计变量
2. 循环移动指针，直到右指针超出数组边界
3. 若当前区间不满足条件，右移右指针r扩大区间，更新统计变量
4. 若当前区间满足条件，更新最优答案，右移左指针l缩小区间，更新统计变量
5. 循环结束后输出最优答案

3.3 完整模板例题（离散化+尺取法经典题）

【题目大意】给定n个元素，每个元素有一个数值和一个编号（编号范围极大），求包含所有编号种类的、数值差最小的连续区间

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;

int n, ans = 1e9; // ans存储最终答案，初始化为极大值
int b[MAXN]; // 统计离散化后每个编号的总出现次数
int c[MAXN]; // 离散化辅助数组
int d[MAXN]; // 尺取法区间内，每个编号的出现次数
int typeCnt = 0; // 编号总种类数
struct Node {
    int val, id; // val:数值，id:原编号
}s[MAXN];

// 按数值从小到大排序，保证尺取法的单调性
bool cmp(Node s1, Node s2){
    return s1.val < s2.val;
}

// 二分实现离散化映射
int getDiscreteId(int x){
    int l = 1, r = n, ans = n;
    while (l <= r){
        int mid = (l + r) / 2;
        if(c[mid] >= x) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ans;
}

int main(){
    // 1. 输入数据
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s[i].val >> s[i].id;
        c[i] = s[i].id;
    } 

    // 2. 离散化处理
    sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++){
        s[i].id = getDiscreteId(s[i].id);
        b[s[i].id]++;
        if(b[s[i].id] == 1) typeCnt++; // 统计总种类数
    } 

    // 3. 按数值排序，保证尺取法单调性
    sort(s + 1, s + 1 + n, cmp);

    // 4. 尺取法核心逻辑
    int l = 1, r = 1;
    int nowCnt = 1; // 当前区间内的编号种类数
    d[s[1].id] = 1; // 初始化第一个元素的计数

    while (r <= n && l <= n){
        if(nowCnt == typeCnt){ // 区间包含所有种类，满足条件
            ans = min(ans, s[r].val - s[l].val); // 更新最小数值差
            // 左指针右移，缩小区间尝试更优解
            d[s[l].id]--;
            if(d[s[l].id] == 0) nowCnt--; // 该种类在区间内消失，种类数-1
            l++;
        }else{ // 不满足条件，右指针右移扩大区间
            r++;
            if(r > n) break; // 防止数组越界
            d[s[r].id]++;
            if(d[s[r].id] == 1) nowCnt++; // 新增种类，种类数+1
        }
    }

    // 5. 输出答案
    cout << ans << endl;
    return 0;
}

【易错提醒】

1. 边界处理：右指针移动时必须判断是否超过n，防止数组越界
2. 计数顺序：移动指针时，必须先更新计数，再更新种类数，顺序不可颠倒
3. 初始值：答案ans必须初始化为足够大的数（如1e9），避免初始值过小导致答案错误
4. 单调性前提：必须保证数组有序，否则尺取法的单调性不成立，会漏掉正确答案

---

四、经典贪心算法模型

4.1 贪心算法核心概述

【定义】在每一步决策中，都做出当前看起来最优的选择，最终推导出全局最优解的算法 【核心前提】问题必须满足两个性质：

1. 贪心选择性质：全局最优解可以通过一系列局部最优的选择得到
2. 最优子结构性质：一个问题的最优解包含其子问题的最优解 【解题关键】找到正确的贪心策略，错误的贪心会直接导致答案错误

---

4.2 模型1：均分纸牌问题

【题目大意】有n堆纸牌，每堆有a[i]张，总牌数可被n整除。每次可将某一堆的1张牌移到相邻堆，求让所有堆牌数相等的最少移动次数 【贪心策略】从左到右遍历每一堆，多的牌往右移，少的牌从右边借，累计每一步差值的绝对值之和，即为最少移动次数 【核心原理】每一步只处理当前堆与下一堆的关系，保证当前堆达到目标值，后续无需回头处理，保证全局最优 【完整模板代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;

int n, a[MAXN];

int main(){
    // 1. 输入数据
    cin >> n;
    long long sum = 0; // 总牌数，用long long防止溢出
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }

    // 2. 计算每堆最终目标牌数
    int target = sum / n;

    // 3. 贪心核心逻辑
    long long ans = 0; // 总移动次数
    long long now = 0; // 当前累计差值
    for(int i = 1; i <= n; i++){
        now += a[i] - target; // 累计当前堆与目标值的差值
        ans += abs(now); // 差值的绝对值即为需要移动的牌数，累计总次数
    }

    // 4. 输出答案
    cout << ans << endl;
    return 0;
}

【易错提醒】

1. 数据溢出：总牌数和移动次数可能极大，必须用long long类型存储
2. 遍历顺序：必须按顺序遍历，不可跳堆，保证贪心策略的正确性
3. 前提校验：必须保证总牌数能被n整除，否则问题无解

---

4.3 模型2：木板覆盖问题

【题目大意】长度为L的牛棚中，n头牛分布在不同位置，最多用m块木板盖住所有牛，木板可任意裁剪，求盖住所有牛所需的木板最小总长度 【贪心策略】

1. 初始值：1块木板盖住所有牛的长度 = 最右牛位置 - 最左牛位置 + 1
2. 每多1块木板，可断开1个最大的空隙，减少的长度等于空隙长度
3. 最终长度 = 初始长度 - 前m-1个最大空隙的和 【核心原理】要让木板总长度最小，就要让木板之间的空隙尽可能大，每多一块木板就能多断开一个大空隙 【完整模板代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;

int m, L, n;
int a[MAXN]; // 存储每头牛的位置
int gap[MAXN]; // 存储相邻两头牛之间的空隙长度
int gapCnt = 0; // 空隙的总数量

int main(){
    // 1. 输入数据
    cin >> m >> L >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 2. 对牛的位置排序，才能计算相邻空隙
    sort(a + 1, a + 1 + n);

    // 3. 计算1块木板的初始长度
    int totalLen = a[n] - a[1] + 1;

    // 4. 计算所有相邻牛之间的空隙长度
    for (int i = 2; i <= n; i++){
        gap[++gapCnt] = a[i] - a[i - 1] - 1; // 空隙长度=两头牛位置差-1
    }

    // 5. 空隙从大到小排序，优先选择最大的空隙
    sort(gap + 1, gap + 1 + gapCnt, greater<int>());

    // 6. 累加前m-1个最大空隙，防止m-1超过空隙总数
    int maxGapSum = 0;
    int useGap = min(m - 1, gapCnt);
    for (int i = 1; i <= useGap; i++){
        maxGapSum += gap[i];
    }

    // 7. 计算最小木板总长度并输出
    int ans = totalLen - maxGapSum;
    cout << ans << endl;

    return 0;
}

【易错提醒】

1. 排序前置：必须先对牛的位置排序，否则计算的空隙完全错误
2. 空隙计算：空隙长度必须是a[i]-a[i-1]-1，减1是因为牛的位置本身需要被木板覆盖
3. 边界处理：当m大于空隙数量时，最多只能断开所有空隙，此时木板长度等于牛的数量

---

4.4 模型3：带期限的活动安排（最大收益）

【题目大意】有n个活动，每个活动有最晚完成期限t和完成奖励w，每个活动需要1天完成，一天只能做1个活动，求能获得的最大奖励总和 【贪心策略】

1. 按奖励从大到小排序，优先选择奖励高的活动
2. 对每个活动，从它的最晚期限往前找，找到第一个空闲日期安排该活动
3. 找不到空闲日期则放弃该活动 【核心原理】优先保证高奖励活动能被安排，每个活动尽量往晚的日期安排，保留前面的空闲日期给其他期限更早的活动 【完整模板代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;

int n;
int a[MAXN]; // a[i]记录第i天安排的活动奖励，0表示空闲
long long ans = 0; // 总奖励，用long long防止溢出

// 活动结构体
struct Activity {
    int t; // 最晚完成期限
    int w; // 活动奖励
}s[MAXN];

// 排序规则：按奖励从大到小排序，优先处理高奖励活动
bool cmp(Activity s1, Activity s2){
    return s1.w > s2.w;
}

int main(){
    // 1. 输入数据
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> s[i].t >> s[i].w;
    }

    // 2. 按奖励降序排序
    sort(s + 1, s + 1 + n, cmp);

    // 3. 贪心核心逻辑：安排活动
    for(int i = 1; i <= n; i++){
        // 从最晚期限往前找第一个空闲日期
        for(int j = s[i].t; j >= 1; j--){
            if(a[j] == 0){ // 找到空闲日期
                a[j] = s[i].w; // 安排活动
                break; // 安排完成，退出循环
            }
        }
    }

    // 4. 累加总奖励
    for(int i = 1; i < MAXN; i++){
        ans += a[i];
    }

    // 5. 输出答案
    cout << ans << endl;
    return 0;
}

【易错提醒】

1. 排序规则：必须按奖励从大到小排序，不可按日期排序，否则无法保证最大收益
2. 查找方向：必须从最晚期限往前找，不可从前往后，否则会占用早日期，导致期限早的活动无法安排
3. 数组边界：a数组的大小必须大于等于最大的活动期限，防止数组越界

---

五、核心算法速记表

算法	核心思想	时间复杂度	核心适用场景
离散化	保序映射，压缩数值范围	O(n log n)（排序+二分）	数值范围大、数据量小的下标计数场景
尺取法	双指针维护连续区间，动态调整	O(n)	连续区间统计、满足单调性的区间问题
均分纸牌贪心	从左到右累计差值，绝对值求和		相邻移动、均分目标的最小次数问题
木板覆盖贪心	优先断开最大空隙，最小化总长度	O(n log n)（排序）	区间覆盖、多段覆盖最小长度问题
活动安排贪心	优先选高收益，尽量晚安排	O(n²)，可优化至O(n log n)	带期限的收益最大化调度问题