第十四届蓝桥杯编程题部分代码题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯编程题部分代码题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C. 冶炼金属

最大值就是取 $a / b$ 的最小值，最小值就是二分找到满足 $mid * (b_i + 1) ≥ a_i$ 的最小值

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
    int l = 0, r = 1e9;
    auto check = [&](int mid)
    {
        for (int i = 0; i < n; i++)
            if (mid * (a[i].y + 1) <= a[i].x) return false;
        return true;
    };
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << ' ';
    int minn = 1e9;
    for (int i = 0; i < n; i++)
        minn = min(minn, a[i].x / a[i].y);
    cout << minn << '\n';
}

signed main()
{
    // freopen("Sample.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    // cout << "Time:" << (double)clock() / 1000 << '\n';
    return 0;
}

D. 飞机降落

全排列枚举所有降落方案，然后判断即可

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> t(n + 10), d(n + 10), l(n + 10);
    for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> l[i];
    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;
    do {
        int tt = 0;
        bool flag = true;
        for (int i = 0; i < n; i++)
        {
            int x = p[i];
            if (tt > t[x] + d[x])
            {
                flag = false;
                break;
            }
            tt = max(tt, t[x]);
            tt += l[x];
        }
        if (flag) 
        {
            cout << "YES" << '\n';
            return;
        }
    } while (next_permutation(p.begin(), p.end()));
    cout << "NO" << '\n';
}

signed main()
{
    // freopen("Sample.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    // cout << "Time:" << (double)clock() / 1000 << '\n';
    return 0;
}

E. 接龙数列

状态定义： $f [i, j]$ 为前 $i$ 个数，以 $j$ 结尾的最长合法子序列，答案就是 $n - ma x$

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

void solve()
{
    int n;
    cin >> n;
    map<int, int> mp;
    vector<int> a(n);
    vector<pair<int, int>> b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        b[i].y = a[i] % 10;
        int x = a[i];
        while (x >= 10) x /= 10;
        b[i].x = x;
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x = mp[b[i].x];
        mp[b[i].y] = max(mp[b[i].y], x + 1);
        ans = max(ans, mp[b[i].y]);
    }
    cout << n - ans << '\n';
}

signed main()
{
    // freopen("Sample.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    // cout << "Time:" << (double)clock() / 1000 << '\n';
    return 0;
}

F. 岛屿个数

考场上没什么思路，随便写了个Flood Fill就润了

G. 字串简写

处理 $b$ 的前缀和，然后扫一遍即可

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

void solve()
{
    int k;
    cin >> k;
    string s;
    char a, b;
    cin >> s >> a >> b;
    int n = s.size();
    s = " " + s;
    vector<int> B(n + 10);
    for (int i = 1; i <= n; i++)
        if (s[i] == b) B[i] ++;
    for (int i = 1; i <= n; i++) B[i] += B[i - 1];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == a)
        {
            if (i + k - 1 > n) continue;
            ans += B[n] - B[i + k - 2];
        }
    }
    cout << ans << '\n';
}

signed main()
{
    // freopen("Sample.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    // cout << "Time:" << (double)clock() / 1000 << '\n';
    return 0;
}

H. 整数删除

首先初始化下每个数的前驱和后继

开一个小根堆，把所有数的大小和位置都放进去

每次循环，拿到数组中最小的数，标记上位置，然后操作它和它的前驱后继

但是可能拿到的数，已经被改变过了，所以我们需要开一个 $ma p$ ，记录下每个位置被改变过多少次

最后把没有被标记的数输出即可

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 10);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<pair<int, int>> b(n + 10);
    for (int i = 1; i <= n; i++) b[i] = {i - 1, i + 1};
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    for (int i = 1; i <= n; i++) heap.push({a[i], i});
    map<int, int> mp;
    vector<bool> st(n + 10);
    for (int i = 0; i < k; i++)
    {
        while (mp[heap.top().y])
        {
            mp[heap.top().y] --;
            heap.pop();
        }
        auto t = heap.top();
        heap.pop();
        st[t.y] = true;
        int l = b[t.y].x, r = b[t.y].y;
        b[l].y = r, b[r].x = l;
        a[l] += t.x, a[r] += t.x;
        mp[l] ++, mp[r] ++;
        if (l) heap.push({a[l], l});
        if (r <= n) heap.push({a[r], r});
    }
    for (int i = 1; i <= n; i++)
        if (!st[i]) cout << a[i] << ' ';
}

signed main()
{
    // freopen("Sample.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    // cout << "Time:" << (double)clock() / 1000 << '\n';
    return 0;
}

写在最后

剩下两题都是LCA好像，不太会，导游暴力Floyd骗分，最后一题没读完题，输出样例后就选择去检查了，上述几题都过了民间数据了，应该问题不大，很好啊，好像省一稳了？噢，原来有人赛时没开long long没关同步流啊，为什么没呢？很简单啊，怕过不了编译，然后就真忘了，我是傻逼文章来源地址https://www.toymoban.com/news/detail-410422.html

到了这里，关于第十四届蓝桥杯编程题部分代码题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！