蓝桥杯刷题——第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组

一、0握手问题 - 蓝桥云课

算法代码：

#include <iostream>
using namespace std;
int main()
{int sum=0;for(int i=49;i>=7;i--)sum+=i;cout<<sum<<endl;return 0;
}

直接暴力，题意很清晰，累加即可。 

二、0小球反弹 - 蓝桥云课

算法代码： 

#include<iostream>  // 引入输入输出流库，用于标准输入输出操作
#include<iomanip>    // 引入输入输出操纵库，用于格式化输出（如设置小数点精度）
#include<cmath>      // 引入数学函数库，用于数学运算（如平方根）using namespace std; // 使用标准命名空间，避免每次调用标准库函数时都要加std::// 定义一个函数check，用于检查两个整数a和b是否满足特定条件
bool check(int a, int b) {// 如果a能被b整除，并且a除以b的结果是偶数，则返回trueif (a % b == 0 && (a / b) % 2 == 0) return true;return false;  // 否则返回false
}// 主函数
int main() {long long x = 343720, y = 233333;  // 定义两个长整型变量x和y，并赋予初始值long long t = 1;  // 定义长整型变量t，并初始化为1long long lx, ly;  // 定义两个长整型变量lx和ly，用于存储计算过程中的临时值// 进入一个无限循环，直到满足特定条件时跳出循环while (1) {lx = 15 * t;  // 计算lx为15乘以tly = 17 * t;  // 计算ly为17乘以t// 如果lx和x满足check函数的条件，且ly和y也满足check函数的条件，则跳出循环if (check(lx, x) && check(ly, y)) break;t++;  // 否则，t自增1，继续循环}// 输出lx和ly的平方和的平方根，保留两位小数cout << setprecision(2) << fixed << sqrt(lx * lx + ly * ly);return 0;  // 程序正常结束，返回0
}

问题背景

1. 小球运动：

   • 小球在长方形内以固定的速度比 dx:dy=15:17运动。

   • 当小球碰到长方形的边框时，会发生反弹（入射角等于反射角）。

   • 我们需要计算小球第一次回到起点时所经过的总路径长度。

2. 反弹的等效路径：

   • 反弹问题可以通过“镜像反射法”简化。将长方形无限复制，形成一个网格，小球的路径可以看作一条直线穿过这些镜像长方形。

   • 小球第一次回到起点，等价于这条直线第一次穿过一个镜像长方形的左上角顶点。

---

数学分析

1. 路径条件：

   • 小球在水平方向（长）移动的总距离必须是长方形长度 x=343720 的偶数倍。这是因为每次反弹都会改变方向，只有偶数倍才能让小球回到起点的水平位置。

   • 同理，小球在垂直方向（宽）移动的总距离必须是长方形宽度 y=233333 的偶数倍。

2. 公式推导：

   • 小球在水平方向的移动距离为 lx=15t。

   • 小球在垂直方向的移动距离为 ly=17t。

   • 为了满足回到起点的条件，必须同时满足：

     lx=15t=2k⋅x（水平方向）ly=17t=2m⋅y（垂直方向）

     其中 k 和 m 是正整数。

3. 简化条件：

   • 我们需要找到最小的 t，使得 15t 是 x 的偶数倍，且 17t是 y的偶数倍。

   • 这等价于：

     

setprecision(2) 是 C++ 标准库 <iomanip> 中的一个操纵符，用于设置浮点数输出的精度。具体来说，它控制输出流中浮点数的小数点后的位数。

详细解释

• setprecision(n)：设置浮点数输出的小数点后的位数为 n。例如，setprecision(2) 表示输出浮点数时保留两位小数。

• fixed：与 setprecision 结合使用，表示使用固定小数格式输出。这意味着小数点后的位数是固定的，而不是科学计数法。

三、0好数 - 蓝桥云课 

算法代码：

#include <stdio.h>
int main()
{int n, i;scanf("%d", &n);  // 输入一个整数 nfor (; n > 0; n--)  // 从 n 开始，递减到 1{for (int m = n; m > 0;)  // 对每个数字 m = n，检查其每一位{if (m % 2 != 0) m /= 10;  // 如果最低位是奇数，去掉最低位else break;  // 如果最低位是偶数，退出循环if (m % 2 == 0) m /= 10;  // 如果新的最低位是偶数，去掉最低位else break;  // 如果新的最低位是奇数，退出循环if (m == 0) i++;  // 如果 m 变为 0，说明满足条件，计数器 i 增加}}printf("%d", i);  // 输出满足条件的数字的数量return 0;
}

        题意清晰，直接一个一个数地循环递减，然后按规则，直接判断奇数位和偶数位是不是符合条件。

