【蓝桥杯】第十五届蓝桥杯C/C++B组省赛补题

本文主要是介绍【蓝桥杯】第十五届蓝桥杯C/C++B组省赛补题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 估分
- 试题 A: 握手问题
- 试题 B: 小球反弹
- 试题 C: 好数
- 试题 D: R 格式
- 试题 E: 宝石组合
- 试题 F: 数字接龙
- 试题 G: 爬山
- 试题 H: 拔河

估分

测试网址：民间测试数据

$5 + 0 + 9 + 5 + 2 + 5 + 18 + 2 = 46$

试题 A: 握手问题

#include <bits/stdc++.h>using namespace std;typedef pair<int, int> PII;void solve() {set<PII> s;int res = 7 * 43;for (int i = 1; i <= 43; i++)for (int j = 1; j <= 43; j++)if (i != j)s.insert({min(i, j), max(i, j)});	cout << res + s.size() << endl;//ans = 1204
} int main() {int t = 1;//cin >> t;while (t --) solve();return 0;
}

试题 B: 小球反弹

不会

试题 C: 好数

这题数据 $1 e 7$ ，暴力跑民间数据（92分，估分9分）

#include <bits/stdc++.h>using namespace std;bool check(int x) {vector<int> v;while (x) {v.push_back(x % 10);x /= 10;}for (int i = 0; i < v.size(); i++) {if (i % 2 == 0 && v[i] % 2 == 0) //奇数位 是偶数 return false;if (i % 2 != 0 && v[i] % 2 != 0) // 偶数位 是奇数 return false;}return true;
}void solve() {int n;cin >> n;int res = 0;for (int i = 1; i <= n; i++) {if (check(i)) res ++;}cout << res << endl;
}signed main() {int t = 1;//cin >> t;while (t --) solve();return 0;
}

试题 D: R 格式

考察高精度乘法、高精度加法，考场上直接暴力写的（民间测试52分，估分5分）

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e5 + 7, inf = 0x3f3f3f3f, mod = 1e9 + 7;
// 浮点数 高精度乘法 ？ 
void solve() {long double n, d;cin >> n >> d;long double res = 1.0 * d * (pow(2, n));//cout << fixed << setprecision(0) << (long double)(pow(2, n)) << endl;cout << fixed << setprecision(0) << res << endl;
}signed main() {int t = 1;//cin >> t;while (t --) solve();return 0;
}

正解：模拟高精度乘法，高精度加法

