本人是二本院校大二的计算机系学生，已经报名了下一届的蓝桥杯省赛，整个寒假在家（这次的寒假挺久的哈哈）在b站学习了一些算法（现在会bfs走迷宫、dfs相关算法、递归回溯、常见排列算法），但是还是有很多算法都还不太熟悉，做起题来真是费劲。

这是我第二次完整的刷真题，第一次刷的是第七届的真题，其刷题笔记、思路和答案在：

不得不说，这次刷的第八届题目真是有点难度，开头几道题就难倒我了，花了好长时间想……（我想，考试时如果这样耗着就挂了，所以遇到不会的一定要跳过！）

不过，我相信通过思考总结后，一定会有所收获的！

注：已完整解答的题目将会标记 （已完成） ，未完全解答出来的题目将在后续更新。代码设计题的代码不代表官方正确解法，只是通过了题目所给的测试而已，因此代码有误还请各位大佬指出哈哈。题目将保留原真题的完整描述，下次复习的时候可以强迫自己多读题（读懂题是关键啊！后面有道题读了十几分钟却不知道题目在讲什么，太浪费时间了！）

第一题、购物单（已完成）

小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。
这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。
小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。
现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。
取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。
你的任务是计算出，小明最少需要取多少现金。
以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。
需要说明的是，88折指的是按标价的88%计算，而8折是按80%计算，余者类推。
特别地，半价是按50%计算。
请提交小明要从取款机上提取的金额，单位是元。
答案是一个整数，类似4300的样子，结尾必然是00，不要填写任何多余的内容。

很简单的数学题，逐个相乘然后求和即可。

但是……我还真的那么笨的一个个去算了，写了可能有15分钟吧，还好答案对了，不然到时候考试这么写，真的亏死了。

巧妙做法：参考了网上大佬的做法，其实只需要把数据复制到一个空文本里，然后把*****用替换功能全部换成“+”号，把“半价”替换成 “ *0.5 ” (数字前面有个乘号)，然后依次把xx折替换成相应的 “ *0.xx ”（前面有个乘号），最后把这段数据放到编译器里执行就好了。

第二题、纸牌三角形（已完成）

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。
下图就是一种排法（如有对齐问题，参看p1.png）。
这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？
请你计算并提交该数字。
注意：需要提交的是一个整数，不要提交任何多余内容。

把三角形展开来看成数组，然后用全排列把数组所有可能列举出来，然后判断有多少种情况符合即可。

这道题，我居然做了1个多小时，还做错了……我把它复杂化了，我分别写了3个方法来判断是否符合边长相等、是否是旋转的情况、是否是镜像的情况。这里记录一下错误的代码……下次复习的时候得长长记性……

除非思路很清晰，否则不要写那么长的代码！！！不要写那么长的代码！！不要写那么长的代码！！很容易出错。

其实全排列没有错，错的是判断情况的时候。其实只需算出边长相等的情况的次数count，然后再判断这其中包含的重复情况。

这里我看错题意了！我以为旋转的意思是9个数字整体顺时针移动1位，真是糊涂啊[捂脸]。这个三角形有3个顶点，旋转的意思应该是从一个顶点到另一个顶点，也就是下面所示：

也就是说，一个数组，就能衍生出其他2种重复的情况，所以总数要除以3，也就是 count / 3 就好了。

一开始想的时候我又想复杂了，写了一通代码，结果不知道为何总是运行不了这个方法。

镜像，只有左右两种情况是重复的，count / 2即可。

所以总的来说，count / 3 / 2，就是正确答案了。

第三题、承压计算（已完成）

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同。
金属材料被严格地堆放成金字塔形。
其中的数字代表金属块的重量（计量单位较大）。
最下一层的X代表30台极高精度的电子秤。
假设每块原料的重量都十分精确地平均落在下方的两个金属块上，
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小，所以显示的数字很大。
工作人员发现，其中读数最小的电子秤的示数为：
请你推算出：读数最大的电子秤的示数为多少？
注意：需要提交的是一个整数，不要填写任何多余的内容。

题目的意思就是把当前的数字分成两半，然后分别把一半的重量放在下一层的左右两个东西上，然后下一层的数字也这样重复操作。

从头部截取一部分数据来解释一下我的做法：

1、逐行扫描，把一行当成数组。比如扫到上面部分的第一行，记录当前行：

2、然后另外定义一个“分散数组” arr，用来记录当前行分散（平分）后的值，那么会得到

3、上面的分散数组即将堆叠到下一层上。继续记录下一行（7，8，8），把这一行的值加上上一行的分散数组的值(即 one[i] = arr[i] + one[i] )。

也就是说，下面的金字塔，左侧和右侧是等效的

然后重复以上步骤累计叠加，最后一行获得的数组就是每个电子秤的值。然后在电子秤上寻找最小值，和题目给出的“”进行比对，肯定会有比例关系，然后在电子秤上寻找最大值乘以这个比例应该就是最终答案了。