四、0R 格式 - 蓝桥云课

自己写的：算法代码（只能通过50%的测试用例） 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;// 快速幂函数，计算 2^n
ll fastPow(int n) {ll a = 2;  // 底数为 2ll sum = 1;  // 初始化 sum 为 1while (n) {if (n & 1) {sum = sum * a;  // 如果当前位为 1，累乘到 sum}a = a * a;  // 底数平方n >>= 1;  // 右移一位}return sum;
}int main() {int n;double d;cin >> n >> d;  // 输入 n 和 dll ans = fastPow(n);  // 计算 2^nll end_format = round(d * ans);  // 将 d 乘以 2^n 并四舍五入//round 函数用于对浮点数进行四舍五入操作printf("%lld\n", end_format);  // 输出结果return 0;
}

 罗勇军老师的几行代码（50%）（高下立判了属于是哈哈）算法代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{    long long n;    double s;    cin>>n>>s;    long long  a = 1<<n;    long long b= (long long)(a*s*1.0+0.5);//加0.5四舍五入    cout << b;
}

题解：

#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间int main()
{int n;string d;    // 由于数字可能非常大，使用字符串来读取cin >> n >> d;  // 输入转换参数 n 和浮点数 dvector<int> b;  // 使用 vector 来存储数字的每一位，方便处理进位int sum = 0, k = 0;  // sum 用于记录总位数，k 用于记录小数点的位置// 从字符串末尾开始遍历，将字符转换为整数并存储到 vector 中for(int i = d.size() - 1; i >= 0; i--){if(d[i] != '.')b.push_back(d[i] - '0');  // 将字符转换为整数并存储else {k = sum;  // 记录小数点的位置}sum++;  // 记录总位数}int u = b.size();  // 记录当前数字的位数// 进行 n 次乘以 2 的操作while(n--){int t = 0;  // t 用于记录进位for(int i = 0; i < b.size(); i++){b[i] = b[i] * 2 + t;  // 当前位乘以 2 并加上进位if(b[i] >= 10){t = b[i] / 10;  // 计算新的进位b[i] = b[i] % 10;  // 取余数作为当前位的值}else {t = 0;  // 如果没有进位，置为 0}}if(t)  // 如果最后还有进位，添加到 vector 中b.push_back(t);}u = b.size();  // 更新数字的位数int t = 1;  // 用于处理四舍五入的进位if(k && b[k - 1] >= 5)  // 如果需要四舍五入{for(int i = k; i < u; i++){b[i] = b[i] + 1;  // 当前位加 1if(b[i] <= 9) {  // 如果不需要继续进位t = 0;break;}else {b[i] -= 10;  // 如果需要继续进位}}if(t)  // 如果最后还有进位，添加到 vector 中b.push_back(t);}// 从最高位开始输出结果，忽略小数部分for(int i = b.size() - 1; i >= k; i--)cout << b[i];return 0;  // 程序结束
}

1. 输入处理

• 输入：读取整数 n 和浮点数 d。

  • n 是转换参数，表示需要将浮点数乘以 2^n。

  • d 是待转换的浮点数，可能非常大，因此用字符串存储。

• 目标：将浮点数 d 转换为整数形式，方便后续计算。

---

2. 将浮点数转换为整数形式

• 遍历浮点数字符串：

  • 从字符串末尾开始遍历，将每个数字字符转换为整数，并存储到 vector<int> b 中。

  • 如果遇到小数点 .，记录小数点的位置 k，表示小数点后有 k 位。

• 结果：

  • b 中存储的是浮点数 d 的整数形式（去掉小数点）。

  • k 记录了小数点的位置，用于后续四舍五入。

---

3. 高精度乘以 2^n

• 循环乘以 2：

  • 进行 n 次乘以 2 的操作，每次操作都模拟高精度乘法。

  • 每次乘以 2 时，遍历 b 中的每一位，计算当前位乘以 2 并加上进位。

  • 如果当前位的结果大于等于 10，则计算进位，并将当前位的结果取余。

  • 如果最后还有进位，将其添加到 b 的末尾。

• 结果：

  • b 中存储的是浮点数 d 乘以 2^n的结果，仍然是一个高精度整数。

---

4. 四舍五入

• 判断是否需要四舍五入：

  • 根据小数点的位置 k，检查小数点后的第一位（即 b[k-1]）是否大于等于 5。

  • 如果大于等于 5，则需要进行四舍五入。

• 四舍五入操作：

  • 从小数点位置开始，向高位逐位加 1，直到没有进位为止。

  • 如果最高位仍有进位，将其添加到 b 的末尾。

