蓝桥杯CB | 第十五届省赛题 & 题解

题解是看了蓝桥云课中的大佬的题解，然后边学习边用自己的话写出来的，代码也是稍微改过一些（方便我这个菜鸟看懂），以是假如有冒犯，联系我删除就好了。感谢各位大佬的题解，受益匪浅。 
  握手问题

题目

问题描述

小蓝组织了一场算法交流会议，统共有 50 人参加了本次会议。在会议上，各人进行了握手交流。按照惯例他们每个人都要与除自己以外的其他全部人进行一次握手 (且仅有一次)。但有 7
 个人，这 7
 人彼此之间没有进行握手 (但这 7
 人与除这 7
 人以外的全部人进行了握手)。请问这些人之间一共进行了多少次握手?
留意 A 和 B 握手的同时也意味着 B 和 A 握手了，以是算作是一次握手。
答案提交 

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
题解 

    感觉是数学问题，直接画图找规律

1. #include <iostream>
2. using namespace std;
3. int main()
4. {
5.   int cnt&#61
6. ;0;
8.         cnt+&#61
9. ;2*(5-2);
11.         int i&#61
12. ;5-2-1
13. ;
15.           for( ; i>&#61
16. ;0;i--)
17.           {
18.             cnt+&#61
19. ;i;
20.         }
22.         cout<<cnt;
23.         return 0;
24. }

复制代码

小球反弹

题目

问题描述

有一长方形，长为 3437
20 单位长度，宽为 233333 单位长度。在其内部左上角顶点有一小球 (无视其体积)，其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx:dy&#61
;1
5:1
7
。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速率不变（假如小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度&#xff1
f;答案四舍五入保存两位小数。

[img]https://i-blog.csdnimg.cn/direct/f1
1
2b30607
1
5442b9401
bd8f2993e97
2.png[/img]

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个小数，在提交答案时只填写这个小数，填写多余的内容将无法得分。
题解

   神。。。 暂时看不懂。。。等我有空再来研究一下。。。如今脑筋已经停摆了

1. #include<bits/stdc++.h>
2. using namespace std;
4. int main()
5. {
6.         long long t&#61
7. ;1
8. ,x&#61
9. ;3437
10. 20,y&#61
11. ;233333;
12.        
13.         //往右延长同样的长方形，当走到第t个长方形的左上角，就算是回到了左上角了
14.         while(1
15. )
16.         {
17.                 if((1
18. 5*t)%x&#61
19. ;&#61
20. ;0 && (1
21. 7
22. *t)%y&#61
23. ;&#61
24. ;0)
25.                         break;
26.                 t++;
27.         }
28.        
29.         //如果小球刚好射向角落sqrt(1
30. 5*1
31. 5*t*t+1
32. 7
33. *1
34. 7
35. *t*t)
36.         //那么根据对称性，按入射方向原路返回，需要*2
37.         cout<<fixed<<setprecision(2)<<2*sqrt(1
38. 5*1
39. 5*t*t+1
40. 7
41. *1
42. 7
43. *t*t);
44.         return 0;
45. }

复制代码

好数

题目

问题描述

一个整数假如按从低位到高位的次序，奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数，我们就称之为 “好数”。
给定一个正整数 N，请盘算从 1
到 N 一共有多少个好数。
输入格式

一个整数 N。
输出格式

一个整数代表答案。
样例输入 1

1. 24

复制代码

样例输出 1

1. 7

复制代码

样例输入 2

1. 2024

复制代码

样例输出 2

1. 1
2. 50

复制代码

样例阐明

对于第一个样例，24
 以内的好数有 1
、3、5、7
、9、21
、23，一共 7
 个。
评测用例规模与约定

对于 1
0% 的评测用例，1
≤N≤1
00。
对于 1
00% 的评测用例，1
≤N≤1
0^7
。
题解

    模拟，直接根据题意写，检查1
~n中的全部奇数（因为要求个位要是奇数）。

1. #include <iostream>
2. using namespace std;
4. bool pd(int n)
5. {
6.   int flag&#61
7. ;0,t;
8.   while(n)
9.   {
10.     t&#61
11. ;n%1
12. 0;
13.     //奇数位
14.     if(flag&#61
15. ;&#61
16. ;0){
17.       if(t%2&#61
18. ;&#61
19. ;0)
20.         return 0;
21.       flag&#61
22. ;1
23. ;
24.     }
25.     else{
26.       if(t%2!&#61
27. ;0)
28.         return 0;
29.       flag&#61
30. ;0;
31.     }
32.     n/&#61
33. ;1
34. 0;
35.   }
36.   return 1
37. ;
38. }
40. int main()
41. {
42.   int n; cin>>n;
44.   int cnt&#61
45. ;0;
46.   for(int i&#61
47. ;1
48. ;i<&#61
49. ;n;i+&#61
50. ;2)  //只检查奇数
51.   {
52.     if(pd(i)) cnt++;
53.   }
55.   cout<<cnt;
56. }