值得注意的是，这样除下去会出现很多的小数（金字塔有29层，小数部分起码会超过小数点后20位），这样会影响我们的判断。于是可以把金字塔每个数字都乘以2^29次方，这样就能保证从头除到尾都不会出现小数了，到时候在从输出的结果中判断即可。

对于上面的代码，我是把金字塔数据放进一个空的txt文本里，然后用网上查的读取文件的方法逐行读取（），然后构造数组，再进行相应的计算即可。

运行后，最后一行数组（全部都是0的那一行）得到的结果是：

这个就是所谓的每个“电子秤”算出的结果，然后我们就观察每个电子秤上的数值，先找到最小值。最小值就是最后一个，即“”，这就巧了！这不就是题目提到的数值吗！所以我们只需要找到这其中的最大值，肯定就是电子秤的最大值（也就是正确答案）了。

注：这道题思路是使用bfs把每种情况列举，然后使用set集合去重，这其中代码很复杂（C语言实现都需要120+行代码），如果到了真正考试的时候，我觉得可以放弃这道题了。

二阶魔方就是只有2层的魔方，只由8个小块组成。
小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：
请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。
如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。
请提交表示状态数的整数，不要填写任何多余内容或说明文字。

第五题、取数位（已完成）

求1个整数的第k位数字有很多种方法。
 
 
 
 
对于题目中的测试数据，应该打印5。
请仔细分析源码，并补充划线部分所缺少的代码。
注意：只提交缺失的代码，不要填写任何已有内容或说明性的文字。

这个函数的作用和它的名字一样，意思是计算x是几位数。因为这是一个递归函数，返回值是len(x / 10) + 1，也就是说每返回一次，x就会少一位（从最低位开始少），同时会计数一次，当x少到不能再少了（x < 10），返回1，然后再逐个递归返回，就可以得到位数。

上面的话有点拗口，刚接触时我也不懂这个函数是什么意思（新手最头疼的就是递归回溯了），仔细了解了一下终于明白了，用下面方式表示可能更直观一点。

2、明白了len()函数的用法后，再来看看f() 函数。

这里不妨设一个比较极端的例子，x = 321， k = 3作为参数传入执行函数：

传入参数后，进行if条件判断，可以发现条件成立，直接返回 x % 10 = 1;（从这里发现了，第k位上的数字，其实指的是从左到右数第k个数字）

好的，那么横线上应该填什么呢？我们试着把x = 4321, k = 3传入

首先进来，if条件肯定判断不通过，所以需要用到我们填空部分的代码。我们要得到的值是"2"，即 f(4321,3) = 2 .那么怎样才能让if条件通过并返回2呢？

我们可以逆推，如果返回的是2，那么这个2一定是在个位，因为只有这样x %10才能等于2。

所以我们的关键在于，如何把4321变成432，很简单，4321 / 10 = 432. 也就是说，我们需要执行f(432, 3)，那么就会返回2了。所以需要在 f(4321,3) 里面再执行 f(432,3) 所以填空部分是一个递归，也就是：

第六题、最大公共子串（已完成）

最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路，并补全划线部分缺失的代码。
 
 
 
 

可以在草稿本上寻找规律，其实举个例子就很容易得出答案了。（下面写的有点复杂，建议拿纸和笔再写一下，挺容易找到规律的。）

代码中提供了两个字符串，把它们分别转化成了数组c1和c2，然后又开辟了一个二维数组a，行是c1.length + 1, 列是 c2.length + 1, 所以我们不妨画个图走一遍代码流程。

我们需要判断"abcdkkk"和"baabcdadabc"的最大公共子串，那么开辟的二维数组就是如下表格所示。其中：

1、横向是索引j, 纵向是索引i，自动初始化为0, 由于for循环索引从1开始，所以等于0的部分全部用"-"代替。

2、由于不知道划线部分应该填什么，就暂时把a[i][j]赋值为1作为标记，于是能得到以下表格：

通过表格可以得知，公共子串在表格中是以对角线形式存在的，而且很容易知道对角线长度其实就是公共子串的长度。因此，为了记录长度，当执行到
a[i][j]=__________时，这里的值应该是沿着对角线自增1，然后变量max会自动记录最大值。因此答案为：

第七题、日期问题（已完成）

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在
1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，
有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，
存在很多可能的日期与其对应。 
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。 
峰值内存消耗（含虚拟机） < 256M
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

现在回过头来看官网对历年真题的解答，发现之前写的代码存在很大的漏洞！很可能超过一半的数据都不能够通过测试。

错误在于yy_MM_dd(int y, int m, int d) 这个方法中。之前在这个方法中我只判断了（day > 31）的情况，殊不知其实还有很多情况需要判断，比如1、3、5、7、8月才有31天，而2月的情况又要分成闰年（29天） 和

①利用参数y构造年份字符串year;
②利用参数m构造月份字符串month，如果不能构造（如m>12），提前return;
③利用参数d构造日的字符串day，如果不能构造（如d>31），提前return;

