C/C++蓝桥杯算法真题打卡（Day10）

一、P10424 [蓝桥杯 2024 省 B] 好数 - 洛谷

算法代码：

#include <stdio.h>
int main()
{
    int n, i;
    scanf("%d", &n);  // 输入一个整数 n
    for (; n > 0; n--)  // 从 n 开始，递减到 1
    {
        for (int m = n; m > 0;)  // 对每个数字 m = n，检查其每一位
        {
            if (m % 2 != 0) m /= 10;  // 如果最低位是奇数，去掉最低位
            else break;  // 如果最低位是偶数，退出循环
            if (m % 2 == 0) m /= 10;  // 如果新的最低位是偶数，去掉最低位
            else break;  // 如果新的最低位是奇数，退出循环
            if (m == 0) i++;  // 如果 m 变为 0，说明满足条件，计数器 i 增加
        }
    }
    printf("%d", i);  // 输出满足条件的数字的数量
    return 0;
}

二、P10391 [蓝桥杯 2024 省 A] 零食采购 - 洛谷 （跳）

大佬题解：

#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间
typedef long long ll;    // 定义long long类型的别名ll

const int N = 1e5 + 5, K = 22;  // 定义常量N为100005，K为22（用于倍增LCA算法）
int n, q, c[N], u, v, s, t, st[N][K + 2], dep[N], cnt[N][K + 2];  // 定义全局变量
// n：节点数量
// q：查询次数
// c[i]：节点i的颜色
// u, v, s, t：临时变量
// st[x][i]：节点x的第2^i级祖先
// dep[x]：节点x的深度
// cnt[x][i]：从根节点到节点x的路径上颜色i的出现次数

vector<int> g[N];  // 存储树的邻接表

void dfs(ll x, ll fx) {  // DFS函数，用于预处理LCA的倍增表和深度
    dep[x] = dep[fx] + 1;  // 计算节点x的深度
    st[x][0] = fx;  // 节点x的第2^0级祖先（即父节点）是fx
    for (ll i = 1; i <= K; i++) {  // 预处理倍增表
        st[x][i] = st[st[x][i - 1]][i - 1];  // 节点x的第2^i级祖先是其第2^(i-1)级祖先的第2^(i-1)级祖先
    }
    for (ll u : g[x]) {  // 遍历节点x的所有子节点
        if (u != fx) dfs(u, x);  // 如果子节点不是父节点，递归处理
    }
}

int LCA(int x, int y) {  // LCA函数，用于计算节点x和y的最近公共祖先
    if (dep[x] < dep[y]) swap(x, y);  // 确保x的深度不小于y
    for (ll i = K; i >= 0; i--) {  // 将x跳到与y同一深度
        ll fx = st[x][i];
        if (dep[fx] >= dep[y]) x = fx;
    }
    if (x == y) return x;  // 如果x和y相等，直接返回x
    for (int i = 20; i >= 0; i--) {  // 同时上跳x和y，直到找到LCA
        ll fa = st[x][i], fb = st[y][i];
        if (fa != fb) x = fa, y = fb;
    }
    return st[x][0];  // 返回LCA
}

void DFS(int x, int fx) {  // DFS函数，用于预处理颜色计数
    for (int u : g[x]) {  // 遍历节点x的所有子节点
        if (u == fx || u == x) continue;  // 跳过父节点和自身
        for (int i = 1; i <= 22; i++) {  // 复制父节点的颜色计数
            cnt[u][i] = cnt[x][i];
        }
        cnt[u][c[u]]++;  // 更新当前节点的颜色计数
        DFS(u, x);  // 递归处理子节点
    }
}

int main() {  // 主函数
    cin >> n >> q;  // 输入节点数量n和查询次数q
    for (int i = 1; i <= n; i++) {  // 输入每个节点的颜色
        cin >> c[i];
    }
    for (int i = 1; i < n; i++) {  // 输入树的边
        cin >> u >> v;
        g[u].push_back(v);  // 添加边u->v
        g[v].push_back(u);  // 添加边v->u
    }
    dfs(1, 1);  // 从根节点1开始预处理LCA的倍增表和深度
    cnt[1][c[1]]++;  // 初始化根节点的颜色计数
    DFS(1, 1);  // 从根节点1开始预处理颜色计数
    while (q--) {  // 处理每个查询
        cin >> s >> t;  // 输入查询的两个节点s和t
        int ans = 0, lc = LCA(s, t);  // 计算s和t的LCA
        for (int i = 1; i <= 22; i++) {  // 遍历所有颜色
            int tt = 0;
            if (c[lc] == i) tt = 1;  // 如果LCA的颜色是i，标记为1
            if (cnt[s][i] + cnt[t][i] - 2 * cnt[lc][i] + tt > 0) ans++;  // 计算路径上颜色i的出现次数
        }
        cout << ans << '\n';  // 输出结果
    }
    return 0;  // 程序结束
}