当前位置：首页 > news >正文

蓝桥杯训练题目（一）—— 难度：简单（除了最后一题哈）

news 2025/2/24 5:24:49

一、1.奇怪的捐赠 - 蓝桥云课

方法一：算法代码（位权法）

问题回顾

7进制转换的思路

为什么“最多分成5份”没有显式使用

验证

方法二：算法代码（暴力）

二、2.ASC - 蓝桥云课

算法代码：

三、3.裁纸刀 - 蓝桥云课

算法代码：

四、4.班级活动 - 蓝桥云课

算法代码：

统计每个 id 出现的次数

计算需要更改的次数

判断并输出结果

五、5.握手问题 - 蓝桥云课

算法代码：

六、6.好数 - 蓝桥云课

算法代码：

代码的逻辑

七、 7.回文字符串 - 蓝桥云课

算法代码：

代码思路分析：

函数 canFormPalindrome

主函数 main

八、8.纯职业小组 - 蓝桥云课

算法代码：

代码整体思路

输入数据处理

使用哈希表存储数对

统计结果

处理目标人数 k

输出结果

整体流程示意

输入阶段

数据存储

结果计算

目标人数处理

输出阶段

一、1.奇怪的捐赠 - 蓝桥云课

方法一：算法代码（位权法）

#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{int a = 0, b = 1000000;while (b) {a += b % 7;b /= 7;}printf("%d", a);return 0;
}

问题回顾

金额的表示：每份金额必须是7的幂次方，即1万元（7^0）、7万元（7^1）、49万元（7^2）、343万元（7^3）等。
数量限制：每份金额的数量不能超过5份。
目标：在满足上述条件的情况下，最大化份数。

7进制转换的思路

将100万元转换为7进制数的思路是基于每份金额必须是7的幂次方。7进制数的每一位代表对应幂次方的金额的份数。例如，7进制数的第0位代表1万元的份数，第1位代表7万元的份数，依此类推。

为什么“最多分成5份”没有显式使用

在7进制转换的方法中，每一位的数字表示对应金额的份数。由于7进制数的每一位数字范围是0到6，而题目要求每份金额的数量不能超过5份，因此：

如果某一位的数字小于或等于5，那么它直接满足条件。
如果某一位的数字等于6，那么它超过了5份的限制。

然而，在实际的7进制转换中，100万元转换为7进制数后，各位数字都不会超过5。这是因为100万元在7进制下的表示不会产生任何一位为6的情况。因此，在这种情况下，“最多分成5份”的条件自动被满足，不需要额外的处理。

验证

让我们再次验证100万元在7进制下的表示：

1000000 ÷ 7 = 142857 余 1
142857 ÷ 7 = 20408 余 1
20408 ÷ 7 = 2915 余 3
2915 ÷ 7 = 416 余 3
416 ÷ 7 = 59 余 3
59 ÷ 7 = 8 余 3
8 ÷ 7 = 1 余 1
1 ÷ 7 = 0 余 1

7进制数为：1 1 3 3 3 3 1 1

各位数字分别为1, 1, 3, 3, 3, 3, 1, 1，都小于或等于5，因此满足“最多分成5份”的条件。

方法二：算法代码（暴力）

#include <iostream>
using namespace std;long n = 1000000;int k = 1;int a =7;int b =49;int c =343;int d = 2401;int e =16807;int f = 117649;int g = 823543;int num = 0;
int main()
{for(int h = 1;h<=5;h++)for(int q =1;q<=5;q++)for(int w=1;w<=5;w++)for(int r =1;r<=5;r++)for(int t =1;t<=5;t++)for(int y =1;y<=5;y++)for(int u =1;u<=5;u++)for(int i =1;i<=5;i++)if((h*k+a*q+b*w+c*r+d*t+e*y+f*u+g*i)==n){num =h+q+w+r+t+y+u+i;cout<<num;break;}return 0;
}

二、2.ASC - 蓝桥云课

算法代码：

#include <iostream>
using namespace std;
int main()
{printf("%d",'L');return 0;
}

我只能说，蓝桥杯旱的旱死涝的涝死。。。

三、3.裁纸刀 - 蓝桥云课

算法代码：

#include <iostream>
using namespace std;
int main()
{int s;s=440+4-1;cout<<s;// 请在此输入您的代码return 0;
}

