【第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;
}

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