复制代码

R格式

题目

问题描述

小蓝最近在研究一种浮点数的表示方法&#xff1
a;R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是:
[list=1
]

将浮点数乘以 2^n&#xff1
b;

四舍五入到最靠近的整数。
输入格式

一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。
输出格式

输出一行表示答案&#xff1
a;d 用 R 格式表示出来的值。
样例输入

1. 2 3.1
2. 4

复制代码

样例输出

1. 1
2. 3

复制代码

样例阐明

3.1
4×2^2&#61
;1
2.56，四舍五入后为 1
3
。
评测用例规模与约定

对于 50% 的评测用例&#xff1
a;1
≤n≤1
0,1
≤ 将 d 视为字符串时的长度 ≤1
5。
对于 1
00% 的评测用例&#xff1
a;1
≤n≤1
000,1
≤1
将 d 视为字符串时的长度 ≤1
024
&#xff1
b;保证 d 是小数，即包罗小数点。
题解

    高精度模板题，这个题解巧妙的地方在于不是直接乘以2^n，而是用while循环，乘n次2。如许一来，每次都是高精度*低精度（2肯定是低精度），比高精度*高精度简单很多。

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.         int n;
6.         string d;  //数太大了，用字符串读
7.         cin>>n>>d;
8.        
9.         vector<int>b;  //用push_back进位的时候可以在后面直接加
10.        
11.         //逆序存储数字，并记录小数点位置（方便后续四舍五入）
12.         int sum&#61
13. ;0,k&#61
14. ;0;  //sum是包括小数点在内的位数，k是小数部分的个数
15.         for(int i&#61
16. ;d.size()-1
17. ;i>&#61
18. ;0;i--)
19.         {
20.                 if(d[i]!&#61
21. ;'.')  //小数点
22.                         b.push_back(d[i]-'0');  //把字符串转换成整型
23.                 else
24.                         k&#61
25. ;sum;  //记录小数点的位置
26.                 sum++;
27.         }
28.        
29.         //*2^n 相当于 乘以n次2
30.         while(n--)
31.         {
32.                 int t&#61
33. ;0;  //记录要进位的数，初始为0
34.                 for(int i&#61
35. ;0;i<b.size();i++)
36.                 {
37.                         b[i]&#61
38. ;b[i]*2+t;  //当前位置的数&#61
39. ;原数字*2+上一位进位的数
40.                        
41.                         //超过1
42. 0，进位
43.                         if(b[i]>&#61
44. ;1
45. 0)
46.                         {
47.                                 t&#61
48. ;b[i]/1
49. 0;  //进位
50.                                 b[i]%&#61
51. ;1
52. 0;
53.                         }
54.                        
55.                         //不需要进位，要把t置为0
56.                         else
57.                                 t&#61
58. ;0;
59.                 }
60.                
61.                 //如果全部运算完了还有要进位的数，直接push到b后面
62.                 if(t)
63.                         b.push_back(t);
64.         }
65.        
66.         //四舍五入
67.         bool flag&#61
68. ;1
69. ;  //标记进位有没有中途结束（方便检验最后一位有没有进位）
70.         if(k && b[k-1
71. ]>&#61
72. ;5)  //如果有小数部分且十分位>&#61
73. ;5（需要进行四舍五入）
74.         {
75.                 for(int i&#61
76. ;k;i<b.size();i++)  //从个位开始处理
77.                 {
78.                         b[i]+&#61
79. ;1
80. ;  //加上进位
81.                         if(b[i]<1
82. 0){  //如果加了进位之后<1
83. 0，不需要继续进位了
84.                                 flag&#61
85. ;0;
86.                                 break;
87.                         }
88.                         else
89.                                 b[i]-&#61
90. ;1
91. 0;  //进1
93.                 }
94.                 if(flag) //最后一位还要进位
95.                         b.push_back(1
96. );  //进位
97.         }
98.        
99.         //对b逆序输出，到小数点位置停止
100.         for(int i&#61
101. ;b.size()-1
102. ;i>&#61
103. ;k;i--)
104.                 cout<<b[i];
105.        
106.         return 0;
107.        
108. }

复制代码

宝石组合

题目

问题描述

