2017第八届蓝桥杯 C/C++B组真题及题解（未完待续）

                1. (5′)标题： 购物单
    小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。
    这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。
    小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。
    现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。

    取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。
    你的任务是计算出，小明最少需要取多少现金。

以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。
—————–
****     180.90       88折
****      10.25       65折
****      56.14        9折
****     104.65        9折
****     100.30       88折
****     297.15        半价
****      26.75       65折
****     130.62        半价
****     240.28       58折
****     270.62        8折
****     115.87       88折
****     247.34       95折
****      73.21        9折
****     101.00        半价
****      79.54        半价
****     278.44        7折
****     199.26        半价
****      12.97        9折
****     166.30       78折
****     125.50       58折
****      84.98        9折
****     113.35       68折
****     166.57        半价
****      42.56        9折
****      81.90       95折
****     131.78        8折
****     255.89       78折
****     109.17        9折
****     146.69       68折
****     139.33       65折
****     141.16       78折
****     154.74        8折
****      59.42        8折
****      85.44       68折
****     293.70       88折
****     261.79       65折
****      11.30       88折
****     268.27       58折
****     128.29       88折
****     251.03        8折
****     208.39       75折
****     128.88       75折
****      62.06        9折
****     225.87       75折
****      12.89       75折
****      34.28       75折
****      62.16       58折
****     129.12        半价
****     218.37        半价
****     289.69        8折
——————–

需要说明的是，88折指的是按标价的88%计算，而8折是按80%计算，余者类推。
特别地，半价是按50%计算。

请提交小明要从取款机上提取的金额，单位是元。
答案是一个整数，类似4300的样子，结尾必然是00，不要填写任何多余的内容。

特别提醒：不许携带计算器入场，也不能打开手机。

【分析】数据处理

        每种物品价格=原价*折扣（0~1），然后求和。得到的结果如果不是整数，则向下取整再+100。

        （PS：也可借助word excel 计算器等工具完成）

【答案】5200

2. (7′)标题：等差素数列

2,3,5,7,11,13,….是素数序列。
类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为30，长度为6。

2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。
这是数论领域一项惊人的成果！

有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：

长度为10的等差素数列，其公差最小值是多少br>
注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。

【分析】枚举

        根据等差数列的通项公式：an=a1+(n-1)*d，可使用两重循环分别枚举数列的第一项a1和公差d，对每一项都需进行素数判定。此外，根据实际问题需要，可设定一个枚举范围：首项[2, 100000]，公差[1, 10000]，并维护最小公差。

【答案】210

3. (13′)标题：承压计算
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。

每块金属原料的外形、尺寸完全一致，但重量不同。
金属材料被严格地堆放成金字塔形。

                             7 
                            5 8 
                           7 8 8 
                          9 2 7 2 
                         8 1 4 9 1 
                        8 1 8 8 4 1 
                       7 9 6 1 4 5 4 
                      5 6 5 5 6 9 5 6 
                     5 5 4 7 9 3 5 5 1 
                    7 5 7 9 7 4 7 3 3 1 
                   4 6 4 5 5 8 8 3 2 4 3 
                  1 1 3 3 1 6 6 5 5 4 4 2 
                 9 9 9 2 1 9 1 9 2 9 5 7 9 
                4 3 3 7 7 9 3 6 1 3 8 8 3 7 
               3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 
              8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 
             8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 
            2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 
           7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 
          9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 
         5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 
        6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 
       2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 
      7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 
     1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 
    2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 
   7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9 
  7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6 
 5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1 
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 

其中的数字代表金属块的重量（计量单位较大）。
最下一层的X代表30台极高精度的电子秤。

假设每块原料的重量都十分精确地平均落在下方的两个金属块上，
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小，所以显示的数字很大。

工作人员发现，其中读数最小的电子秤的示数为：2086458231
请你推算出：读数最大的电子秤的示数为多少br>
注意：需要提交的是一个整数，不要填写任何多余的内容。

【分析】递推

        此题的情景有点类似杨辉三角形。

        根据题意，首先自顶向下，将a[r][c]/2后分别加到a[r+1][c]和a[r+1][c+1]上（0

        将此题中的数据（X以上的部分）作为输入，即可得到答案。

【答案】72665192664

4. 标题：方格分割
6×6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。

如图：p1.png, p2.png, p3.png 就是可行的分割法。

试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。

请提交该整数，不要填写任何多余的内容或说明文字。

【分析】搜索（DFS）

        省赛的时候看到此题有点懵，有一丢丢搜索的思路但旋转对称的判别上就gg了。。。

5. (9′)标题：取数位
求1个整数的第k位数字有很多种方法。

以下的方法就是一种。

对于题目中的测试数据，应该打印5。

请仔细分析源码，并补充划线部分所缺少的代码。

注意：只提交缺失的代码，不要填写任何已有内容或说明性的文字。

【分析】递归+数位基本操作

        每轮操作将待取数位的整数n除以10取整，直到其最后一位t为n的第k位，则t即为所求。

【答案】f(x/10,k)

6. (11′)标题：最大公共子串

最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。

比如：”abcdkkk” 和 “baabcdadabc”，
可以找到的最长的公共子串是”abcd”,所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。

【分析】DP

        这里使用动态规划法求解串s1和s2的最大公共子串长度，a[i][j]表示串s1的前i个字符组成的串和串s2的前j个字符组成的串的最大公共子串的长度。

       s1中的子串s1[0]..s1[i]匹配s2中的子串s2[0]..s2[j]，在s1[0]..s1[i-1]和s2[0]..s2[j-1]已经匹配的情况下匹配长度+1，即a[i][j]=a[i-1][j-1]+1，此方程是在s1[i]和s2[j]匹配的情况下才成立的  即s1[i]==s2[j]；

        而题目代码中给出的判断条件是if(s1[i-1]==s2[j-1])，这是因为对于一个字符串s1来说，它的子串必定”含于”s1[0]..s1[len1-1]，而a数组的下标是从1开始的，这样做的好处是不需要进行数组边界处理。试想一下，如果a数组和串s1 s2下标都从0开始，a[0][0]表示s1[0]和s2[0]匹配的情况，则在s1[0]==s2[0]的情况下必然有a[0][0]=a[0-1][0-1]+1（越界！）。解决办法即是进行数组边界处理：
if(s1[i]==s2[j]) {
 if(i==0||j==0) a[i][j]=1;
 else a[i][j]=a[i-1][j-1]+1;
}
        此外，我们对于动态规划求最优解应该有一个概念：最优解不一定要在状态中表示出来。例如在这里，我们只需要把所有子串匹配长度求出来，然后去更新最大长度就可以了。这里的状态并不是当前情况下的最优解。

#include #include #define N 256int f(const char* s1, const char* s2){ int a[N][N]; int len1 = strlen(s1); int len2 = strlen(s2); int i,j;  memset(a,0,sizeof(int)*N*N); int max = 0; for(i=1; ifor(j=1; jif(s1[i-1]==s2[j-1]) {    a[i][j] = a[i-1][j-1]+1;  //填空    if(a[i][j] > max) max = a[i][j];   }  } }  return max;}int main(){ printf("%dn", f("abcdkkk", "baabcdadabc")); //补充：  printf("%dn", f("abc","def")); 
来源：何必当初女
                                                        
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！