算法练习题解：哈希表、前缀和与贪心算法实战 | 极客日志

C++算法

算法练习题解：哈希表、前缀和与贪心算法实战

整理六道经典算法练习题，涵盖火柴棒等式、导弹拦截、铺设道路、书架摆放、单词统计及连续自然数和。涉及暴力枚举、贪心算法、动态规划（01 背包）、前缀和与哈希表、字符串处理等核心知识点。通过具体代码实现与思路解析，帮助读者掌握常见算法模板在实际题目中的应用，适合备战蓝桥杯及各类算法竞赛。

霸天发布于 2026/2/90 浏览

算法练习题解：哈希表、前缀和与贪心算法实战

前言

这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。对应题目点链接即可做。

本期涉及算法：哈希表，前缀和，背包问题，特殊枚举，字符串函数运用与细节处理，贪心算法。

题目清单

1.火柴棒等式

题目：P1149 [NOIP 2008 提高组] 火柴棒等式

图片描述

解法：暴力枚举 n的最大值为 24，由于'+'和'='要用掉 4 根火柴，剩下 20 根火柴。进行估算，1111 + 1 = 1112 要用掉 25 根火柴，所以四位数以上不考虑。711 + 0 = 711，满足条件，所以枚举所有 1~1000 即可，判断是否刚好等于 n。

**细节：**因为不能有前导 0，要对 0 特殊处理。

代码：

#include <iostream>
using namespace std;

int n;
int a[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int calc(int x) {
    if (x == 0) return 6; // 边界处理
    int sum = 0;
    while (x) {
        sum += a[x % 10];
        x /= 10;
    }
    return sum;
}

  {
    cin >> n;
     ret = ;
     ( a = ; a <= ; a++) {
         ( b = ; b <= ; b++) {
             c = a + b;
             ((a) + (b) + (c) +  == n) ret++;
        }
    }
    cout << ret << endl;
     ;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int x1, y1, x2, y2, n;
struct node {
    int x, y, d;
} a[N];

int calc(int i, int x, int y) {
    int dx = x - a[i].x;
    int dy = y - a[i].y;
    return dx * dx + dy * dy;
}

bool cmp(node& a, node& b) {
    return a.d > b.d;
}

int main() {
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        a[i].d = calc(i, x1, y1);
    }
    sort(a + 1, a + 1 + n, cmp);
    int ret = a[1].d;
    int r2 = 0;
    for (int i = 2; i <= n + 1; i++) {
        int r1 = a[i].d;
        r2 = max(r2, calc(i - 1, x2, y2));
        ret = min(ret, r1 + r2);
    }
    cout << ret << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

int main() {
    cin >> n;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > a[i - 1]) {
            ret += a[i] - a[i - 1];
        }
    }
    cout << ret << endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 1e4 + 10;
int n;
int t[N], w[N];
int f[M]; // f[i][j] 优化一维，f[i][j],从前 i 本书挑选，水平放置厚度为 j，此时的最小宽度

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> w[i];
        sum += t[i];
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = sum; j >= t[i]; j--) {
            f[j] = min(f[j], f[j - t[i]] + w[i]);
        }
    }
    for (int j = sum; j >= 0; j--) {
        if (f[j] <= sum - j) {
            cout << sum - j << endl;
            break;
        }
    }
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    string s, t;
    cin >> s;
    getchar(); // 读入换行符
    getline(cin, t); // 要读空格
    
    // 预处理
    s = ' ' + s + ' ';
    t = ' ' + t + ' ';
    
    // 大写转小写
    for (int i = 0; i < s.size(); i++) {
        s[i] = tolower(s[i]);
    }
    for (int i = 0; i < t.size(); i++) {
        t[i] = tolower(t[i]);
    }
    
    int cnt = 0, first = 0;
    if (t.find(s) == -1) {
        cout << -1 << endl;
    } else {
        first = t.find(s);
        int pos = 0;
        while (t.find(s, pos) != -1) {
            pos = t.find(s, pos);
            cnt++;
            pos++;
        }
        cout << cnt << " " << first << endl;
    }
    return 0;
}

#include <iostream>
#include <unordered_map>
using namespace std;

typedef long long LL;
int m;
unordered_map<LL, int> mp; // 前缀和对应的索引

int main() {
    cin >> m;
    int n = (m + 1) / 2; // 枚举范围
    mp[0] = 0; // <0, 0> 赋值语句（执行操作）不能直接在全局作用域执行
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i; // sum - m
        if (mp.count(sum - m)) {
            cout << mp[sum - m] + 1 << " " << i << endl;
        }
        mp[sum] = i;
    }
    return 0;
}