在一个神秘的丛林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐蔽在树洞里的宝藏，里面装满了闪耀着美丽光芒的宝石。这些宝石都有着不同的颜色和外形，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi​，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量&#xff1
a;

[img]https://i-blog.csdnimg.cn/direct/07
2d8af321
8345a698f321
0eadc56a06.png[/img]

其中 LCM 表示的是最小公倍数函数。
小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。假如存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。
输入格式

第一行包罗一个整数 N 表示宝石个数。
第二行包罗 N 个整数表示 N 个宝石的 “闪亮度”。
输出格式

输出一行包罗三个整数表示满足条件的三枚宝石的 “闪亮度”。
样例输入

1. 5
2. 1
3. 2 3
4. 4 9

复制代码

样例输出

1. 1
2. 2 3

复制代码

评测用例规模与约定

对于 30% 的评测用例&#xff1
a;3≤N≤1
00,1
≤Hi​≤1
000 。
对于 60% 的评测用例&#xff1
a;3≤N≤2000 。
对于 1
00% 的评测用例&#xff1
a;3≤N≤1
05,1
≤Hi​≤1
0^5 。
题解

   在蓝桥云课上看到的这个题解太完整太清晰了，直接抄下来学习。
  起首是这个数学分析就想不到。然后另有就是反向摆列，一般都是摆列数字，盘算最小公因数，但是这个题解是直接摆列公因数，然后查找公因数的2、3……倍，看有没有这些闪亮度的宝石。然后另有就是可能存在相同闪亮度的宝石，以是感觉谁人k<mp[j]的for循环也非常神奇（也可能本人写算法题是在太太太少了）
  思路

   ** 侵删 **
  先进行数学分析&#xff1
a;

[img]https://i-blog.csdnimg.cn/direct/060b03cbbc1
3
44c5b01
c36a9e7
e0432b.png[/img]

其中gcd表示最大公因数。
摆列a，b，c三个宝石，盘算精美度，当摆列到一个比原本最大值还大的组合，更新宝石的组合，这种方法的时间复杂度太高了。
留意到题目中Hi​≤1
0^5，在限定Hi的大小，以是要直接根据最大公因数S来探求出满足条件的三枚宝石。与其摆列三个数字再盘算它们的S，不如直接摆列S来探求满足条件的三个数字。
举个例子，对于1
2 1
5 24
30这四枚宝石，当S&#61
;1
5时，我们可以找到闪亮度为1
5 30的这两枚宝石，但是题目要求需要3枚宝石才可以组合，以是使S&#61
;1
5的组归并不存在。当摆列S&#61
;6时，可以找到1
2 24
30三枚宝石，以是答案是1
2 24
30.
算法描述

1
）统计全部闪亮度对应的宝石个数
2）初始化一个长度为1
0^5+1
的数组mp，输入几就给数组mp的第几个元素+1

3）摆列S，对于每个S&#61
;i，都需要遍历整个mp来探求闪亮度为j（j&#61
;ki）的宝石个数。
初始化满足条件的宝石数量ans&#61
;0，让ans加上mp[j]，当ans>&#61
;3时，输出结果数组，假如宝石少于3个，摆列下一个S 
代码

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int h&#61
5. ;1
6. e5;
8. int main()
9. {
10.         int n; cin>>n;
11.        
12.         int mp[h+1
13. ]&#61
14. ;{0};  //mp[x]&#61
15. ;n表示闪亮度为x的宝石有n个
16.         for(int i&#61
17. ;0;i<n;i++)
18.         {
19.                 int t; cin>>t;  //闪亮度
20.                 mp[t]++;  //表示闪亮度为t的
21.         }
22.        
23.         //直接枚举精美程度S(这里用i表示)，因为要找最大的，所以递减枚举
24.         for(int i&#61
25. ;h;i>&#61
26. ;1
27. ;i--)
28.         {
29.                 int ans&#61
30. ;0;  //表示找到了几个宝石
31.                 int now&#61
32. ;0;  //表示现在数组有几个宝石
33.                
34.                 int num[3];  //存储枚举到的宝石j
35.                
36.                 //因为要查找最小公因数为i的宝石j，所以直接找mp数组下标为i 2i 3i...的宝石
37.                 for(int j&#61
38. ;i;j<&#61
39. ;h;j+&#61
40. ;i)
41.                 {
42.                         ans+&#61
43. ;mp[j];
44.                        
45.                         //从闪亮度为j的宝石中选取不超过mp[j]个宝石（可能有宝石是同一闪亮度）
46.                         //放入num数组，并使now++，直到已经选了3个宝石
47.                         for(int k&#61
48. ;0;k<mp[j] && now<3;k++)
49.                         {
50.                                 num[now]&#61
51. ;j;
52.                                 now++;
53.                         }
54.                        
55.                         if(ans>&#61
56. ;3)  //如果找到了三个以上的宝石，由于是从大到小枚举的，所以此时的就是答案
57.                         {
58.                                 for(int k&#61
59. ;0;k<3;k++)
60.                                         cout<<num[k]<<" ";
61.                                 cout<<endl;
62.                                 return 0;
63.                         }
64.                 }
65.         }
66. }

