【第16届蓝桥杯 | 软件赛】CB组省赛第二场

个人主页：Guiat
归属专栏：算法竞赛

正文

总共8道题。

A. 密密摆放（5分填空题）

【题目】密密摆放

【分析】
考察观察，首先考虑最多盒子数量：200 * 250 * 240 / (30 * 40 * 50)，观察到正好可以被整除，即最终结果。

【答案】200

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve() { cout << 200 * 250 * 240 / (30 * 40 * 50) << '\n'; }int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

B. 脉冲强度之和（5分填空题）

【题目】脉冲强度之和

【分析】
考察数学和观察。
p = k + (k + 1) + (k + 2) + ··· + (k + 9) = (k + (k + 9)) * 10 / 2 = 10k + 45（k为正整数）
1 <= p <= 20255202且各个数位上的数字都相同 => p = 55、555、5555、55555、555555、5555555
所以 ans = 55 + 555 + 5555 + 55555 + 555555 + 5555555

【答案】6172830

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve() { cout << 55 + 555 + 5555 + 55555 + 555555 + 5555555 << '\n'; }int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

C. 25 之和

【题目】25 之和

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve()
{int n; cin >> n;cout << (n + (n + 24)) * 25 / 2 << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

D. 旗帜

【题目】旗帜

【分析】

优先找规律。

观察上面两张图，总结出规律：（A下标之和） % 7 == 1 或 5，满足题目要求，找出规律后代码就很好写了。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;string s = "LANQIAO"; int ans;void solve()
{int h, w; cin >> h >> w;for (int i = 0; i < h; i ++) for (int j = 0; j < w; j ++){if ((i + j) % 7 == 1 || (i + j) % 7 == 5) ans ++;// if (s[(i + j) % 7] == 'A') ans ++;}cout << ans << '\n';
}int main()
{IOS; int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

E. 数列差分

【题目】数列差分

【分析】
贪心 + 排序 + 双指针。
贪心思路：让较大的 a[i] 尽量匹配较大的 b[j]，无法匹配时调整 b[j]（ans ++）。

可视化理解（双指针）

讲解完毕。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e5 + 10; int a[N], b[N], ans;void solve()
{int n; cin >> n;for (int i = 0; i < n; i ++) cin >> a[i];for (int i = 0; i < n; i ++) cin >> b[i];sort(a, a + n); sort(b, b + n);int i = n - 1, j = n - 1;while (j != -1){if (a[i] - b[j] <= 0) ans ++, j --;else i --, j --;}cout << ans << '\n';
}int main()
{IOS; int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

F. 树上寻宝

【题目】树上寻宝

【分析】

本题用dfs做就好了。

• 题意：给定一棵树，每个节点有一个权值。求距离根节点不超过 2k 的所有节点的权值之和。
• 思路：DFS遍历：计算每个深度（距离根节点的边数）的节点权值和。
• 累加结果：将深度不超过 2k 的所有节点的权值相加。
• 深度计算：deep[i] 表示深度为 i 的所有节点的权值和。
• 结果范围：题目要求不超过 k 条边，即深度不超过 2k（因为每条边连接两个节点）。

【AC_Code】

#include <iostream>
#include <vector>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const int N = 1e5 + 10;
vector<int> aList[N]; ll w[N], deep[N], ans;void dfs(int now, int fa, int step)
{deep[step] += w[now - 1];for (int a : aList[now]) if (a != fa) dfs(a, now, step + 1);
}void solve()
{int n, k; cin >> n >> k;for (int i = 0; i < n; i ++) cin >> w[i];for (int i = 0; i < n - 1; i ++){int u, v; cin >> u >> v;aList[u].push_back(v); aList[v].push_back(u);}dfs(1, -1, 0);for (int i = 0; i <= min(n, 2 * k); i ++) ans += deep[i];cout << ans << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

G. 翻转硬币

【题目】翻转硬币

【分析】

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std;const int N = 1e3 + 5; int n, m, a[N][N], dp[N][2][2];int calculate(int row, int prev, int curr, int next)
{int res = 0;for (int i = 1; i <= m; ++i){int cnt = 0;if (i > 1 && a[row][i] == a[row][i - 1]) cnt++;if (i < m && a[row][i] == a[row][i + 1]) cnt++;if (row > 1 && !(prev == curr ^ a[row][i] == a[row - 1][i])) cnt++;if (row < n && !(curr == next ^ a[row][i] == a[row + 1][i])) cnt++;res += cnt * cnt;}return res;
}void solve()
{cin >> n >> m;for (int i = 1; i <= n; ++i){string s; cin >> s;for (int j = 1; j <= m; ++j) a[i][j] = s[j - 1] - '0';}dp[2][0][0] = calculate(1, 0, 0, 0); dp[2][0][1] = calculate(1, 0, 1, 0);dp[2][1][0] = calculate(1, 0, 0, 1); dp[2][1][1] = calculate(1, 0, 1, 1);for (int i = 3; i <= n + 1; ++i){dp[i][0][0] = max(dp[i - 1][0][0] + calculate(i - 1, 0, 0, 0), dp[i - 1][0][1] + calculate(i - 1, 1, 0, 0));dp[i][0][1] = max(dp[i - 1][1][0] + calculate(i - 1, 0, 1, 0), dp[i - 1][1][1] + calculate(i - 1, 1, 1, 0));dp[i][1][0] = max(dp[i - 1][0][0] + calculate(i - 1, 0, 0, 1), dp[i - 1][0][1] + calculate(i - 1, 1, 0, 1));dp[i][1][1] = max(dp[i - 1][1][0] + calculate(i - 1, 0, 1, 1), dp[i - 1][1][1] + calculate(i - 1, 1, 1, 1));}int ans = max( { dp[n + 1][0][0], dp[n + 1][0][1], dp[n + 1][1][0], dp[n + 1][1][1] } );cout << ans << "\n";
}int main()
{IOS int _ = 1;while (_ --) solve();return 0;
}

H. 破解信息

【题目】破解信息

【分析】
简化题意：按序输出输入字符串的最大字符。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve()
{string s; cin >> s; char maxC = 'a'; int pos = 0, cnt = 0;for (int i = 0; i < s.length(); i ++){if (maxC < s[i]) maxC = s[i], i = pos;}for (char c : s) if (c == maxC) cnt ++;while (cnt --) cout << maxC; cout << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

结语
感谢您的阅读！期待您的一键三连！欢迎指正！