2023 蓝桥杯 C++ B组

民智有待提高

个人题解，仅供参考。QAQ
A 组：
A

235。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s = "5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";
    int n = 100;

    auto check = [&](string &s, string &t) {
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (j < (int) t.size() && s == t[j]) {
                j++;
            }
        }
        if (j == t.size()) {
            return true;
        }
        return false;
    };

    int ans = 0;
    string year = "2023";
    int d[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    for (int i = 1; i <= 12; i++) {
        string month = to_string(i);
        if (month.size() == 1) {
            month = "0" + month;
        }
        for (int j = 1; j <= d; j++) {
            string day = to_string(j);
            if (day.size() == 1) {
                day = "0" + day;
            }
            string t = year + month + day;
            if (check(s, t)) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
   
    return 0;
}
B

11027421。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

double eps = 1E-4;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    auto get = [&](int x, int y) {
        double zero = 1.0 * x / (1.0 * (x + y));
        double one = 1.0 * y / (1.0 * (x + y));
        return -(x * zero * log2(zero) + y * one * log2(one));
    };

    int n = 23333333;
    for (int i = 0; i <= n; i++) {
        if (abs(get(i, n - i) - 11625907.5798) <= eps) {
            cout << i << '\n';
            return 0;
        }
    }

    return 0;
}
C

签到，复杂度 O(n)。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int mx = 2E9, mn = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        mx = min(mx, a / b);
        mn = max(mn, a / (b + 1) + 1);
    }
    cout << mn << ' ' << mx << '\n';

    return 0;
}
D

全排列，复杂度 O(\sum (n!))。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a = {x, y, z};
    }
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        p = i;
    }

    do {
        bool ok = 1;
        int j = p[0];
        int time = a[j][0] + a[j][2];
        for (int i = 1; i < n; i++) {
            int j = p;
            if (time <= a[j][0] + a[j][1]) {
                time = max(time, a[j][0]);
                time += a[j][2];
            } else {
                ok = 0;
                break;
            }
        }
        if (ok) {
            cout << "YES\n";
            return;
        }
    } while (next_permutation(p.begin(), p.end()));

    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}
E

dp，复杂度 O(n)。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a;
    }
    vector<int> pre(10, -1);
    vector<int> f(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x = a[0] - '0';
        int y = a.back() - '0';
        if (pre[x] != -1) {
            f = f[pre[x]] + 1;
        } else {
            f = 1;
        }
        ans = max(ans, f);
        if (pre[y] == -1 || f > f[pre[y]]) {
            pre[y] = i;
        }
    }
    cout << n - ans << '\n';

    return 0;
}
F

先把外侧海水变成 2，然后除外侧海水以外全变成 1，然后看有几块 1。复杂度 O(\sum(n\cdot m))。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;

    n += 2;
    m += 2;

    vector<vector<int>> b(n, vector<int>(m));
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            char ch;
            cin >> ch;
            b[j] = ch - '0';
        }
    }

    int mx[] = {-1, 0, +1, 0, +1, +1, -1, -1};
    int my[] = {0, -1, 0, +1, -1, +1, -1, +1};

    auto bfs = [&](int x, int y, int N, int T, int K) {
        queue<array<int, 2>> q;
        q.push({x, y});
        b[x][y] = T;
        while (!q.empty()) {
            int i = q.front()[0];
            int j = q.front()[1];
            q.pop();
            for (int k = 0; k < K; k++) {
                int X = i + mx[k];
                int Y = j + my[k];
                if (X < 0 || X >= n) {
                    continue;
                }
                if (Y < 0 || Y >= m) {
                    continue;
                }
                if (b[X][Y] == N) {
                    b[X][Y] = T;
                    q.push({X, Y});
                }
            }
        }
    };

    bfs(0, 0, 0, 2, 8);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (b[j] != 2) {
                b[j] = 1;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (b[j] == 1) {
                ans++;
                bfs(i, j, 1, 2, 4);
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}
G

二分，复杂度 O(n\log n)。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    string s;
    char c[2] = {'a', 'a'};
    cin >> k >> s >> c[0] >> c[1];
    int n = s.size();
    vector<vector<int>> p(2);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            if (s == c[j]) {
                p[j].push_back(i);
            }
        }
    }
    i64 ans = 0;
    for (int i = 0; i < (int)p[0].size(); i++) {
        int j = p[0] + k - 1;
        if (p[1].back() < j) {
            continue;
        }
        int I = lower_bound(p[1].begin(), p[1].end(), j) - p[1].begin();
        int val = (int)p[1].size() - I;
        ans += val;
    }
    cout << ans << '\n';

    return 0;
}
H

