蓝桥杯！经验分享~(24年15届省一)

前言

首先说明一下本篇文章并非比赛复盘与题目讲解，而是作者比赛做题时自己的思想路程，以给其他人一些切实的比赛体验与经验，而不会拥有具体的解题代码等

本文章文字很多，请耐心阅读，不需要看懂，就是通过我做题时的一些心路历程来了解了解比赛大概是怎么一会事，希望能帮助到你。

—————————————————————————————————————————

这里先说明一下我的情况：

获奖：C/C++ B组 省一

以前的比赛经历：无

知识储备：只学了 C 语言的各种语法基础，算法只浅学了七种常见的排序(我其他文章中有)，数据结构学了 顺序表、链表、栈和队列还有树结构中的二叉树和堆 等很基础的数据结构

学习时间：从去年九月到今年四月比赛

刷题：最多刷了百来道题，且多数为简单难度

以上说这些是为了告诉大家，自己知识储备量少、经验少也是可以拿奖的，要相信自己

而作者拿奖就是凭借：基础扎实，做题(思考)时清晰的头脑，和一点运气

—————————————————————————————————————————

这里说一些在比赛前我做的一些准备：

比赛前几天去看了一下和做了一下去年蓝桥杯的比赛，结果只能做起两道题，其余很多题目我题都读不明白或我根本没有那方面的知识储备，但仔细看题解时又能看懂，懂了之后再去看题目瞬间就明白题目说的是什么了，也就是说，如果明白题目说的是什么的话，题就能做上百分之六十以上了，所以我明白了 先要逐字逐句地用清晰的头脑把题目看懂，也就是因为做到了这点，在比赛时我除了一道动态规划的问题，其他所有题都至少由思路

然后另一个准备是去学习了一下DevC++怎么用，因为我一直用的VS，DevC++报错是英文的嘛，所以基本没用过，在考试前在网上看了下视频，学会了调试，这也帮了我大忙

下面开始讲题了

—————————————————————————————————————————

A:握手问题

题目描述：

小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上， 大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进 行一次握手（且仅有一次）。但有 7 个人，这 7 人彼此之间没有进行握手（但 这 7 人与除这 7 人以外的所有人进行了握手）。

请问这些人之间一共进行了多 少次握手？

注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。

作者思路：

因为作者笨怕出错，乍一看感觉很简单，觉得这七个不握手的人所导致减少的次数是固定的，但为了保险起见，我先以十个人中七个人不握手，算了下这七个人不握手所导致减少的握手次数的确是固定的，才最后用五十个人互相握手减去这七个人减少的次数，最后得出：1204

并且，因为作者的谨慎，握手次数到底是怎么计算的我也是画图一个一个数的来确定的，虽然耗时间，但最终实际结果证明：在这种考基础的比赛上 “稳” 比 “快” 更重要吧

—————————————————————————————————————————

B：小球反弹

题目描述：

有一长方形，长为 343720 单位长度，宽为 233333 单位长度。在其内部左 上角顶点有一小球（无视其体积），其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx : dy = 15 : 17。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速 率不变（如果小球刚好射向角落，则按入射方向原路返回）。

从小球出发到其第 一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍 五入保留两位小数。

作者思路：

当我一看这题的图和读这题目时，第一反应就是和物理有关，啥入射角啊反射角，但我物理又不怎么样，心里上就有压力，就导致看不懂题(或因为内心就已经认定不会做了)，又看见这例子的数据巨大，连拼凑答案的可能都没有，所以果断放弃，看后面有没有时间再看看，知难而退才能更合理地分配资源嘛

但是未战先怯是很不好的的习惯，大家一定不要像我这样，至少要先把题读个大概确定自己确实没法应付才先暂时放弃

—————————————————————————————————————————

C：好数

题目描述：

一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上 的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称 之为“好数”。

给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

输入格式：

一个整数 N

输出格式：

一个整数代表答案

样例输入1：

24

样例输出1：

7

样例输入2：

2024

样例输出2：

150

样例说明：

对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。

评测用例规模与约定：

