蓝桥杯算法竞赛经典题解汇总

关于二分查找边界：

• (l + r + 1) / 2：找最大值（最后一个满足条件的）需要加 1，偏向右边。
• check 函数作用：检查如果正方形的边长是 mid，能不能从所有巧克力中切出至少 k 块。

蓝桥杯 124 密码脱落

题目链接：https://www.lanqiao.cn/problems/124/learning/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
char s[N];
int memo[N][N]; // 初始化为 -1
// 最长回文子序列
int dfs(int i, int j){
    if(memo[i][j] != -1) return memo[i][j];
    if(i == j) return memo[i][j] = 1;
    if(i > j) return memo[i][j] = 0;
    if(s[i] == s[j]) memo[i][j] = dfs(i+1, j-1) + 2;
    else memo[i][j] = max(dfs(i+1, j), dfs(i, j-1));
    return memo[i][j];
}
int main(){
    cin >> s;
    int n = strlen(s);
    memset(memo, -1, sizeof(memo));
    int max_pal = dfs(0, n-1);
    cout << n - max_pal << '\n';
    return 0;
}

题目大意：给一个字符串 s，问最少需要'脱落'多少个字符（即删除多少个字符），才能让剩下的字符构成一个回文串。

转化思路：最少删除字符数 = 字符串长度 - 最长回文子序列（LPS）的长度。

递归逻辑：

• 若 s[i] == s[j]，则 LPS(i, j) = LPS(i+1, j-1) + 2。
• 若 s[i] != s[j]，则 LPS(i, j) = max(LPS(i+1, j), LPS(i, j-1))。

注意：memo[i][j] 表示字符串从位置 i 到位置 j 的最长回文子序列长度，需初始化为 -1。

蓝桥杯 128 冰雹数

题目链接：https://www.lanqiao.cn/problems/128/learning/

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
bool vis[N];
int main() {
    ll n, max_h = 0;
    cin >> n;
    for(ll i = 1; i < n; ++i) {
        if(vis[i]) continue;
        ll x = i;
        while(x != 1) {
            if(x <= n) vis[x] = true;
            max_h = max(max_h, x);
            if(x % 2 == 0) x /= 2;
            else x = x * 3 + 1;
        }
    }
    cout << max_h << endl;
    return 0;
}

蓝桥杯 138 密文搜索

题目链接：https://www.lanqiao.cn/problems/138/learning/

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int n, ans = 0;
    cin >> s >> n;
    unordered_map<string, int> cnt; // 密码存放在哈希表中
    for(int i = 0; i < n; ++i) {
        string pwd;
        cin >> pwd;
        sort(pwd.begin(), pwd.end());
        cnt[pwd]++;
    }
    int len = s.size();
    for(int i = 0; i <= len - 8; ++i) {
        string sub = s.substr(i, 8); // 把 s 中的字串排序好再插哈希表存放的密码里面有没有
        sort(sub.begin(), sub.end());
        ans += cnt[sub];
    }
    cout << ans << endl;
    return 0;
}

蓝桥杯 143 饮料换购

题目链接：https://www.lanqiao.cn/problems/143/learning/

#include <iostream>
using namespace std;
int main() {
    int n, yu = 0, count;
    cin >> n;
    count = n;
    while(n >= 3) {
        yu = n % 3; // 多余的未能兑换的瓶子瓶盖 该瓶子包含在 count 中
        n = n / 3; // 瓶盖兑换的瓶子数量
        count += n;
        n += yu; // 新增的瓶子瓶盖加上未能兑换的瓶子瓶盖
    }
    cout << count;
    return 0;
}

蓝桥杯 146 三元组中心问题

题目链接：https://www.lanqiao.cn/problems/146/learning/

#include <iostream>
using namespace std;
int main() {
    int n, ans = 0;
    cin >> n;
    int a[1010];
    bool is_center[1010] = {false};
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for(int j = 1; j < n - 1; ++j) {
        for(int i = 0; i < j; ++ i) {
            for(int k = j + 1; k < n; ++k) {
                if(a[i] < a[j] && a[j] < a[k]) {
                    is_center[j] = true;
                    break;
                }
            }
            if (is_center[j]) break;
        }
    }
    for(int j = 0; j < n; ++j) {
        if (is_center[j]) ans++;
    }
    cout << ans << '\n';
}

定义：一个元素 a[j] 被称为'中心'，需要满足存在 i < j 且 a[i] < a[j]，以及存在 k > j 且 a[j] < a[k]。即 a[j] 左边至少有一个比它小的数，右边至少有一个比它大的数。

蓝桥杯 148 音节判断

题目链接：https://www.lanqiao.cn/problems/148/learning/

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    bool judge = 0; // 0 表示辅音 1 表示元音
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
        if ((s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') && judge == 1) {
            ans++;
            judge = 0;
        }else if (s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u' && judge == 0) {
            ans++;
            judge = 1;
        }
    }
    if (ans == 4) {
        cout << "yes" << endl;
    }else {
        cout << "no" << endl;
    }
    return 0;
}

蓝桥杯 162 通电

题目链接：https://www.lanqiao.cn/problems/162/learning/

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1010;
struct Village {
    int x, y, h;
} v[N];
double calc_cost(int i, int j) {
    int dx = v[i].x - v[j].x;
    int dy = v[i].y - v[j].y;
    int dh = v[i].h - v[j].h;
    return sqrt(dx*dx + dy*dy) + (double)dh*dh;
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> v[i].x >> v[i].y >> v[i].h;
    }
    double dist[N];
    bool vis[N] = {false};
    fill(dist, dist + n, 1e18);
    dist[0] = 0; // 初始化 1 号村庄（下标 0）为起点 距离 0
    double ans = 0;
    for(int i = 0; i < n; ++i) {
        int u = -1;
        double min_d = 1e18;
        for(int j = 0; j < n; ++j) {
            if(!vis[j] && dist[j] < min_d) {
                min_d = dist[j];
                u = j;
            }
        }
        vis[u] = true;
        ans += min_d;
        for (int j = 0; j < n; ++j) {
            if (!vis[j]) {
                double cost = calc_cost(u, j);
                if (cost < dist[j]) dist[j] = cost;
            }
        }
    }
    printf("%.2lf\n", ans);
    return 0;
}

蓝桥杯 178 全球变暖

题目链接：https://www.lanqiao.cn/problems/178/learning/

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
char g[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool has_safe;
void dfs(int x, int y) {
    if(x < 0 || x >=N || y < 0 || y >= N || g[x][y]!= '#') return;
    g[x][y] = '*'; // 标记当前点为已遍历
    bool is_safe = true;
    for(int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if(g[nx][ny] == '.') { is_safe = false; break; }
    }
    if(is_safe) has_safe = true;
    for(int i = 0; i < 4; ++i){
        dfs(x + dx[i], y + dy[i]);
    }
}
int main() {
    int n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> g[i];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(g[i][j] == '#') {
                has_safe = false;
                dfs(i, j);
                if(!has_safe) ans++;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

遇到一个 #，就开始 DFS，把整个岛屿的 # 改成 *（标记已访问）。在 DFS 过程中，每到一个 #，就检查它是不是安全陆地。只要岛屿上至少有一个安全陆地，这个岛屿就不会被完全淹没。