优先队列，复杂度 O(n\log n)。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a;
    }

    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
    for (int i = 0; i < n; i++) {
        q.push({a, i});
    }

    vector<int> pre(n), nex(n);
    for (int i = 0; i < n; i++) {
        pre = i - 1;
    }
    for (int i = 0; i < n; i++) {
        nex = i + 1;
    }

    while (!q.empty()) {
        auto Top = q.top();
        i64 ai = Top.first;
        int i = Top.second;
        q.pop();
        if (ai != a) {
            q.push({a, i});
            continue;
        }
        a = -1;
        int Nex = nex;
        int Pre = pre;
        if (Nex < n) {
            a[Nex] += ai;
            pre[Nex] = Pre;
        }
        if (Pre >= 0) {
            a[Pre] += ai;
            nex[Pre] = Nex;
        }
        k--;
        if (k == 0) {
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        if (a != -1) {
            cout << a << ' ';
        }
    }
    cout << '\n';

    return 0;
}
I

lca，复杂度 O(n\log n+m\log n)。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> dep(n + 1, 1);
    vector<vector<int>> p(n + 1, vector<int>(__lg(n + 1) + 1));
    vector<i64> sum(n + 1);
    function<void(int, int)> dfs = [&](int cur, int pre) {
        p[cur][0] = pre;
        for (int i = 1; i <= __lg(dep[cur]); i++) {
            p[cur] = p[p[cur][i - 1]][i - 1];
        }
        for (auto &x : g[cur]) {
            int nex = x.first;
            int w = x.second;
            if (nex != pre) {
                dep[nex] = dep[cur] + 1;
                sum[nex] = sum[cur] + w;
                dfs(nex, cur);
            }
        }
    };

    dfs(1, 0);

    auto lca = [&](int x, int y) {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        for (int i = __lg(dep[x] - dep[y]); i >= 0; i--) {
            if (dep[p[x]] >= dep[y]) {
                x = p[x];
            }
        }
        if (x == y) {
            return x;
        }
        for (int i = __lg(dep[x]); i >= 0; i--) {
            if (p[x] != p[y]) {
                x = p[x];
                y = p[y];
            }
        }
        return p[x][0];
    };

    auto dis = [&](int x, int y) {
        int LCA = lca(x, y);
        return sum[x] + sum[y] - 2 * sum[LCA];
    };

    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a;
    }

    vector<i64> b(m);
    i64 tot = 0;
    vector<i64> d(m - 1);
    for (int i = 0; i < m - 1; i++) {
        d = dis(a, a[i + 1]);
        tot += d;
    }

    for (int i = 0; i < m; i++) {
        if (i > 0) {
            b += d[i - 1];
        }
        if (i < m - 1) {
            b += d;
        }
        if (i > 0 && i < m - 1) {
            b -= dis(a[i - 1], a[i + 1]);
        }
    }
   
    for (int i = 0; i < m; i++) {
        cout << tot - b << " \n"[i == m - 1];
    }

    return 0;
}
J

lca，树上差分，复杂度 O(n\log n+m\log n)。

C++ Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    vector<int> u(n - 1), v(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dep(n + 1, 1);
    vector<vector<int>> p(n + 1, vector<int>(__lg(n + 1) + 1));
    function<void(int, int)> dfs = [&](int cur, int pre) {
        p[cur][0] = pre;
        for (int i = 1; i <= __lg(dep[cur]); i++) {
            p[cur] = p[p[cur][i - 1]][i - 1];
        }
        for (auto nex : g[cur]) {
            if (nex != pre) {
                dep[nex] = dep[cur] + 1;
                dfs(nex, cur);
            }
        }
    };

    dfs(1, 0);

    auto lca = [&](int x, int y) {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        for (int i = __lg(dep[x] - dep[y]); i >= 0; i--) {
            if (dep[p[x]] >= dep[y]) {
                x = p[x];
            }
        }
        if (x == y) {
            return x;
        }
        for (int i = __lg(dep[x]); i >= 0; i--) {
            if (p[x] != p[y]) {
                x = p[x];
                y = p[y];
            }
        }
        return p[x][0];
    };

    vector<i64> sum(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        sum[x]++;
        sum[y]++;
        int LCA = lca(x, y);
        sum[LCA]--;
        sum[p[LCA][0]]--;
    }

    function<void(int, int)> dfs_again = [&](int cur, int pre) {
        for (auto &nex : g[cur]) {
            if (nex != pre) {
                dfs_again(nex, cur);
                sum[cur] += sum[nex];
            }
        }
    };
    dfs_again(1, 0);

    for (int i = n - 2; i >= 0; i--) {
        if (sum[u] == m && sum[v] == m) {
            cout << i + 1 << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
   
    return 0;
}

本文使用 Zhihu On VSCode 创作并发布

胡为民

太强了，我暴力了四五题，一题填空题不会哈哈。

久久广告

[害羞]

没有你的陪伴我好孤单

我一打开你这个就卡

西门无雪

c题应该有问题mx=min()mn=max()

夜之灾祸

有无A组

奔走的青春王鹏飞

马哥？[小情绪]

柒柒捌捌

[害羞]

卓娅

写反了QAQ

姜呈全

D题可以贪心，将飞机到达的时间从小到大排序，然后一个一个判断