C++算法入门经典题型笔记（高效复习版）

---

题型1：质数筛+暴力枚举（怪物攻击问题）

题目描述

怪物生命值为hp，两种攻击方式：

1. 物理攻击：第i次伤害为2^(i-1)（1,2,4,8...），可多次使用
2. 魔法攻击：仅可使用1次，伤害为任意质数 求将生命值恰好打到0的最少攻击次数，无法做到输出-1

核心思路

1. 预处理：埃氏筛预处理1e5以内质数；预处理前i次物理攻击总伤害s[i] = 2^i - 1
2. 暴力枚举：物理攻击最多16次（2^16-1=65535 < 1e5，2^17-1=131071 > 1e5）
3. 可行性判断：
   • s[i] == hp：仅需i次物理攻击
   • s[i] < hp且剩余血量为质数：需i+1次攻击（i次物理+1次魔法）

核心代码模板

const int MAX_HP = 1e5+10;
bool isP[MAX_HP];
int h[20], s[20];

// 预处理质数（埃氏筛）
void init_prime() {
    isP[1] = 1; // 1不是质数
    for(int i=2; i<MAX_HP; i++)
        if(!isP[i])
            for(int j=i*2; j<MAX_HP; j+=i)
                isP[j] = 1;
}

// 预处理物理攻击前缀和
void init_attack() {
    h[1] = 1;
    for(int i=2; i<=16; i++) h[i] = h[i-1]*2;
    for(int i=1; i<=16; i++) s[i] = s[i-1]+h[i];
}

// 主逻辑
int solve(int hp) {
    int ans = 1e9;
    for(int i=0; i<=16; i++) {
        if(s[i] > hp) break; // 前缀和递增，超过直接退出
        if(s[i] == hp) ans = min(ans, i);
        else if(!isP[hp-s[i]]) ans = min(ans, i+1);
    }
    return ans == 1e9 ? -1 : ans;
}

💡 优化&易错点

• 前缀和严格递增，s[i] > hp时直接break
• ❌ 忘记isP[1] = 1；❌ 物理攻击次数上限算错；❌ 忽略魔法攻击只能用1次

---

题型2：几何基础-两个矩形的最小覆盖正方形

题目描述

给定两个轴对齐矩形的左下角和右上角坐标，求能完全覆盖它们的最小正方形面积。

核心思路

1. 先求两个矩形的最小包围矩形：
   • 左边界：min(x1, x3)，右边界：max(x2, x4)
   • 下边界：min(y1, y3)，上边界：max(y2, y4)
2. 最小正方形边长 = 包围矩形长和宽的最大值
3. 面积 = 边长 × 边长

核心代码模板

int solve(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    int left = min(x1, x3);
    int right = max(x2, x4);
    int bottom = min(y1, y3);
    int top = max(y2, y4);
    int side = max(right-left, top-bottom);
    return side * side;
}

⚠️ 易错点

• 边界的min/max搞反；该方法对重叠、相邻、分离的矩形都适用，无需特殊处理

---

题型3：字符串模拟-外观数列（报数问题）

题目描述

外观数列定义：第1项为"1"，第n项是对第n-1项的报数描述（如1→11→21→1211），求第n项。

核心思路

模拟法：遍历上一项字符串，统计连续相同字符的个数，将"个数+字符"拼接成新字符串。

核心代码模板

string countAndSay(int n) {
    string s = "1";
    for(int i=2; i<=n; i++) {
        string t;
        int cnt = 1;
        for(int j=1; j<s.size(); j++) {
            if(s[j] == s[j-1]) cnt++;
            else {
                t += to_string(cnt);
                t += s[j-1];
                cnt = 1;
            }
        }
        // 必须处理最后一组连续字符！
        t += to_string(cnt);
        t += s.back();
        s = t;
    }
    return s;
}

⚠️ 易错点