对于 10% 的评测用例，1 ≤ N ≤ $10^2$。

对于 100% 的评测用例，1 ≤ N ≤ $10^7$。

作者思路：

对于这道题，思路上很简单，就是从个位开始一直向前判断是否满足条件即可，这里我用了条件编译，就是先判断末位上是否满足条件，然后 /= 10，再判断是否满足条件，循环直到为 0 也就是这个数已经判断完，这里条件编译是什么意思呢，就是 判断奇数位 和 偶数位 的代码轮流编译

大概就如下三部分：”首次定义“    ~~    ” 若定义了奇数的就执行奇数的代码“    ~~   ”若定义了偶数的代码就执行偶数的代码“

#define 奇数 1         ~~~~~~~        //因为先判断奇数位(个位)所以先定义奇数

---

#ifdef 奇数

…                          ~~~~~~~~~~~~~~~~~~~~~~~~                          //判断奇数位的代码
#undef 奇数          ~~~~~~~~          //删除这个定义
#define 偶数 1      ~~~~      //定义偶数的

#endif

---

#ifdef 偶数

…                          ~~~~~~~~~~~~~~~~~~~~~~~~                          //判断偶数位的代码
#undef 偶数          ~~~~~~~~          //删除这个定义
#define 奇数 1       ~~~~~      //定义奇数的

#endif

---

D: R 格式

题目描述：

小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d ，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是：

1. 将浮点数乘以 $2^n$

2. 四舍五入到最接近的整数

输入格式：

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

输出格式：

输出一行表示答案：d 用 R 格式表示出来的值

样例输入：

2     ~~~     3.14

样例输出：

13

样例说明：

3.14$\times 2^2$=12.56，四舍五入后为13

评测用例规模与约定：

对于 50% 的评测用例，1 ≤ n ≤ 10，1 ≤ 将d视为字符串时的长度 ≤15。
对于100% 的评测用例，1 ≤ n ≤ 1000 ，1 ≤ 将 d 视为字符串时的长度 ≤1024；保证 d 是小数，即包含小数点。

作者思路：

当时这道题在没学高精度问题的我眼下异常简单，就直接 浮点数乘 $2^n$ 后 加 0.5 再强制类型转换为整型了，就点击这句话跳转的文章中的第二个方法，当时根本没去往高精度的方向去想，但这样这道题还是肯定跑了一点分的，如果当时想起来了高精度的话，我还是不会做，不过上面步骤 加0.5 就会改为 0.5555555 这样的了，肯定就能跑更多题了

所以，讲究一个用最朴素的办法去一点一点的拿分

—————————————————————————————————————————

E：宝石问题

题目描述：

在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的“闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的“闪亮度” 属性值为 $H_i$，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：
$$S=H_a{H}_b{H}_c\cdot \frac{\mathrm{LCM}\left(H_a,H_b,H_c\right)}{\mathrm{LCM}\left(H_a,H_b\right)\cdot \mathrm{LCM}\left(H_a,H_c\right)\cdot \mathrm{LCM}\left(H_b,H_c\right)}$$

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

​输入格式：

第一行包含一个整数 N 表示宝石个数
第二行包含 N 个整数表示 N 个宝石的“闪亮度”

输出格式：

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

样例输入：

5
1 2 3 4 9

样例输出：

1 2 3

评测用例规模与约定：

对于 30 % 的评测用例，3 ≤ N ≤ 100，1 ≤ $H_i$ ≤ 1000
对于 60 % 的评测用例，3 ≤ N ≤ 2000
对于 100 % 的评测用例，3 ≤ N ≤ $10^5$，1 ≤ $H_i$ ≤ $10^5$

作者思路：

当时我一看这么长题目，还有一大串公式就觉得这题肯定很难，但实际这题你只要把这么一长串题目读懂就会发现挺简单的，所以我说 清晰地理解题意很重要

其实这道题先写出求最小公倍数的函数，再遍历代入公式，就暴力解题啦，当然肯定只能跑一部分，不过当时这么长题目和公式，脑袋已经晕了，只想着按着做能把题做了就行了，而且作者因为基础还是不够扎实，写的求最小公倍数的函数时间复杂度极高，给出的数据大小只要破百 程序就会挂，所以这道题我可能根本没得分