复制代码

数字接龙

题目

问题描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N×N 的格子棋盘上睁开，其中每一个格子处都有着一个 0…K−1
之间的整数。游戏规则如下&#xff1
a;
[list=1
]

从左上角 (0,0) 处出发，目标是到达右下角(N−1
,N−1
) 处的格子，每一步可以选择沿着程度/垂直/对角线方向移动到下一个格子。

对于路径经过的棋盘格子，按照经过的格子次序，上面的数字组成的序列要满足&#xff1
a;0,1
,2,…,K−1
,0,1
,2,…,K−1
,0,1
,2…。

途中需要对棋盘上的每个格子恰恰都经过一次（仅一次）。

路径中不可以出现交织的线路。例如之前有从 (0,0) 移动到 (1
,1
) ，那么再从 (1
,0) 移动到 (0,1
) 线路就会交织。
为了方便表示，我们对可以行进的全部八个方向进行了数字编号，如下图 2 所示&#xff1
b;因此行进路径可以用一个包罗 0…7
之间的数字字符串表示，如下图 1
是一个迷宫示例，它所对应的答案就是&#xff1
a;41
25521
4
。

[img]https://i-blog.csdnimg.cn/direct/de81
85fe5a81
4ba297
21
7
67
6fd4824
e1
.png[/img]

如今请你帮小蓝规划出一条行进路径并将其输出。假如有多条路径，输出字典序最小的那一个&#xff1
b;假如不存在任何一条路径，则输出 −1
。
输入格式

第一行包罗两个整数 N,K 。
接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。
输出格式

输出一行表示答案。假如存在答案输出路径，否则输出 −1
。
样例输入

1. 3 3
2. 0 2 0
3. 1
4. 1
5. 1
7. 2 0 2

复制代码

样例输出

1. 41
2. 25521
3. 4

复制代码

样例阐明

行进路径如图 1
 所示。
评测用例规模与约定

对于 80% 的评测用例&#xff1
a;1
≤N≤5。
对于 1
00% 的评测用例&#xff1
a;1
≤N≤1
0,1
≤K≤1
0 。
题解

   非常神奇的判断线路是否交织的方法。。。学习。。其他部分就是跟通例dfs题差不多

1. #include<bits/stdc++.h>using namespace std;const int N&#61
2. ;1
3. 1
4. ;  //棋盘最大大小int n,k;int g[N][N];  //存储棋盘上的数字//8个方向（对应图2中的0~7
5. ，因为要按字典序最小输出）int dx[8]&#61
6. ;{-1
7. ,-1
8. ,0,1
9. ,1
10. ,1
11. ,0,-1
12. };int dy[8]&#61
13. ;{0,1
14. ,1
15. ,1
16. ,0,-1
17. ,-1
18. ,-1
19. };string path;  //存储路径的方向编号bool st[N][N];  //标志棋盘上的格子是否被访问过//edge[a][b][c][d]&#61
20. ;1
21. 表示(a,b) → (c,d)已走过bool edge[N][N][N][N];  //检查路径是否交织//检查是否解决问题bool check(int x,int y){        if(x!&#61
22. ;n-1
23. || y!&#61
24. ;n-1
25. || path.size()!&#61
26. ;n*n-1
27. )                return 0;        return 1
28. ;}bool pd(int x,int y,int nx,int ny,int i){        //不能超出边界        if(x<0 || x>&#61
29. ;n || y<0 || y>&#61
30. ;n)                return 0;                        //只能走一次        else if(st[nx][ny])                return 0;                //符合序列要求        else if(g[nx][ny]!&#61
31. ;(g[x][y]+1
32. )%k)                return 0;                //检查路径是否交织（对于斜向移动，检查是否有反向的路径）        //i%2&#61
33. ;&#61
34. ;1
35. 表示是斜向移动（根据图2）        /*                假设往右下方向走&#xff1
36. a;            (x,y)      (nx,y)                         (x,ny)     (nx,ny)                那么需要检查是否存在(x,ny)->(nx,y)和(nx,y)->(x,ny)        */        else if(i%2 && (edge[x][ny][nx][y] || edge[nx][y][x][ny]))                return 0;                        else return 1
37. ;}bool dfs(int x,int y){        if(check(x,y))                return 1
38. ;                st[x][y]&#61
39. ;1
40. ;                for(int i&#61
41. ;0;i<8;i++)        {                int nx&#61
42. ;x+dx[i];                int ny&#61
43. ;y+dy[i];                                if(!pd(x,y,nx,ny,i))  //不满足                        continue;                                        //粉碎现场                edge[x][y][nx][ny]&#61
44. ;1
45. ;  //标志路径                path+&#61
46. ;i+'0';  //将方向编号加入路径                                if(dfs(nx,ny)) return 1
47. ;  //递归搜索下一个格子                                //规复现场                path.pop_back();                edge[x][y][nx][ny]&#61
48. ;0;        }        st[x][y]&#61
49. ;0;        return false;}int main(){        cin>>n>>k;                for(int i&#61
50. ;0;i<n;i++)                for(int j&#61
51. ;0;j<n;j++)                        cin>>g[i][j];                                if(!dfs(0,0))  //没有找到路径                cout<<-1
52. <<endl;        else                cout<<path<<endl;        return 0;}

