第十四届蓝桥杯编程题部分代码题解

C. 冶炼金属

最大值就是取 $a/b$ 的最小值，最小值就是二分找到满足 $mid\ast (b_i+1)\ge 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-max$

#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. 整数删除

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

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

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

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

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

#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没关同步流啊，为什么没呢？很简单啊，怕过不了编译，然后就真忘了，我是傻逼