也就是告诉大家基础很重要，细心很重要，冷静也很重要

—————————————————————————————————————————

F：数字接龙

题目描述：

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 $N\times 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。
输入格式：

第一行包含两个整数 N、K
接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字

输出格式：

输出一行表示答案。如果存在答案输出路径，否则输出 -1

样例输入：

3 3
0 2 0
1 1 1
2 0 2

样例输出：

41255214

样例说明：

行进路径如 图$1$ 所示

评测用例规模与约定：

对于 80% 的评测用例，1 ≤ N ≤ 5
对于 100% 的评测用例，1 ≤ N ≤ 10，1 ≤ K ≤ 10

作者思路：

这题一眼动态规划(dfs)，我虽然没学过还是见过一次的，所以果断放弃，当然不能什么都不写，不是说没有答案输出 -1 吗，那么 printf(“-1”);

就是这样了，不会的话只写可能会出现的答案也可能拿分

—————————————————————————————————————————

G：爬山

题目描述：

小明这天在参加公司团建，团建项目是爬山。在$x$轴上从左到右一共有$n$座山，第 $i$ 座山的高度为 $h_i$。他们需要从左到右依次爬过所有的山，需要花费的体力值为$s=\underset{i=1}{\sum ^n}{h}_i$。
然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为 $H$ 的山的高度变为 $\sqrt{H}$，可以使用 $P$ 次；第二种魔法可以将高度为 $H$ 的山的高度变为 $\frac{H}{2}$，可以使用 Q 次，并且对于每座山可以按任意顺序多次释放这两种魔法。

小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少？

输入格式：

输入共两行
第一行为三个整数 $n,P,Q$
第二行为 $n$ 个整数 $h_1,h_2,...,h_n$

输出格式：

输出共一行，一个整数代表答案

样例输入：

4 1 1
4 5 6 49

样例输出：

18

样例说明：

将第四座山变为$\sqrt{49}=7$，然后再将第四座山变为$\frac{7}{2}=3$
体力值为 $4+5+6+3=18$

评测用例规模与约定：

对于 20% 的评测用例，$n$ ≤ 8，$P$ = 0
对于 100% 的评测用例，$n$ ≤ 100000，0 ≤ $P$ ≤ $n$，0 ≤ $Q$ ≤ $n$，0 ≤ $h_i$ ≤ 100000

作者思路：

这题题意很好理解，哪座山高就对它使用魔法，然后用效果最好的魔法(减的最多)，但我当时可能有点晕了就在想一种可能：会不会虽然当前这次魔法的效果最大化了，但如果巧妙地用一些其他的顺序会比 ”单纯每次去用减的更多的魔法“ 要更好。但又无法去推理证明，于是觉得这题很难，但看用例时，前 20% 的用例只有 /2 的魔法，就去跑这 20% 的用例了。但实际上不会存在这个可能

而具体思路就是，要把所以山尽量弄成差不多高的，就先把山排升序，因为魔法只有第二种(当时只想跑前 20%)，所以把排好序的山从中位数的位置分开，然后从最后的一座山向前使用魔法，如果当前被施魔法的这座山还是比它前面那座山高就继续对它用魔法，不然就按顺序一 一向前一座山施法直到魔法用完或到达中间位置的山，然后重新排序再来一次。
不过这里思路有个缺陷，若以前被施法的山的高度比当前要施法的山还要高，继续施法就是错误的了，因为我们没有对后面已施过法山做处理，但我们只要记录一下已施过法中最高的山，只要当前的山比它矮就提前重新排序再来一次。
然后现在我发现，把山从中间分为两块，施法到中间的山时就重复步骤这一点好像是多余的，不过谁知道我那时候是怎么想的呢。

最后当我把这跑测例的代码写好后，一瞧就发现所有测试用例也就是包括第一种魔法，它不就是多了个判断哪个魔法减的更多吗，所以最后把那部分补充上就完成这道题了

