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

发布于:2025-03-16 ⋅ 阅读:(18) ⋅ 点赞:(0)

一、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的结果是偶数,则返回true
    if (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,并初始化为1
    long long lx, ly;  // 定义两个长整型变量lx和ly,用于存储计算过程中的临时值

    // 进入一个无限循环,直到满足特定条件时跳出循环
    while (1) {
        lx = 15 * t;  // 计算lx为15乘以t
        ly = 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);  // 输入一个整数 n
    for (; 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;  // 底数为 2
    ll sum = 1;  // 初始化 sum 为 1
    while (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 和 d
    ll ans = fastPow(n);  // 计算 2^n
    ll 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 和浮点数 d

  vector<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;  // 当前位加 1
        if(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 加入 tmp
                    tmp[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; // 如果没有找到路径,输出-1
    else
        cout << 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;             // 初始化子数组和为 0
    for (int i = l; i <= r; i++)  // 遍历子数组的每个元素
        s += a[i];        // 累加子数组的元素
    return s;             // 返回子数组的和
}

int main() {
    int n;                // 定义整数 n,表示数组的大小
    cin >> n;             // 输入数组的大小 n

    for (int i = 1; i <= n; i++)  // 遍历数组的每个位置
        cin >> a[i];       // 输入数组的每个元素

    ll ans = 1e12;         // 初始化答案为一个大值(1e12),用于存储最小绝对差

    // 暴力枚举所有可能的子数组对
    for (int l1 = 1; l1 <= n; l1++) {        // 枚举第一个子数组的起始位置 l1
        for (int r1 = l1; r1 <= n; r1++) {    // 枚举第一个子数组的结束位置 r1
            for (int l2 = r1 + 1; l2 <= n; l2++) {  // 枚举第二个子数组的起始位置 l2
                for (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++) {        // 枚举第一个子数组的起始位置 l1
        for (int r1 = l1; r1 <= n; r1++) {    // 枚举第一个子数组的结束位置 r1
            ll sum1 = sum(l1, r1);             // 计算第一个子数组的和
            for (int l2 = r1 + 1; l2 <= n; l2++) {  // 枚举第二个子数组的起始位置 l2
                for (int r2 = l2; r2 <= n; r2++) {  // 枚举第二个子数组的结束位置 r2
                    ll 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];  // 计算前缀和
    }

    // 枚举所有可能的子数组和,并将其插入 multiset
    for (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),用于存储最小绝对差

    // 遍历所有可能的第一个区间的右端点 i
    for (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 中删除该和
        }

        // 遍历所有可能的第一个区间的左端点 j
        for (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;             // 程序结束
}