第十五届蓝桥杯赛后复盘(本人个人做法)
目录
试题A 握手问题
试题B： 小球反弹
试题C： 好数
试题D ：R格式
试题E：宝石组合
试题F：数字接龙
试题G：爬山
试题H：拔河
试题A 握手问题（本题总分：5分）
【问题描述】
小蓝组织了一场算法交流会议，总共有50人参加了本次会议。在会议上,大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进,行一次握手（且仅有一次）。但有7个人，这7人彼此之间没有进行握手（但,这7人与除这7人以外的所有人进行了握手）。请问这些人之间一共进行了多,少次握手?
注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1024
#include<iostream>//A握手问题using namespace std;int fact(int n)//用递归{if (n == 0)return 0;return n + fact(n - 1);}int main(){int a7 = 43 * 7;//这7个人之间没有相互握手，但和其他43个人都有握手int a43;a43 = fact(42);//第8个人还要和和42个人握手，第9个人还要和和41个人握手......cout << a7 + a43 << endl;//两者相加return 0;}试题B： 小球反弹(本题总分：5分)
【问题描述】
有一长方形，长为343720 单位长度，宽为 233333 单位长度。在其内部左,上角顶点有一小球（无视其体积)，其初速度如图所示且保持运动速率不变，分,解到长宽两个方向上的速率之比为 dx：dy = 15：17。小球碰到长方形的边框时,会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速,率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第,一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍,五入保留两位小数。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一,个小数，在提交答案时只填写这个小数，填写多余的内容将无法得分。
1100325199.77
#include<iostream>#include<cmath>#include <iomanip>using namespace std;typedef long long ll;const ll w = 343720;const ll h = 233333;int main(){//因为当最后小球返回到起始位置时，小球的dx分量和dy分量都是343720和233333的偶数倍//由此就可以算出其总路程for (ll i = 2;i<10000;i += 2){for (ll j = 2;j < 10000;j += 2){if (i * w * 17 == j * h * 15){cout << setiosflags(ios::fixed) << setprecision(2) << sqrt(((i * w) * (i * w) + (j * h) * (j * h))) << endl;//如果setprecision(n)与setiosflags(ios::fixed)合用，可以控制小数点右边的数字个数goto it;}}}it:return 0;}试题C： 好数（本题总分：10分）
【问题描述】
一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位·-·）上的数字是奇数，偶数位（十位、千位、十万位··）上的数字是偶数，我们就称,之为“好数”。给定一个正整数N，请计算从1到N一共有多少个好数。
【输入格式】一个整数N。
【输出格式】一个整数代表答案。
【样例输入1】
24
【样例输出1】
7
【样例输入2】
2024
【样例输出2】
150
【样例说明】
对于第一个样例，24以内的好数有1、3、5、7、9、21、23，一共7个。
【评测用例规模与约定】
对于10%的评测用例，1≤N≤100。,对于100%的评测用例，1≤N≤107。
#include<iostream>using namespace std;bool isoddnumber(int n){int p = 1;while (n){if ((n % 10 == 0 || n % 10 == 2 || n % 10 == 4 || n % 10 == 6 || n % 10 == 8) && p % 2 != 0){return false;}p++;n /= 10;}return true;}bool isevennumber(int n){int p = 1;while (n){if ((n % 10 == 1 || n % 10 == 3 || n % 10 == 5 || n % 10 == 7 || n % 10 == 9) && p % 2 == 0){return false;}p++;n /= 10;}return true;}int main(){int N;int ans = 0;cin >> N;for (int i = 1;i <= N;i++){if (isoddnumber(i) && isevennumber(i)){ans++;}}cout << ans << endl;return 0;}试题D ：R格式（本题总分：10分）
【问题描述】
小蓝最近在研究一种浮点数的表示方法：R格式。对于一个大于0的浮点数d，可以用 R格式的整数来表示。给定一个转换参数n，将浮点数转换为R格式整数的做法是：
1.将浮点数乘以2^n；
2.四舍五入到最接近的整数。
【输入格式】
一行输入一个整数n和一个浮点数d，分别表示转换参数和待转换的浮点数。
【输出格式】
输出一行表示答案：d用R格式表示出来的值。
【样例输入】
2 3.14
【样例输出】
13
【样例说明】
3.14×2^2=12.56，四舍五入后为13。
【评测用例规模与约定】
对于50%的评测用例：1≤n≤10，1≤将d视为字符串时的长度≤15。
对于100% 的评测用例：1≤n≤1000，1≤将d视为字符串时的长度≤1024；保证d是小数，即包含小数点。
#include<iostream>using namespace std;int square(int n){int ans = 1;for (int i = 1;i <= n;i++){ans *= 2;}return ans;}int isjia1(double s){int s5 = s;double s6 = s - s5;if (s6 >= 0.5)return s5 + 1; return s5;}int main(){double s1;double s2;double s3;cin >> s1 >> s2;s3 = s2 * square(s1);cout << isjia1(s3) << endl;return 0;}试题E：宝石组合（本题总分：15分）
【问题描述】
在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的“闪亮度”属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了N枚宝石，第i枚宝石的“闪亮度”属性值为H，小蓝将会从这N枚宝石中选出三枚进行组合，组合之后的精美程度S可以用以下公式来衡量：
其中LCM表示的是最小公倍数函数。
小蓝想要使得三枚宝石组合后的精美程度S尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案S值相同，优先选择按照H值升序排列后字典序最小的方案。
【输入格式】
第一行包含一个整数N表示宝石个数。
第二行包含N个整数表示N个宝石的“闪亮度”。
【输出格式】
输出一行包含三个整数表示满足条件的三枚宝石的“闪亮度”。
【样例输入】5
1 2 3 4 9
【样例输出】
1 2 3
【评测用例规模与约定】
对于30%的评测用例：3≤N≤100，1≤H≤1000。
对于60%的评测用例：3≤N≤2000。
对于100%的评测用例：3≤N≤10，1≤H≤10
#include<iostream>#include<map>#include<algorithm>using namespace std;const int N = 1e5 + 10;int h[N];struct des {int x, y, z;bool operator<(const des& a)const{if (x != a.x)return x < a.x;if (y != a.y)return y < a.y;return z < a.z;}};map<des, double> s;int gcd(int a, int b){if (b == 0)return a;return gcd(b, a % b);}int lcm(int a, int b){if (b == 0)return 0;return a * b / gcd(a, b);}int main(){int n;cin >> n;for (int i = 0; i < n; i++)cin >> h[i];sort(h, h + n);double maxs = 0;do {int temp[3];temp[0] = h[0];temp[1] = h[1];temp[2] = h[2];sort(temp, temp + 3);s[{temp[0], temp[1], temp[2]}] = temp[0] * temp[1] * temp[2] * lcm(lcm(temp[0], temp[1]), temp[2]) / (lcm(temp[0], temp[1]) * lcm(temp[2], temp[1]) * lcm(temp[0], temp[2]));maxs = max(maxs, s[{temp[0], temp[1], temp[2]}]);} while (next_permutation(h, h + n));auto it = s.begin();for (; it != s.end(); it++){if (it->second == maxs){cout << it->first.x << ' ' << it->first.y << ' ' << it->first.z << endl;break;}}return 0;}试题F：数字接龙（本题总分：15分）
【问题描述】
小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为N×N的格子棋盘上展开，其中每一个格子处都有着一个0...K-1之间的整数。游戏规则如下：
1.从左上角（0,0）处出发，目标是到达右下角（N－1,N－1）处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
2.对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0,1,2,...,K-1,0,1,2,...,K-1,0,1,2...。
3.途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
4.路径中不可以出现交叉的线路。例如之前有从(0,0）移动到(1,1)，那么再从（1,0）移动到（0,1）线路就会交叉。
为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2所示；因此行进路径可以用一个包含0...7之间的数字字符串表示，如下图1是一个迷宫示例，它所对应的答案就是：41255214。
现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出-1。
略（dfs)
试题G：爬山（本题总分：20分）
【问题描述】
小明这天在参加公司团建，团建项目是爬山。在x轴上从左到右一共有n座山，第i座山的高度为h[i]。他们需要从左到右依次爬过所有的山，需要花费的体力值为S=∑h[i]。然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为H的山的高度变为√H，可以使用P次；第二种魔法可以将高度为H的山的高度变为⌊H/2⌋，可以使用Q次。并且对于每座山可以按任意顺序多次释放这两种魔法。
小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少？【输入格式】
输入共两行。
第一行为三个整数n，P，Q。
第二行为n个整数h[1]，h[2]，…，h[n]。【输出格式】
输出共一行，一个整数代表答案。【样例输入】
4 1 1
4 5 6 49【样例输出】
18【样例说明】
将第四座山变为⌊√49⌋=7，然后再将第四座山变为⌊7/2⌋=3。体力值为4+5+6+3=18。
【评测用例规模与约定】
对于20%的评测用例，保证n≤8，P=0。
对于100%的评测用例，保证n≤100000，0≤P≤n，0≤Q≤n,,0≤h≤100000。
试题G的思路是（个人思路）：先排序，从小到大，然后给最大的数用魔法，看看两种模式哪个用了更小，当前数变成用了魔法后的值，然后当前数再与第二大的数比较大小，如果还是最大的话就继续用魔法，值得当前数的值小于第二大的数或者魔法次数用光，然后继续循环下去，给后面的数使用魔法，如果所有数都用了魔法但是魔法次数还有剩余的话就继续重复这一过程使得用尽魔法次数
#include<iostream>#include<cmath>#include<vector>#include<algorithm>using namespace std;vector<int>app;int onefit(int n){int ans = sqrt(n);return ans;}int twofit(int n){int ans = n / 2;return ans;}int overcome(int n,int p,int q){sort(app.begin(), app.end());int max = app[n - 1];if (onefit(max) > twofit(max)&&q>0){app[n - 1] = twofit(max);q--;return overcome(n, p, q);}else if (onefit(max) <= twofit(max)&&p>0){app[n - 1] = onefit(max);p--;return overcome(n, p, q);}else if (p == 0&&q!=0){app[n - 1] = twofit(max);q--;return overcome(n, p, q);}else if (p != 0 && q == 0){app[n - 1] = onefit(max);p--;return overcome(n, p, q);}else if(q==0&&p==0){int ans = 0;for (int i = 0;i < n;i++){ans += app[i];}return ans;}}int main(){int n, p, q;cin >> n >> p >> q;cout << endl;for (int i = 0;i < n;i++){int b;cin >> b;app.push_back(b);}cout << overcome(n,p, q) << endl;return 0;}试题H：拔河（本题总分：20分）
【问题描述】
小明是学校里的一名老师，他带的班级共有n名同学，第i名同学力量值为d。在闲暇之余，小明决定在班级里组织一场拔河比赛。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。
【输入格式】
输入共两行。
第一行为一个正整数 n。
第二行为n个正整数ai;
【输出格式】
输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。
【样例输入】
5
10 9 8 12 14
【样例输出】
1
【样例说明】
其中一种最优选择方式：
队伍1：{a1,a2,a3}，队伍 2：{a4,a5}，力量值和分别为10+9+8=27，12+14=26,差距为|27-26|=1。
【评测用例规模与约定】
对于 20%的评测用例，保证n≤ 50。
对于100%的评测用例，保证n≤10^3，ai≤10^9。
试题H的思路是（个人思路）：分为3个数组，一个是装原数组，另一个是队伍1数组，最后一个是队伍2数组；其中刚开始原数组的首位元素加入到队伍1数组，原数组的末端元素加入到队伍2数组；接下来开始判断队伍1力量总和和队伍2力量总和谁大，如果队伍1数组更大，则将原数组逆向加入到队伍2数组；反之，则正向加入到队伍1数组.........最后直到原数组的元素全部分配到队伍1数组和队伍2数组，这个时候，就可以计算出队伍1数组的所有元素之和和队伍2数组所有元素之和的差的绝对值
#include<iostream>#include<vector>#include<cmath>using namespace std;int forceleft(vector<int>arrleft)//计算左侧队伍的力量值总和{int leftnums = 0;for (int i = 0;i < arrleft.size();i++){leftnums += arrleft[i];}return leftnums;}int forceright(vector<int>arrright)//计算右侧队伍的力量值总和{int rightnums = 0;for (int i = 0;i < arrright.size();i++){rightnums += arrright[i];}return rightnums;}int forcediffence(vector<int>arrleft,vector<int>arrright)//这个函数计算两个队伍力量值总和的差异{return abs(forceleft(arrleft) - forceright(arrright));}int force(vector<int>arr)//force函数是核心函数，它试图平衡左侧和右侧队伍的力量值总和。开始时，它将//第一个和最后一个元素分别放入左侧和右侧队伍。然后，它比较两个队伍的力量值// 总和，并根据比较结果将下一个元素添加到力量值总和较小的队伍中。这个过程持// 续进行，直到所有的元素都被分配到队伍中{vector<int>arrleft;vector<int>arrright;arrleft.push_back(arr[0]);arrright.push_back(arr[arr.size() - 1]);int leftnumber = 1;int rightnumber = arr.size() - 2;while (leftnumber <= rightnumber){if (forceleft(arrleft) >= forceright(arrright)){arrright.push_back(arr[rightnumber]);rightnumber--;}else{arrleft.push_back(arr[leftnumber]);leftnumber++;}}return forcediffence(arrleft, arrright);}int main()//main函数读取输入的力量值数量n，然后读取力量值并存储到arr中。//之后，它调用force函数来计算并输出两个队伍力量值总和的最小差异{int n;cin >> n;vector<int>arr;arr.resize(n); // 确保arr有足够的空间来存储元素 for (int i = 0;i < n;i++){cin >> arr[i];}cout << force(arr) << endl;;return 0;}一些是个人自己做法，一些参考其他人的做法写的，毕竟实力有限，可能和答案有出入；有一些地方可能有错误或者重复的部分，可以指出，望见谅。