复制代码

拔河

题目

问题描述

小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学气力值为 ai​。在闲暇之余，小明决定在班级里组织一场拔河角逐。
为了保证角逐的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号一连&#xff1
a;{al1
,al1
+1
,…,ar1
−1
,ar1
} 和 {al2,al2+1
,…,ar2−1
,ar2}，其中 l1
≤r1
<l2≤r2。
两个队伍的人数不必相同，但是需要让队伍内的同学们的气力值之和尽可能相近。请盘算出气力值之和差距最小的挑选队伍的方式。
输入格式

输入共两行。
第一行为一个正整数 n。
第二行为 n 个正整数 ai​。
输出格式

输出共一行，一个非负整数，表示两个队伍气力值之和的最小差距。
样例输入

1. 5
2. 1
3. 0 9 8 1
4. 2 1
5. 4

复制代码

样例输出

1. 1

复制代码

样例阐明

其中一种最优选择方式&#xff1
a;
队伍 1
&#xff1
a; {a1
,a2,a3}，队伍 2&#xff1
a;{a4,a5}，气力值和分别为 1
0+9+8&#61
;27
1
0+9+8&#61
;27
 , 1
2+1
4&#61
;261
2+1
4&#61
;26，差距为 ∣27
−26∣&#61
;1
∣27
−26∣&#61
;1
 。
评测用例规模与约定

对于 20% 的评测用例，保证 n≤50 。
对于 1
00% 的评测用例，保证 n≤1
03,ai≤1
09 。
题解

   没读清题、、被样例阐明坑惨了，以为必须要全部人都上场。感觉下面这个题解很巧妙的一点是不需要思量选重复的情况，也不需要思量两个队伍的编号限定，因为两个队伍选重复了其实就相称于两个队伍都没有选重叠部分，编号限定也完全就是用来迷惑的。。
  算法思路

因为队伍内的编号需要一连，通过两重for循环，摆列出每一种选法的气力值，放入check数组中&#xff1
b;
把check从小到大排序，气力之和差距最小的一定是在check中相邻的两种选法（不用管区间重叠的情况，重叠就相称于两种都没有选重叠部分）
代码实现

1. #include<bits/stdc++.h>using namespace std;typedef long long ll;const ll N&#61
2. ;1
3. e3+1
4. 0;ll n,a[N];ll cnt&#61
5. ;0;  //记录有几种选法，方便放入check数组ll check[N*N];  //记录每一种选法的气力值int main(){        cin>>n;        for(ll i&#61
6. ;0;i<n;i++) cin>>a[i];                for(ll i&#61
7. ;0;i<n;i++)        {                ll sum&#61
8. ;0;                for(ll j&#61
9. ;i;j<n;j++)                {                        sum+&#61
10. ;a[j];                        check[cnt++]&#61
11. ;sum;                }        }                //排序        sort(check,check+cnt);                //遍历check,找到相邻两个数之差的最小值        ll ans&#61
12. ;1
13. e1
14. 2+1
15. 0; //先把ans界说成一个很大的数，便于记录第一个值        for(int i&#61
16. ;1
17. ;i<cnt;i++)                ans&#61
18. ;min(ans,abs(check[i]-check[i-1
19. ]));                cout<<ans;        return 0;}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。