#include <bits/stdc++.h>
using namespace std;int n; string d;
vector<int> A, B;vector<int> mul(vector<int> &A, int b) {vector<int> C;int t = 0;for (int i = 0; i < A.size() || t; i++) {if (i < A.size()) t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}vector<int> mul(vector<int> &A, vector<int> &B) {vector<int> C(A.size() + B.size() + 7, 0);for (int i = 0; i < A.size(); i++) {for (int j = 0; j < B.size(); j++) {C[i + j] += A[i] * B[j];}}for (int i = 0; i + 1 < C.size(); i++) {C[i + 1] += C[i] / 10;C[i] %= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();reverse(C.begin(), C.end());return C;
}vector<int> add(vector<int> &A, vector<int> &B) {if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i++) {t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}int main() {cin >> n >> d;A.push_back(1);while (n--) A = mul(A, 2);//for (auto c : A) cout << c; cout << endl;int len = d.size() - d.find('.') - 1;reverse(d.begin(), d.end());for (auto c: d) {if (c != '.')B.push_back(c - '0');}//for (auto c : B) cout << c; cout << endl;auto res = mul(A, B);//for (auto c : res) cout << c; cout << endl;int last = -1;while (len--) last = res.back(), res.pop_back();if (last >= 5) {vector<int> base;base.push_back(1);reverse(res.begin(), res.end());res = add(res, base);reverse(res.begin(), res.end());}for (auto c: res) cout << c;
}

试题 E: 宝石组合

数论，赛场暴力写的民间测试过了一个点，估分2分

试题 F: 数字接龙

赛场调dfs调了很久调不出来，最后输出-1民间测试得分一半, 估分5分吧。正解dfs搜索，注意数学中的直角坐标方向与二维数组中的方向是不同的，按0，1，2…8的方向进行搜索，即可得到字典序最小的答案。最重要的问题是判路径是否交叉，可以拿一个dir数组记录当前遍历位置所走的方向（0~8），判断交叉共有四种情况即方向为1，3，5，7时，四种情况如下：
i == 1 && (dir[x - 1][y] == 3 || dir[x][y + 1] == 7)
i == 3 && (dir[x + 1][y] == 1 || dir[x][y + 1] == 5)
i == 5 && (dir[x][y - 1] == 3 || dir[x + 1][y] == 7)
i == 7 && (dir[x][y - 1] == 1 || dir[x - 1][y] == 5)
参考：数字接龙-蓝桥杯

#include <bits/stdc++.h>using namespace std;typedef pair<int ,int> PII;
const int N = 10 + 7;
// int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; // 按照 0 1 2 3 ... 8的方向遍历
int n, k, g[N][N], dir[N][N], st[N][N];
vector<int> ans;bool dfs(int x, int y, int cnt) {if (x == n - 1 && y == n - 1 && cnt == n * n) return true;for (int i = 0; i < 8; i++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= n || st[a][b]) continue;if ((g[a][b] != g[x][y] + 1 && g[x][y] >= 0 && g[x][y] < k - 1) || (g[a][b] != 0 && g[x][y] == k - 1)) continue;//检查是否路径交叉 if (i == 1 && (dir[x - 1][y] == 3 || dir[x][y + 1] == 7)) continue;if (i == 3 && (dir[x + 1][y] == 1 || dir[x][y + 1] == 5)) continue; if (i == 5 && (dir[x][y - 1] == 3 || dir[x + 1][y] == 7)) continue; if (i == 7 && (dir[x][y - 1] == 1 || dir[x - 1][y] == 5)) continue; st[x][y] = 1, dir[x][y] = i;ans.push_back(i);if (dfs(a, b, cnt + 1)) return true;ans.pop_back();st[x][y] = 0, dir[x][y] = -1; //回溯}return false;
}void solve() {cin >> n >> k;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> g[i][j];if (g[n - 1][n - 1] != k - 1 || g[0][0] != 0) {cout << -1; return ;}	memset(dir, -1, sizeof dir);st[0][0] = 1;if (dfs(0, 0, 1)) {for (auto c : ans) cout << c;} else {cout << -1;}
}signed main() {int t = 1;//cin >> t;while (t --) solve();return 0;
}

试题 G: 爬山

思路：贪心 + 堆，每次用使用消除更多的方法，民间数据（92分，估分18分）

#include <bits/stdc++.h>#define x first
#define y second
#define int long longusing namespace std;typedef pair<int ,int> PII;
const int N = 1e5 + 7, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int n, k, q, p, x;//贪心 堆 void solve() {cin >> n >> p >> q;priority_queue<int, vector<int>> heap;for (int i = 1; i <= n; i++) {cin >> x;heap.push(x);}while (!heap.empty()) {auto t = heap.top();if (p <= 0 && q <= 0) break;if (p > 0 && q > 0) {heap.pop();int det1 = abs(t - floor(sqrt(t))), det2 = t / 2;if (det1 >= det2) heap.push(floor(sqrt(t))), p --;elseheap.push(t / 2), q --;}else if (p > 0 && q <= 0) {heap.pop();heap.push(floor(sqrt(t))), p --;} else if (p <= 0 && q > 0) {heap.pop();heap.push(t / 2), q --;} }int res = 0;while (!heap.empty()) {res += heap.top();//cout << heap.top() << endl;heap.pop();}cout << res << endl;
}signed main() {int t = 1;//cin >> t;while (t --) solve();return 0;
}