目录
题库链接：题库 - 蓝桥云课
1A：握手问题（填空5分）
问题描述
小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手 (且仅有一次)。但有 77 个人，这 7 人彼此之间没有进行握手 (但这 7 人与除这 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手?
注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
解析代码_数学_正解
比较简单的填空题，可以用组合数学计算，也可以分成两堆人来思考。
43个人每人握手42个人（彼此握手需要/2），有7个人需要握手43个人 。
#include <iostream>
using namespace std;
int main()
{
cout << 43 * 42 / 2 + 43 * 7 <<endl;
return 0;
}2B：小球反弹（填空5分）
问题描述
有一长方形，长为 343720 单位长度，宽为 233333 单位长度。在其内部左上角顶点有一小球 (无视其体积)，其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx:dy=15:17。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍五入保留两位小数。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个小数，在提交答案时只填写这个小数，填写多余的内容将无法得分。
解析代码_数学_正解
也是数学题，最终返回左上角时，走过的水平路程和垂直路程一定是343720 和233333 的偶数倍，并且水平路程与垂直路程之比一定为15 : 17 。写暴力去找结果即可，答案是1100325199.77
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int W = 233333;
const int L = 343720;
signed main()
{
for (int x = 2; x <= 10000; x += 2)
{
for (int y = 2; y <= 10000; y += 2)
{
if (15 * W * y == 17 * L * x)
{
printf("%.2llf", sqrt((L * x) * (L * x) + (W * y) * (W * y)));
return 0;
}
}
}
return 0;
}3C：好数（编程10分）
解析代码_暴力_正解
正解应该是数位dp，但是感觉数据不大，暴力枚举也能过。
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
bool inline judge(int x)
{
int k = 1;
while (x)
{
if ((x & 1) != (k & 1))
return false;
x /= 10;
k++;
}
return true;
}
signed main()
{
ios::sync_with_stdio(0); // 关流
cin.tie(0);
cout.tie(0);
int n = 0;
cin >> n;
int res = 0;
for (int i = 1; i <= n; i += 2)
{
if (judge(i))
++res;
}
cout << res << endl;
return 0;
}4D：R 格式（编程10分）
小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是：
将浮点数乘以 2^n；
四舍五入到最接近的整数。
输入格式
一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。
输出格式
输出一行表示答案：d 用 R 格式表示出来的值。
样例输入
2 3.14
样例输出
13
样例说明
3.14×2^2 = 12.56，四舍五入后为 13。
解析代码_高精度_正解
高精度加和乘
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
string add(string s, string t)
{
int end1 = s.size() - 1, end2 = t.size() - 1;
string ret;
int carry = 0;
while(end1 >= 0 || end2 >= 0)
{
int val1 = end1 >= 0 ? s[end1] - '0' : 0;
int val2 = end2 >= 0 ? t[end2] - '0' : 0;
ret += (val1 + val2 + carry) % 10 + '0';
if(val1 + val2 + carry > 9)
carry = 1;
else
carry = 0;
--end1;
--end2;
}
if(carry)
ret += '1';
reverse(ret.begin(), ret.end());
return ret;
}
string mul(string num1, string num2)
{
int n1 = num1.size(), n2 = num2.size();
vector<int> tmp(n1 + n2 - 1);
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
for(int i = 0; i < n1; ++i)
{
for(int j = 0; j < n2; ++j)
{
tmp[i+j] += (num1[i] - '0') * (num2[j] - '0');
}
}
string ret = "";
int carry = 0;
for(auto& e : tmp)
{
ret += ((e + carry) % 10 + '0');
carry = (e + carry) / 10;
}
if(carry)
ret += (carry + '0');
while(ret.size() > 1 && ret.back() == '0')
ret.pop_back(); // 处理前导0
reverse(ret.begin(), ret.end());
return ret;
}
signed main()
{
ios::sync_with_stdio(0); // 关流
cin.tie(0);
cout.tie(0);
int n = 0;
string d;
cin >> n >> d;
string res = "1";
for (int i = 0; i < n; i++)
{
res = mul(res, "2");
}
int pos = 0;
while (d[d.size() - 1 - pos] != '.')
{
pos++;
}
res = mul(res, d.substr(0, d.size() - pos - 1) + d.substr(d.size() - pos));
string remain = "5";
for (int i = 0; i < pos - 1; i++)
{
remain += "0";
}
res = add(res, remain);
cout << res.substr(0, res.size() - pos) << endl;
return 0;
}5E：宝石组合（编程15分）
问题描述
在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：
其中 LCM 表示的是最小公倍数函数。
小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。
输入格式
第一行包含一个整数 N 表示宝石个数。
第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。
输出格式
输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
样例输入
5
1 2 3 4 9
样例输出
1 2 3
解析代码_dp_正解
找最大gcd(a[i],a[j],a[k])，里面的最小的三个数
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[100100], b[100100];
vector<int> vec[100100];
signed main()
{
ios::sync_with_stdio(0); // 关流
cin.tie(0);
cout.tie(0);
int n = 0;
cin >> n;
int max_a = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[a[i]]++;
max_a = max(max_a, a[i]);
}
sort(a + 1, a + 1 + n);
for (int i = 2; i <= max_a; i++)
{
for (int j = i; j <= max_a; j += i)
{
for (int k = 1; k <= b[j]; k++)
{
if (vec[i].size() >= 3)
break;
vec[i].push_back(j);
}
}
}
for (int i = max_a; i >= 2; i--)
{
if (vec[i].size() >= 3)
{
cout << vec[i][0] << " " << vec[i][1] << " " << vec[i][2] << endl;
return 0;
}
}
cout << a[1] << " " << a[2] << " " << a[3] << endl;
return 0;
}6F：数字接龙（编程15分）
解析代码_dfs_正解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11;
int n, k;
int g[N][N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
string path;
bool st[N][N], edge[N][N][N][N];
bool dfs(int a, int b)
{
if (a == n - 1 && b == n - 1)
{
return path.size() == n * n - 1;
}
st[a][b] = true;
for (int i = 0; i < 8; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x < 0 || x >= n || y < 0 || y >= n)
continue;
if (st[x][y])
continue;
if (g[x][y] != (g[a][b] + 1) % k)
continue;
if (i % 2 && (edge[a][y][x][b] || edge[x][b][a][y]))
continue;
edge[a][b][x][y] = true;
path += i + '0';
if (dfs(x, y))
return true;
path.pop_back();
edge[a][b][x][y] = false; // 恢复现场
}
st[a][b] = false; // 恢复现场
return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
if (!dfs(0, 0))
cout << -1 << endl;
else
cout << path << endl;
return 0;
}7G：爬山（编程20分）
解析代码_贪心_有争议
贪心是官方题解，但是有些数据过不了。
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
const int N = 1e5 + 10; // 定义常量N，表示最大可能的输入规模
int main()
{
priority_queue<int> pq; // 声明一个大根堆，用于维护当前最大值
int n, p, q;
cin >> n >> p >> q; // 输入数字个数n，以及操作次数p和q
for (int i = 1; i <= n; i++) // 输入n个数字并加入堆中
{
int x;
cin >> x;
pq.push(x);
}
while (p || q) // 当还有操作次数时循环处理
{
int cur = pq.top(); // 获取当前最大值
pq.pop(); // 移除当前最大值
if (p) // 贪心优先执行p操作（开平方）
{
cur = sqrt(cur); // 对当前值开平方
p--; // 减少p操作次数
}
else if (q) // 当p操作用完时执行q操作（除以2）
{
cur /= 2; // 当前值除以2
q--; // 减少q操作次数
}
pq.push(cur); // 将处理后的值重新加入堆中
}
int s = 0; // 计算堆中所有元素的和
while (!pq.empty())
{
s += pq.top(); // 累加堆顶元素
pq.pop(); // 移除堆顶元素
}
cout << s << endl; // 输出最终结果
return 0;
}8H：拔河（编程20分）
解析代码_双指针二分_正解
#include <bits/stdc++.h>
#define int long long // 使用长整型
#define endl '\n'
using namespace std;
int num[1010] = {0}; // 存储原始数组
int pre[1010] = {0}; // 前缀和数组
multiset<int> mset; // 用于存储所有可能的子数组和
signed main()
{
ios::sync_with_stdio(0); // 关闭同步流以提高输入输出效率
cin.tie(0);
cout.tie(0);
int n = 0;
cin >> n; // 输入数组长度
for (int i = 1; i <= n; i++)
{
cin >> num[i]; // 输入数组元素
pre[i] = pre[i - 1] + num[i]; // 计算前缀和
}
for (int l = 1; l <= n; l++) // 生成所有可能的子数组和并存入multiset
{
for (int r = l + 1; r <= n; r++)
{
mset.insert(pre[r] - pre[l]); // 计算并存储子数组和
}
}
int res = INT_MAX; // 初始化结果为最大值
for (int r = 1; r < n; r++)
{
for (int l = 0; l < r; l++)
{
int val = pre[r] - pre[l]; // 计算当前子数组和
auto it = mset.lower_bound(val); // 在multiset中查找最接近val的值
if (it != mset.end())
{
res = min(res, abs(*it - val)); // 更新最小差值
}
if (it != mset.begin())
{
it--;
res = min(res, abs(*it - val)); // 更新最小差值
}
}
for (int i = r + 1; i <= n; i++) // 动态维护multiset，移除不再需要的子数组和
{
mset.erase(mset.find(pre[i] - pre[r]));
}
}
cout << res << endl; // 输出结果
return 0;
}
/*
输入示例：
5
10 9 8 12 14
*/本篇完。
开始没有第九第十题了。