• 结果：

  • b 中存储的是四舍五入后的最终结果。

---

5. 输出结果

• 从最高位开始输出：

  • 从 b 的最高位开始，输出每一位数字。

  • 忽略小数部分（即小数点后的位数）。

• 结果：

  • 输出的是浮点数 d 乘以 2^n 并四舍五入后的整数结果。

---

6. 代码的核心思想

• 高精度计算：

  • 由于浮点数和 2^n 可能非常大，普通数据类型无法存储，因此使用字符串和 vector<int> 来模拟高精度计算。

• 逐位处理：

  • 通过逐位遍历和进位处理，实现了高精度乘法和四舍五入。

• 四舍五入：

  • 根据小数点后的第一位决定是否需要进位，模拟了四舍五入的过程。

五、 0宝石组合 - 蓝桥云课

（这道题我只会暴力，而且没拿到该拿的分，别提了，都是泪）

牛逼的题解：

#include <bits/stdc++.h>  // 包含所有标准库头文件#define N 500010  // 定义常量 N，表示数组的最大大小int gem[N], num[N];  // 定义两个数组：gem 用于存储输入的宝石编号，num 用于统计每种宝石的数量int main() {int n;scanf("%d", &n);  // 输入整数 n，表示宝石的数量int max = -0x3f3f3f3f;  // 初始化 max 为一个很小的值，用于记录宝石编号的最大值for (int i = 0; i < n; i++) {scanf("%d", &gem[i]);  // 输入每个宝石的编号num[gem[i]]++;  // 统计每种宝石的数量if (gem[i] > max) max = gem[i];  // 更新宝石编号的最大值}// 从最大值开始，尝试找到满足条件的三个宝石for (int i = max; i >= 1; i--) {  // i 是可能的公因数int tmp[3], pos = 0;  // tmp 用于存储符合条件的宝石编号，pos 用于记录 tmp 中的位置int cnt = 0;  // cnt 用于统计符合条件的宝石数量// 遍历所有 i 的倍数，检查是否存在对应的宝石for (int j = i; j <= max; j += i) {  // j 是 i 的倍数if (num[j]) {  // 如果宝石 j 存在cnt += num[j];  // 统计宝石 j 的数量for (int k = 0; k < num[j] && pos < 3; k++) {  // 将宝石 j 加入 tmptmp[pos++] = j;}}if (cnt == 3) break;  // 如果找到三个宝石，跳出循环}// 如果找到三个宝石，输出结果并结束程序if (cnt == 3) {for (int j = 0; j < 3; j++) {printf("%d ", tmp[j]);  // 输出三个宝石的编号}break;  // 结束程序}}return 0;  // 程序结束
}

代码思路： 

六、0数字接龙 - 蓝桥云课 

题解代码：

#include <bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;const int N = 11; // 定义棋盘的最大大小为11×11
int n, k; // n为棋盘大小，k为数字循环的范围
int g[N][N]; // 存储棋盘上的数字
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // 定义8个方向的x坐标偏移
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; // 定义8个方向的y坐标偏移
string path; // 存储路径的方向编号
bool st[N][N]; // 标记棋盘上的格子是否被访问过
bool edge[N][N][N][N]; // 检查路径是否交叉// 深度优先搜索函数，用于寻找路径
bool dfs(int a, int b) {// 如果到达右下角格子，检查路径长度是否为n*n-1（因为起点不计入路径）if (a == n - 1 && b == n - 1)return path.size() == n * n - 1;st[a][b] = true; // 标记当前格子已访问for (int i = 0; i < 8; i++) { // 遍历8个方向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; // 如果所有方向都无法到达终点，返回false
}int main() {cin >> n >> k; // 输入棋盘大小和数字循环范围for (int i = 0; i < n; i++) // 读取棋盘上的数字for (int j = 0; j < n; j++)cin >> g[i][j];// 从起点(0,0)开始搜索路径if (!dfs(0, 0))cout << -1 << endl; // 如果没有找到路径，输出-1elsecout << path << endl; // 输出路径的方向编号序列return 0;
}

罗勇军老师的分析：（有道理）

 

七、0拔河 - 蓝桥云课

算法代码（20%暴力枚举） 