找规律，一个二维码是0+外围4刀，两个是1+4，四个是3+4，六个是5+4

四、4.班级活动 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
int n, id;
unordered_map<int,int> mp;
int main(){cin >> n;for(int i = 1; i <= n; ++i){cin >> id;mp[id]++;}int cnt1 = 0, cnt2 = 0;for(auto &pair : mp){if(pair.second == 1) cnt1++; // 只出现1次的元素数量else cnt2 += pair.second - 2; // 出现多次的元素数量的多余总数(-2是因为俩俩配对，每个元素-2剩下的就是多余的)}if(cnt1 > cnt2) cout << (cnt1 + cnt2) / 2 << '\n';//容易的理解是cnt2+(cnt1-cnt2)/2 也就是(cnt1 + cnt2) / 2//先把能用的cnt2全用上 剩余的(cnt1-cnt2)再自己俩俩配对else cout << cnt2 << '\n';//cnt2不仅够用 还多出来了 多出来的cnt2也得处理 每个数字都得改成新的（因为已经多出来了） 所以总共就是cnt2return 0;
}

统计每个 id 出现的次数
- 使用 unordered_map<int, int> mp 来记录每个 id 出现的次数。
- 通过 mp[id]++ 来统计每个 id 出现的次数。
计算需要更改的次数
- cnt1 用于记录出现次数为 1 的 id 的数量。
- cnt2 用于记录出现次数大于 2 的 id 的多余次数（即 pair.second - 2）。
判断并输出结果
- 如果 cnt1 > cnt2，表示需要将一些出现次数为 1 的 id 更改为其他 id，使得它们能够匹配。此时，最少需要更改 (cnt1 + cnt2) / 2 次。
- 否则，只需要更改 cnt2 次，将多余的次数减少到 2 次。

五、5.握手问题 - 蓝桥云课

算法代码：

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

对于第一个人来说，除了自己以外要跟其他49人握手，所以第一个是49次；
对于第二个人来说，第一个人主动跟我握手了，有一次不算，所以第二个是48次；
以此类推......第43个人就是7次。到了最后七个人呢，因为互相都没有握手，并且7个人都被前面的人握过手了，所以都是0次。所以从7开始求和到49即可得到总的握手次数。

六、6.好数 - 蓝桥云课

算法代码：

#include <stdio.h>
int main()
{int n, i=0;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;
}

代码的逻辑

外层循环：从 n 开始，递减到 1，遍历每个数字。
内层循环：对每个数字 m，检查其每一位是否满足交替奇偶的条件。
- 如果最低位是奇数，去掉最低位。
- 如果新的最低位是偶数，去掉最低位。
- 重复上述步骤，直到 m 变为 0。
- 如果 m 变为 0，说明该数字满足条件，计数器 i 增加。

七、 7.回文字符串 - 蓝桥云课

算法代码：

#include <iostream>
#include <string>
using namespace std;bool canFormPalindrome(const string& S) {int left = 0, right = S.length() - 1;while (left <= right) {if (S[left] == S[right]) {// 字符匹配，继续向中间移动left++;right--;} else if (S[right] == 'l' || S[right] == 'q' || S[right] == 'b') {// 如果右端字符是 l、q、b，可以通过在开头添加字符来匹配right--;} else {// 无法匹配，返回 falsereturn false;}}return true;
}int main() {int T;cin >> T;while (T--) {string S;cin >> S;if (canFormPalindrome(S)) {cout << "Yes" << endl;} else {cout << "No" << endl;}}return 0;
}

代码思路分析：

函数 canFormPalindrome
- 该函数接受一个字符串 S 作为参数，返回一个布尔值，表示是否可以通过在开头添加字符来形成回文串。
- 使用两个指针 left 和 right，分别指向字符串的开头和结尾。
- 在 while 循环中，比较 left 和 right 指针所指向的字符：
  - 如果字符匹配，则继续向中间移动指针。
  - 如果字符不匹配，且 right 指针指向的字符是 'l'、'q' 或 'b'，则可以通过在开头添加字符来匹配，因此只移动 right 指针。
  - 如果字符不匹配且不满足上述条件，则返回 false，表示无法形成回文串。
- 如果循环结束后所有字符都匹配，则返回 true。
主函数 main
- 首先读取测试用例的数量 T。
- 对于每个测试用例，读取字符串 S，并调用 canFormPalindrome 函数进行判断。
- 根据函数返回的结果输出 "Yes" 或 "No"。

八、8.纯职业小组 - 蓝桥云课

算法代码：

#include <iostream>
#include <unordered_map>
using namespace std;long long T, n, k; // 定义全局变量 T（测试用例数量）、n（数对数量）、k（目标人数）int main() {cin >> T; // 读取测试用例的数量while (T--) { // 对于每个测试用例重复以下操作cin >> n >> k; // 读取当前测试用例中的 n 和 k--k; // 将 k 减 1，可能是为了处理后续逻辑中的索引unordered_map<int, int> arr; // 使用哈希表来存储每个数 a 对应的总和 bint a, b; // 声明变量 a 和 b// 读取 n 个数对并更新哈希表for (int i = 0; i < n; ++i) {cin >> a >> b; // 读取一对数 (a, b)arr[a] += b; // 将 b 加到对应的 a 的总和中}long long ret = 0; // 初始化结果变量为 0long long hash[4] = {0}; // 初始化一个大小为 4 的数组，用于存储不同余数的计数（0 到 3）// 遍历哈希表 arr，处理数对的总和并更新结果和 hash 数组for (auto &e : arr) {int b = e.second; // 获取当前数对的 b 值if (b < 3) {ret += b; // 如果 b 小于 3，直接累加到结果中} else {ret += 2; // 如果 b 大于等于 3，则结果加 2b -= 2; // 减去 2hash[3] += b / 3; // 计算 b 的完整三组数，并更新 hash[3]++hash[b % 3]; // 更新 hash 数组，记录 b 的余数}}// 处理 hash 数组，根据 k 的值计算结果for (int i = 3; i > 0; --i) { // 从大到小遍历 hash 数组if (hash[i] < k) { // 如果当前哈希值小于 kret += i * hash[i]; // 将当前 i 乘以 hash[i] 加到结果中hash[i] = 0; // 清空当前 hash[i]} else {ret += i * k; // 如果 hash[i] 大于等于 k, 将 i 乘以 k 加到结果中k = 0; // 将 k 设置为 0，表示目标人数已满足break; // 退出循环}}// 检查是否满足条件并输出结果if (k == 0 && hash[3] + hash[2] + hash[1] > 0) { cout << ret + 1 << endl; // 如果 k 为 0 且 hash 中仍有剩余，输出 ret + 1} else {cout << -1 << endl; // 否则输出 -1，表示无法满足条件}}return 0; // 正常结束程序
}

代码整体思路

输入数据处理
- 首先，读取测试用例的数量 T。对于每个测试用例，接下来要读取两个整数 n（数对的数量）和 k（目标人数）。
- 将 k 减 1，以便后续逻辑处理时减少一个人数的计算。这通常是为了考虑后续的逻辑处理，使得在满足条件的情况下能够方便地计算。
使用哈希表存储数对
- 使用 unordered_map 来存储每个数 a 及其对应的总和 b。这使得可以动态地将相同的 a 值的 b 值累加，而不需要固定大小的数组。
- 读取 n 个数对 (a, b)，并通过 arr[a] += b 的方式将每个 b 值加到对应的 a 上。
统计结果
- 初始化结果变量 ret 为 0，用于存储最终的返回结果。
- 初始化一个大小为 4 的数组 hash，用于存储不同余数（0 到 3）的计数。
- 遍历哈希表 arr 中的每个元素，处理每个 b 值：
  - 如果 b < 3，直接将 b 加到 ret。
  - 如果 b >= 3，则将结果加 2（表示在处理过程中可以形成的基本结构），然后计算 b 中包含的完整三组数，并更新余数计数。
处理目标人数 k
- 通过遍历 hash 数组，从大到小处理：
  - 如果 hash[i] < k，则将全部的 hash[i] 乘以 i 加到结果中，并减少 k。需要注意，这一行代码中的 k -= hash[i]; 应该是对 k 的最终值进行更新。
  - 如果 hash[i] >= k，则将 k 乘以 i 加到结果中，并设置 k 为 0，表示目标人数已经满足。
输出结果
- 在最后的条件判断中，检查如果 k 为 0 且 hash[3] + hash[2] + hash[1] > 0（即还有剩余的数对），则输出 ret + 1；否则输出 -1，表示无法满足条件。