[C++知识库]2018年 第九届 蓝桥杯省赛 C/C++ B 组

前言：感觉这年的题目除了第一题 都有点难度的

一、填空题

1.第几天

2000 年的 1 月 1 日，是那一年的第 11 天。

那么，2000 年的 5 月 4 日，是那一年的第几天？
答案:125

#include <iostream>
using namespace std;
int main()
{
  cout<<31 + 29 + 31 + 30 + 4;
  return 0;
}

2.明码

4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 
16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16 
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 
0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4 
4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64 
16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128 
0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0 
2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0 
1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0 
0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0 

答案:
解析：就是需要将每个数字转为8进制，每两个数为一行，一行就是16个点，那一位为1就是有墨迹，0就是没有。转8位2进制的话有特殊函数
头文件为：
用法：

• bitset<8> b(n); //就把n转化为 8 位2进制数据存到了 b 中
• bitset<16> b(n); //就把n转化为16位2 进制数据存到了 b 中
• str1 = b.to_string(); //转为字符串

代码转载:作者：广海_小疯疯丶

#include <bitset>
#include <iostream> 
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
    int n,m;
    string str1, str2;
    while(cin >> n >> m){
        bitset<8> b(n);
        str1 = b.to_string();
        int len1 = str1.length();
        for(int i = 0;i < len1; i++){
          if(str1[i] == '0') printf(" ");
          else printf("*");
        }
        bitset<8> c(m);
        str2 = c.to_string();
        int len2 = str2.length();
        for(int i = 0;i < len2; i ++){
          if(str2[i] == '0') printf(" ");
          else printf("*");
        }
        printf("\n");
    }
    return 0;
}

3.乘积尾零

如下的 10 行数据，每行有 10 个整数，请你求出它们的乘积的末尾有多少个零？

5650 4542 3554 473 946 4114 3871 9073 90 4329 
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 
1486 5722 3135 1170 4014 5510 5120 729 2880 9019 
2049 698 4582 4346 4427 646 9742 7340 1230 7683 
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 
6701 6645 1671 5978 2704 9926 295 3125 3878 6785 
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 
689 5510 8243 6114 337 4096 8199 7313 3685 211 

答案:31
解析：这个看了题解才知道，有个两数相乘尾数为0的话，那只能是2和 5 相乘。举个例子
6 * 40 = 2 * 3 * 2 * 2 * 5 *2 = 240（只有一个 5 所以只有一对5 和 2相乘 那么也只有一个零）
5 * 20 = 5 * 2 * 2 * 5 = 100 （有两对匹配，所以有两个零）
所以，我们求出这些数中5 和 2的个数，然后去小的那个个数，就是0的个数

#include <iostream>
using namespace std;
  int x;
  int num2,num5;
  int min(int a, int b)
  {
    return a > b ? b : a;
  }
int main()
{
  for(int i = 0; i < 100; i ++)
  {
    scanf("%d",&x);
    while(x % 5 == 0) //查看几个5
    {
      num5 ++;
      x /= 5;
    }
    while(x % 2 == 0) //查看几个2
    {
      num2 ++;
      x /= 2;
    }
      
  }
 cout << min(num2, num5);
  return 0;
}

4.测试次数

答案:19
解析：难度有点高，可能题目我都看懵了
代码转载自测试次数（动态规划）作者：Stephencurry‘s csdn

#include <iostream>
#include <cstdio>
using namespace std;
int dp[5][1005];
void solve(int phone,int floor)
{
    for(int i=1;i<=phone;i++)
        for(int j=1;j<=floor;j++)
    {
        dp[i][j]=j; //i部手机在j层摔坏的最坏次数为j次
    }
    for(int i=2;i<=phone;i++) //有i部手机
        for(int j=1;j<=floor;j++)//当楼只有j层时
            for(int k=1;k<j;k++)//手机可能从第k层摔下
            {                    //摔碎了i-1部手机在 k - 1层中测试  
                                //没摔碎 i 部手机在 j - k测试(就是 k + 1 到 j 层中测试)
                dp[i][j]=min( dp[i][j], max(dp[i-1][k-1],dp[i][j-k]) + 1);
            }
}
int main()
{
    solve(3,1000);
    printf("%d\n",dp[3][1000]);
    return 0;
}

二、代码填空

5.快速排序

答案 ： a,i+1,r,(k-(i-l+1))
解答看 E题：快速排序 作者:lily*-*

三、程序题

6.递增三元组

输入数据

3
1 1 1
2 2 2
3 3 3

输出

27

解析：三层循环，就超时了，那就两层循环，找出a中比b小的数，找出c中比b大的数，然后相乘，加起来。
还有一种前缀和的做法递增三元组

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
int n;
int main()
{
  cin >> n;
    for(int j = 1; j <= n; j ++) scanf("%d",&a[j]);
    for(int j = 1; j <= n; j ++) scanf("%d",&b[j]);
    for(int j = 1; j <= n; j ++) scanf("%d",&c[j]);
  sort(a + 1, a + n + 1);
  sort(b + 1, b + n + 1);
  sort(c + 1, c + n + 1);
  int i = 1, k = 1;
  long long res = 0;
    for(int j = 1; j <= n; j ++)
      {
        while(i <= n && a[i] < b[j]) i ++;
        while(k <= n && b[j] >= c[k]) k ++;
        res +=  (long long)(i - 1) * (n - k + 1);
        //这里还得转化为long long 不然也会错
      }
  cout <<res;
  return 0;
}

7.螺旋折线

跳转–> 1237. 螺旋折线

8.日志统计

跳转–> 1238. 日志统计

9.全球变暖

跳转–> 1233. 全球变暖

10.乘积最大

跳转–> 1239. 乘积最大