//20%：暴力枚举
#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间const int N = 1e3 + 100;  // 定义常量 N，表示数组的最大大小
typedef long long ll;     // 定义 long long 类型的别名 ll
ll a[100];                // 定义数组 a，用于存储输入的数字// 计算子数组和的函数
ll sum(int l, int r) {ll s = 0;             // 初始化子数组和为 0for (int i = l; i <= r; i++)  // 遍历子数组的每个元素s += a[i];        // 累加子数组的元素return s;             // 返回子数组的和
}int main() {int n;                // 定义整数 n，表示数组的大小cin >> n;             // 输入数组的大小 nfor (int i = 1; i <= n; i++)  // 遍历数组的每个位置cin >> a[i];       // 输入数组的每个元素ll ans = 1e12;         // 初始化答案为一个大值（1e12），用于存储最小绝对差// 暴力枚举所有可能的子数组对for (int l1 = 1; l1 <= n; l1++) {        // 枚举第一个子数组的起始位置 l1for (int r1 = l1; r1 <= n; r1++) {    // 枚举第一个子数组的结束位置 r1for (int l2 = r1 + 1; l2 <= n; l2++) {  // 枚举第二个子数组的起始位置 l2for (int r2 = l2; r2 <= n; r2++) {  // 枚举第二个子数组的结束位置 r2// 计算两个子数组和的绝对差，并更新最小值ans = min(ans, abs(sum(l2, r2) - sum(l1, r1)));}}}}cout << ans;           // 输出最小绝对差return 0;              // 程序结束
}

 算法代码（40%暴力枚举+前缀和优化） 

#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间const int N = 1e3 + 100;  // 定义常量 N，表示数组的最大大小
typedef long long ll;     // 定义 long long 类型的别名 ll
ll a[N], prefix[N];       // 定义数组 a 和前缀和数组 prefix// 计算子数组和的函数
ll sum(int l, int r) {return prefix[r] - prefix[l - 1];  // 返回子数组 [l, r] 的和
}int main() {int n;                // 定义整数 n，表示数组的大小cin >> n;             // 输入数组的大小 n// 读取数组并计算前缀和for (int i = 1; i <= n; i++) {cin >> a[i];                // 输入数组的每个元素prefix[i] = prefix[i - 1] + a[i];  // 计算前缀和}ll ans = 1e12;         // 初始化答案为一个大值（1e12），用于存储最小绝对差// 枚举所有子数组对for (int l1 = 1; l1 <= n; l1++) {        // 枚举第一个子数组的起始位置 l1for (int r1 = l1; r1 <= n; r1++) {    // 枚举第一个子数组的结束位置 r1ll sum1 = sum(l1, r1);             // 计算第一个子数组的和for (int l2 = r1 + 1; l2 <= n; l2++) {  // 枚举第二个子数组的起始位置 l2for (int r2 = l2; r2 <= n; r2++) {  // 枚举第二个子数组的结束位置 r2ll sum2 = sum(l2, r2);           // 计算第二个子数组的和ans = min(ans, abs(sum2 - sum1));  // 更新最小绝对差}}}}cout << ans;           // 输出最小绝对差return 0;              // 程序结束
}

逆天题解：（真的想不出来，我是个只会暴力的fw）

#include<bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;     // 使用标准命名空间const int N = 1e3 + 10;  // 定义常量 N，表示数组的最大大小
long long a[N];          // 定义数组 a，用于存储前缀和
int n;                   // 定义整数 n，表示数组的大小
multiset<long long> s;   // 定义 multiset，用于存储所有可能的子数组和// 自定义函数，返回两个数中的较小值
long long minn(long long a, long long b) {if (a < b) return a;else return b;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  // 取消同步流，加速输入输出cin >> n;  // 输入数组的大小 n// 读取数组并构造前缀和for (int i = 1; i <= n; i++) {cin >> a[i];a[i] += a[i - 1];  // 计算前缀和}// 枚举所有可能的子数组和，并将其插入 multisetfor (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {s.insert(a[j] - a[i - 1]);  // 计算子数组 [i, j] 的和，并插入 multiset}}long long res = 1e9;  // 初始化结果为一个大值（1e9），用于存储最小绝对差// 遍历所有可能的第一个区间的右端点 ifor (int i = 1; i < n; i++) {// 删除以 i 作为右端点的所有子数组和for (int j = i; j <= n; j++) {auto k = a[j] - a[i - 1];  // 计算子数组 [i, j] 的和s.erase(s.find(k));        // 从 multiset 中删除该和}// 遍历所有可能的第一个区间的左端点 jfor (int j = 1; j <= i; j++) {auto k = a[i] - a[j - 1];  // 计算第一个子数组 [j, i] 的和// 在 multiset 中查找最接近 k 的值auto p = s.lower_bound(k);  // 找到第一个 >= k 的值if (p != s.end()) {res = minn(res, abs(*p - k));  // 更新最小绝对差}if (p != s.begin()) {p--;  // 找到第一个 < k 的值res = minn(res, abs(*p - k));  // 更新最小绝对差}}}cout << res << endl;  // 输出最小绝对差return 0;             // 程序结束
}