• ❌ 最容易忘：循环结束后添加最后一组的个数和字符
• ❌ 用cnt+'0'转字符串（cnt可能≥10，必须用to_string）

---

题型4：前缀和计数-环形数组区间最大值

题目描述

给定长度为n的环形数组（元素范围[-100, 100]），m次查询区间[x,y]的最大值（x>y时区间跨首尾）。

核心思路

数值范围极小（仅201个可能值），用前缀和计数数组：

• s[i][j]：前i个元素中，数值j-100出现的次数（加100消除负数下标）
• 求区间最大值：从200（对应100）往下遍历，第一个出现次数>0的就是最大值
• 环形区间：拆成[x,n]和[1,y]两个普通区间，取最大值

核心代码模板

const int MAXN = 1e5+10;
int s[MAXN][201];

// 预处理前缀和计数数组
void init(int a[], int n) {
    for(int i=1; i<=n; i++) {
        memcpy(s[i], s[i-1], sizeof(s[i])); // 复制上一行
        s[i][a[i]+100]++; // 数值偏移
    }
}

// 普通区间最大值
int get_max(int l, int r) {
    for(int i=200; i>=0; i--)
        if(s[r][i] - s[l-1][i] > 0)
            return i - 100;
    return -100;
}

// 环形区间查询
int query(int x, int y, int n) {
    if(x <= y) return get_max(x, y);
    else return max(get_max(x, n), get_max(1, y));
}

💡 适用场景

当数值范围远小于数组长度时，比线段树、ST表更简单高效

---

题型5：二分答案-最大化中位数

题目描述

给定数组a和k次操作（每次给一个元素加1），求操作后能得到的最大中位数。

核心思路

二分答案（答案具有单调性：如果t可行，所有≤t的数都可行）

1. 先将数组从小到大排序
2. 二分枚举可能的中位数t，用check函数判断可行性
3. check函数：要让中位数≥t，只需让中间及右边的元素≥t，计算操作次数是否≤k

核心代码模板

const int MAXN = 2e5+10;
int a[MAXN], n, k;

bool check(int t) {
    long long cnt = 0; // 操作次数可能很大，必须用long long
    for(int i = n/2 + 1; i <= n; i++) { // 仅处理中间及右边元素
        if(a[i] < t) cnt += t - a[i];
        if(cnt > k) return false; // 提前退出优化
    }
    return cnt <= k;
}

int solve() {
    sort(a+1, a+1+n);
    int l = 1, r = 2e9, ans = 0;
    while(l <= r) {
        int mid = l + (r - l)/2; // 避免溢出
        if(check(mid)) {
            ans = mid;
            l = mid + 1; // 尝试更大的中位数
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

📌 二分答案通用条件

✅ 答案具有单调性
✅ 可以快速判断某个值是否可行（check函数时间复杂度≤O(n)）

⚠️ 易错点

• ❌ 忘记先排序；❌ 操作次数用int导致溢出；❌ mid计算用(l+r)/2溢出

---

补充：质数最优性证明（常见考点）

问题：为什么用质数作为魔法攻击伤害是最优的？（假设魔法攻击可多次使用）

反证法： 假设存在合数m，用m作为伤害的次数比质数更少。

• 合数m可分解为m = p1×p2×...×pk（p1-pk为质数）
• 1次m伤害等价于k次质数伤害，显然1 ≤ k
• 当k>1时，用质数次数更少；当k=1时，m本身就是质数
• 因此，用质数永远不会比合数差，且通常更优

哥德巴赫猜想（拓展）

• 大于2的偶数可表示为2个质数的和
• 大于5的奇数可表示为3个质数的和
• 应用：将n分解为最少质数之和，最多需要3次

---

5分钟复习自测清单

✅ 能默写埃氏筛代码
✅ 能说出二分答案的两个必要条件
✅ 能写出外观数列的最后一组字符处理逻辑
✅ 能拆分环形数组的区间查询
✅ 能写出最大化中位数的check函数