所以这道题可以告诉大家，保持头脑清晰真的很重要，我这道题就是因为前面都是跑用例已经形成了”都不会“的想法，所以先只写了个半成品，幸好后面清醒了一下，把它补全了。还有一点，因为我忘了 qsort 函数是怎么样的了，所以排序是自己手撕的一个快排，耗费了很多时间，所以基础也真的很重要

H：拔河

题目描述：

小明是学校里的一名老师，他带的班级共有$n$名同学，第$i$名同学力量值为$a_i$在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛的双方实力尽可能相近，需要在这$n$名同学中挑选出两个队伍，队伍内的同学编号连续： { a l 1 , a l 1 + 1 , . . .   , a r 1 − 1 , a r 1 } \{ a_{l_1},a_{l_1+1},... ~,a_{r_1-1},a_{r1}\} {al1​​,al1​+1​,... ,ar1​−1​,ar1​} 和 { a l 2 , a l 2 + 1 , . . .   , a r 2 − 1 , a r 2 } \{ a_{l_2},a_{l_2+1},... ~,a_{r_2-1},a_{r2}\} {al2​​,al2​+1​,... ,ar2​−1​,ar2​} ，其中 $l_1\le r_1<l_2\le r_2$。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式：

输入共两行
第一行为一个正整数 $n$
第二行为 $n$ 个正整数 $a_i$

输出格式：

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

样例输入：

5
10 9 8 12 14

样例输出：

1

样例说明：

其中一种最优选择方式：
队伍一： { a 1 , a 2 , a 3 } \{a_1,a_2,a_3 \} {a1​,a2​,a3​}，队伍二： { a 4 , a 5 } \{a_4,a_5 \} {a4​,a5​}，力量值分别为 $10+9+8=27$， $12+14=26$，差距为 $|27-26|=1$

评测用例规模与约定：

对于 20% 的评测用例，$n$ ≤ 50
对于 100% 的测评用例，$n$ ≤ $10^3$，$a_i$ ≤ $10^9$

作者思路：

这题我的思路是根据它给的样例所得出来的，但漏洞百出。不过我的目的还是跑部分用例，对于第一次参加比赛并且知识储备这么少，我的目标就是不能留空，跑测试用例就行了。

我的思路就是先将数据排序，然后从中间分为左右两部分，左部分肯定小于等于右部分的，然后将右部分最小的一个一个地加到左边去，直到左部分 ≥ 右部分，记录最小差值。当然，这样做漏洞百出啦，不过能跑过样例(笑)，现在想来如果只想着跑用例的话，数据排序后从右往左哪边力量小就放数据到哪边，后面放的值小，差值肯定更小，就能跑更多用例了(笑)。但是以上都不是正确正经的做法(笑)。

相信大家也肯定知道不会做的题就跑部分用例和样例就行了，毕竟能跑过样例就说明是存在这样的可能的，也就是是存在得分的可能的，所以遇到不会的题，一定要尝试用最朴素简单的思路去跑尽可能多的用例

后记

这次比赛能获得省一我真的始料不及的，运气的部分肯定占很大的吧。
真正拿下的题可能只有 C 和 G 两道题吧，其他的都跑跑用例，所以大家不会做一定要跑跑用例

这里再说一下比赛过程吧：

其实没什么需要注意的，比赛时记得带身份证和考证还有吃的，考试开始时老师会告诉一个网址，输入后进入考试界面等待考试即可，代码写好后记得放到”试卷上“，其他的需注意的东西你到考场一看就明白了，然后考场上有什么需求和需要帮助的找老师就行了，像我考试时那个键盘是坏的换两次都是给我拿个烂的来，第三个才是好的(笑)，然后即使我带了吃的，但考场上没有其他人吃东西我也不好意思吃，就饿着肚子(都叫出声了)，你们一定要该吃吃该喝喝，不要像我的考场上其他那些人，那么腼腆不吃东西，害得我都不好意思吃东西
(╯ರ ~ ರ）╯︵ ┻━┻

最后，感谢你能看到这，万分感谢，希望帮助到了你！