①利用参数y构造年份字符串year；

②利用参数m构造月份的字符串month；如果不能构造（如m>12），提前return;

③利用参数d构造日的字符串day，并进行一系列的判断（如判断该月应该是30天还是31天、该年是闰年还是平年），如果发现不能构造，提前return；

2、输入的形式是 02/03/04，用 数组t 从左到右存储这3个数字。对于输入的日期（如02/03/04），分成以下三种情况（注意方法的参数从左到右是年、月、日）：

也就是说，在main里执行3次 yy_MM_dd() 方法，只不过3次执行方法时传入的参数顺序不同。

注：该题代码虽通过了题目给出的测试，但是时间复杂度太高，到真正考试时有可能有些例子会运行超时，等到后面我知道了更优的解法后再回来补充。（考试时这样写应该也能得到一点分的）

建议看官网对该题的讲解！我感觉这道题我的思路不对，以下思路及代码不建议作为解题的参考，建议直接看官网源码（在我自己写的代码后面）。这道题考虑到了使用完全背包（dp）的算法（我还没学习到），具体思路建议到官网看题解。

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中
第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼
中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买
11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能
放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
对于样例2，所有奇数都凑不出来，所以有无限多个。 

题目简化过来的意思就是：给定几个数(a1,a2, … ,an)，由这几个数随意组合凑正整数（这几个数都有无限个），求出不能凑出正整数的数量。
1、比如（3，4）两个数，1、2、5就凑不出来。
6可以凑出来，3+3；
2、再举个例子，（4，5）两个数，1、2、3、6、7凑不出来。
通过这两个例子，大胆推测，如果两个数（a，b）组合起来，在区间 [a*b, +∞) 内任意整数都可以通过（a, b）凑出来。因此我们只需要考虑区间 (0, a*b] 内有多少个数不能被表示即可。
于是代码具体步骤如下：
1、比如（3，4）两个数，开辟一个长度为3×4的数组。能凑的数用1标记。
2、列一个方程，3x+4y=C，先固定C，然后再固定y，如果得出x有正整数解，说明这个C可以通过3和4凑出来。比如3x + 4 = 7，存在正整数解x = 1，因此7 可以通过3 + 4凑出来。
3、由于输入的数字不一定只有两个，多个数的话，那就两两分组，依次执行以上方法（开辟的数组长度我大胆推测为两个最小的数之积，然后这个数组需要作为“全局变量”，即多组数据共享这个数组），如果参数a和b都是偶数，那么不执行这个方法。

以下是自己写的代码，当测试数据只有2个数字时，代码可通过，未测试多于2个数字时的正确性。建议参考官网源码 （在这段代码的后面）；

第九题、分巧克力（已完成）

 儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
 小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
 为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
 1. 形状是正方形，边长是整数 
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入保证每位小朋友至少能获得一块1x1的巧克力。 
输出切出的正方形巧克力最大可能的边长。

1、按照面积来分。把每块巧克力的面积加起来，然后除以人数，就能得到每个人理论上得到的巧克力的面积（记为sq）。

2、然后把该面积（sq）开根号，得到的数向下取整，作为每块巧克力的边长（记为bian，此时的bian一定是理论上最好的情况）

3、以这个bian为标准，来计算巧克力是否够分。

注意：计算巧克力是否够分时，如果巧克力的最短边小于bian，那么一定要把这个最短边赋值给bian，然后重新计算。

如果不够分，bian–；

4、直到bian减到全部巧克力够分了，输出bian；如果bian等于1，直接输出1；

1、现有一个6×6的巧克力，8个人分。其总面积为36，理论上每个人得到的巧克力面积为：sq = 36/8 = 4.5

2、sq开根号，得到理论上每个人得到的巧克力的最大边长bian = √4.5 ≈ 2.1213……然后向下取整，即bian = 2；

3、把这个大巧克力的长（为6）除以bian，得到3；把这个巧克力的宽（为6）除以bian，得到3；也就是说，这个巧克力能分出3 × 3 = 9 个bian 为2的巧克力。9 >= 8，够每个人分，直接输出bian = 2。

第十题、k倍区间（已完成）

注：该题代码运用的是暴力法，可能有些测试会超时，如果等到后面知道了更优的解法，再回来补充。

想着这个是最后一题了，按照我刷题的速度，考试时写到这一题，时间也应该所剩无几了。所以花了不到10分钟写了一个暴力法。

就是把这个数组的所有公共子串列举出来，然后统计总和，如果总和是k的倍数，计数count++即可。

刷题其实就是为了积累经验，能够在刷题的过程认识到自己缺失的知识点，那么刷题就是有效果的。以上所有代码仅供参考，不代表官方解法（官方源码除外）。其实代码也不是注重于结果，而是注重刷题时的思考过程，熟悉了各种题目的套路考试起来才能得心应手啊。