2020年蓝桥杯校内模拟赛复盘

校内模拟赛复盘"/>

2020年蓝桥杯校内模拟赛复盘

文章目录

• 2020年蓝桥杯校内模拟赛复盘
• • 填空题
  • • 1. `1200000` 有多少个约数？（只计算正约数）
    • • 思路
      • 代码
    • 2. 在计算机存储中，15.125GB是多少MB
    • • 思路
      • 代码
    • 3. 一棵包含有 `2019` 个结点的树，最多包含多少个叶结点
    • • 思路
      • 代码
    • 4. 在 `1` 至 `2019` 中，有多少个数的数位中包含数字 `9`
    • • 思路
      • 代码
  • 编程题
  • • 5. 给定一个数列，请问数列中有多少个元素可能是递增三元组的中心
    • • 思路1
      • 思路2
    • 6. 给定正整数 `n`，请问在整数 `1` 至 `n` 中有多少个数位递增的数
    • • 思路
      • 代码
    • 7. 特殊单词
    • • 思路
      • 代码
      • 延伸思考
    • 8. 神奇序列
    • • 思路1
      • 分析
      • 思路2
    • 9. 草地延伸
    • • 思路
      • 代码
    • 10. 好看晚会
    • • 思路
      • 代码

2020年蓝桥杯校内模拟赛复盘

全校大约40人参加本次模拟赛，成绩只排13。对于失分点在何处甚是不解，发现思路或是细节有不妥的同学欢迎前来斧正，共同进步: )

填空题

本人报的是 C/C++ 类型的比赛，在填空题时为了快速得出结果采用的是 Python。

1. 1200000 有多少个约数？（只计算正约数）

思路

本题从 [ 1 , 1200000 ] [1, 1200000] [1,1200000] 遍历即可，结果为 96。

代码

• Python

  • 法1（常规做法）

  res = 0
  for i in range(1, 1200001):if 1200000 % i == 0:res += 1
  print(res)
  

  • 法2（列表生成式）

  print(sum([1200000 % i == 0 for i in range(1, 1200001)]))
  

• C++

  #include <iostream>
  using namespace std;
  int main()
  {int res = 0;for (int i = 1; i <= 1200000; i++){if (1200000 % i == 0){res++;}}cout << res << endl;return 0;
  }
  

2. 在计算机存储中，15.125GB是多少MB

思路

根据进制换算 1 G B = 2 10 M B = 1024 M B 1GB = 2 ^ {10} MB = 1024MB 1GB=210MB=1024MB，进行简单乘法 15.125 ∗ 1024 = 15488 15.125 * 1024 = 15488 15.125∗1024=15488。

代码

#include <iostream>
using namespace std;
int main()
{cout << (15.125 * 1024) << endl;return 0;
}

3. 一棵包含有 2019 个结点的树，最多包含多少个叶结点

思路

在总结点数一定时，完全二叉树中有最多的叶子结点。
我在做题时忘了具体的计算公式，是在纸上画图算的，思路是算出每一层的二叉树结点数：

第几层	结点数
1	1
2	2
3	4
4	8
…	…
10	512

可看出当层数为 n n n 时每一层的结点数为 2 n − 1 2 ^ {n -1} 2n−1，那么前 n n n 层的结点总数为 1 + 2 + 3 + . . . + 2 n − 1 = 2 n − 1 1 + 2 + 3 + ... + 2 ^ {n - 1} = 2 ^ n - 1 1+2+3+...+2n−1=2n−1，采取快速逼近的思想，要使结点总数最接近 2019，当 n = 10 n = 10 n=10 时结点总数为 1023，与 2019 相差 996，故最后一层有 996 个结点，占用了倒数第2层 498 个结点的子结点位置，使得倒数第2层减少了 498 个叶子结点（倒数第2层总共有 512 个结点）而剩下 14 个叶子结点。所以叶子结点总共有 最后一层 996 + 倒数第2层 14 = 1010 个结点。

---

后来看到有大佬的博客提到由结点总数推出叶子结点数的公式。

太长不看版
叶子结点最多的个数与结点总数的奇偶有关，奇数个则有 n + 1 2 \frac{n + 1}{2} 2n+1​个，偶数个则有 n 2 \frac{n}{2} 2n​ 个。

具体分析：

叶子结点就是出度为 0 的结点，即没有子结点的结点。

1. 假设 n n n 为完全二叉树的结点总数， n 0 n_0 n0​ 是度为0的结点总数（即叶子结点数）， n 1 n_1 n1​ 是度为1的结点总数， n 2 n_2 n2​ 是度为2的结点总数，边数为b。

2. 由二叉树的性质可知： n = n 0 + n 1 + n 2 (1) n = n_0 + n_1 + n_2\tag{1} n=n0​+n1​+n2​(1) b = n − 1 ( 二 叉 树 是 最 小 连 通 图 ) (2) b = n - 1(二叉树是最小连通图)\tag{2} b=n−1(二叉树是最小连通图)(2)
   联立两式得 b = n 0 + n 1 + n 2 − 1 b = n_0 + n_1 + n_2 - 1 b=n0​+n1​+n2​−1
   另有 b = n 1 + 2 n 2 b = n_1 + 2n_2 b=n1​+2n2​
   则有 n 0 + n 1 + n 2 − 1 = n 1 + 2 n 2 n_0 + n_1 + n_2 - 1 = n_1 + 2n_2 n0​+n1​+n2​−1=n1​+2n2​
   即 n 2 = n 0 − 1 (3) n_2 = n_0 - 1\tag{3} n2​=n0​−1(3)

3. 将上述 (1) (3) 把 n 2 n_2 n2​ 消去可得： n = 2 n 0 + n 1 − 1 n = 2n_0 + n_1 - 1 n=2n0​+n1​−1

4. 由于完全二叉树中度为1的结点数 n 1 n_1 n1​ 只有两种可能 0 或 1：
   当 n 1 = 0 n_1 = 0 n1​=0 时 n 0 = n + 1 2 (4) n_0 = \frac{n + 1}{2}\tag{4} n0​=2n+1​(4)
   当 n 1 = 1 n_1 = 1 n1​=1 时 n 0 = n 2 (5) n_0 = \frac{n}{2}\tag{5} n0​=2n​(5)

5. 完全二叉树中除去最后一层的结点总数有 ( 2 n − 1 ) (2 ^ n - 1) (2n−1) 个，为奇数，根据完全二叉树的结点总数 n = 2019 n = 2019 n=2019 可以知道最后一层结点数为偶数（奇数 - 奇数 = 偶数），故度为1的结点数 n 1 = 0 n_1 = 0 n1​=0，利用公式 (4) 求出叶子结点数 n 0 = n + 1 2 = 2019 + 1 2 = 1010 n_0 = \frac{n + 1}{2} = \frac{2019 + 1}{2}= 1010 n0​=2n+1​=22019+1​=1010。

代码

#include <iostream>
using namespace std;
int main()
{int n = 2019;if (n % 2 == 1) //若结点总数为奇数，则n1 = 0{cout << (n + 1) / 2 << endl;}else //若结点总数为偶数，则n1 = 1{cout << n / 2 << endl;}return 0;
}

4. 在 1 至 2019 中，有多少个数的数位中包含数字 9

思路

本题从 [ 1 , 2019 ] [1, 2019] [1,2019] 遍历即可，结果为 544。

代码

• Python

  • 法1（常规做法）

  res = 0
  for num in range(1, 2020):# 在循环体内修改循环变量不会影响循环条件中的循环变量while num != 0:if num % 10 == 9:res += 1breakelse:num //= 10
  print(res)
  

  • 法2（列表生成式）

  print(sum(['9' in str(num) for num in range(1, 2020)]))
  

• C++

#include <iostream>
#include <string>
using namespace std;
int main()
{int res = 0;for (int num = 1; num <= 2019; num++){string s = to_string(num);if (s.find('9') != -1){res++;}}cout << res << endl;return 0;
}

编程题

5. 给定一个数列，请问数列中有多少个元素可能是递增三元组的中心

问题描述： 在数列 a [ 1 ] , a [ 2 ] , . . . , a [ n ] a[1], a[2], ..., a[n] a[1],a[2],...,a[n] 中，如果对于下标 i , j , k i, j, k i,j,k 满足 0 < i < j < k < n + 1 0 < i < j < k < n + 1 0<i<j<k<n+1 且 a [ i ] < a [ j ] < a [ k ] a[i] < a[j] < a[k] a[i]<a[j]<a[k]，则称 a [ i ] , a [ j ] , a [ k ] a[i], a[j], a[k] a[i],a[j],a[k] 为一组递增三元组， a [ j ] a[j] a[j] 为递增三元组的中心。

输入格式： 输入的第一行包含一个整数 n。第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，表示给定的数列。
输出格式： 输出一行包含一个整数，表示答案。

样例输入：
5
1 2 5 3 5
样例输出：
2
样例说明： a[2] 和 a[4] 可能是三元组的中心。

评测用例规模与约定： 对于 50% 的评测用例，2 <= n <= 100，0 <= 数列中的数 <= 1000。对于 所有 评测用例，2 <= n <= 1000，0 <= 数列中的数 <= 10000。

思路1

三层循环暴力遍历，时间复杂度为 O ( n 3 ) O(n ^ 3) O(n3)，在实际评测时可能会超时。

#include <iostream>
#include <set>
using namespace std;
int main()
{int n;cin >> n;int a[n];for (int i = 0; i < n; i++){cin >> a[i];}set<int> s;for (int i = 0; i < n - 2; i++){for (int j = i + 1; j < n - 1; j++){for (int k = j + 1; k < n; k++){if (a[i] < a[j] && a[j] < a[k]){/* 注意，对于[1, 2, 2, 3]之类有重复连续元素的特殊数组此处如果是s.insert(a[j])，则结果会偏小 */s.insert(j);break; // 提前结束内层循环，节省时间}}}}cout << s.size() << endl;return 0;
}

思路2

正序遍历一次数组，max 数组记录满足 a[i] < a[j](i < j) 的下标元素 j；逆序遍历一次数组，min 数组记录满足 a[j] < a[k](j < k) 的下标元素 j，最后求 max 数组和 min 数组的交集数目。时间复杂度为 O ( n ) O(n) O(n)。

#include <iostream>
using namespace std;
int main()
{int n;cin >> n;int a[n];bool max[n] = {false}, min[n] = {false};for (int i = 0; i < n; i++){cin >> a[i];}int bottom = a[0];for (int i = 1; i < n - 1; i++){if (a[i] > bottom){max[i] = true;}else if (a[i] < bottom){bottom = a[i];}}int top = a[n - 1];int res = 0;for (int i = n - 2; i >= 1; i--){if (a[i] < top){min[i] = true;}else if (a[i] > top){top = a[i];}}for (int i = 1; i < n - 1; i++){if (max[i] && min[i]){res++;}}cout << res << endl;return 0;
}

而在逆序遍历时其实已经可以直接进行比较，去掉 min 数组以及省去最后一次遍历过程，节省时间。

#include <iostream>
using namespace std;
int main()
{int n;cin >> n;int a[n];bool max[n] = {false};for (int i = 0; i < n; i++){cin >> a[i];}int bottom = a[0];for (int i = 1; i < n - 1; i++){if (a[i] > bottom){max[i] = true;}else if (a[i] < bottom){bottom = a[i];}}int top = a[n - 1];int res = 0;for (int i = n - 2; i >= 1; i--){if (a[i] < top && max[i]){res++;}else if (a[i] > top){top = a[i];}}cout << res << endl;return 0;
}

6. 给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数

问题描述： 一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。

输入格式： 输入的第一行包含一个整数 n。
输出格式： 输出一行包含一个整数，表示答案。

样例输入： 30
样例输出： 26

评测用例规模与约定： 对于 40% 的评测用例，1 <= n <= 1000。对于 80% 的评测用例，1 <= n <= 100000。对于 所有 评测用例，1 <= n <= 1000000。

思路

本题从 [ 1 , n ] [1, n] [1,n] 遍历即可。

代码

#include <iostream>
using namespace std;
int main()
{int n;cin >> n;int res = 0;for (int i = 1; i <= n; i++){int tmp = i, max = 9;while (tmp){if (tmp % 10 <= max){max = tmp % 10;}else{break;}tmp /= 10;}// 当tmp归零时说明该数已完全遍历if (tmp == 0){res++;}}cout << res << endl;return 0;
}

7. 特殊单词

问题描述： 小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。给定一个单词，请判断这个单词是否也是这种单词，如果是请输出 yes，否则请输出 no。（元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。）

输入格式： 输入一行，包含一个单词，单词中只包含小写英文字母。
输出格式： 输出答案，或者为yes，或者为no。

样例输入： lanqiao
样例输出： yes

样例输入： world
样例输出： no

评测用例规模与约定： 对于 所有 评测用例，单词中的字母个数不超过 100。

思路

因为状态只有 空 -> 辅音 -> 元音 -> 辅音 -> 元音 五种状态，状态空间并不大，所以可以由 0 到 4列举出来。

代码

#include <iostream>
#include <string>
using namespace std;// 判断是否是元音
bool isVowel(char ch)
{return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}int main()
{string word;cin >> word;int state = 0;for (int i = 0; i < word.size(); i++){if (state == 0){if (!isVowel(word[i])){state = 1;}else{break;}}else if (state == 1){if (isVowel(word[i])){state = 2;}}else if (state == 2){if (!isVowel(word[i])){state = 3;}}else if (state == 3){if (isVowel(word[i])){state = 4;}}else if (state == 4){if (!isVowel(word[i])){state = 5;break; // 已超过题目要求，继续遍历无意义，可直接退出循环}}}cout << ((state == 4) ? "yes" : "no") << endl;return 0;
}

延伸思考

原题是单词中辅音和元音状态转换 4 次，倘若改成转换 n 次，则不能一一列举，需要根据奇偶状态进行判断，将状态抽象出来。

抽象出函数如下：

bool isMatch(string word, int n)
{if (n <= 0){return false;}int state = 0;for (int i = 0; i < word.size(); i++){/*注意，空状态state = 0和元音状态 state % 2 == 0是有区别的空状态只能接辅音，而元音状态辅音元音都能接*/if (state == 0){if (!isVowel(word[i])){state++;}else{break;}}else if (state > n){break;}else{// 如果当前状态与下一个字母类型相反状态才变化if ((state % 2 == 1 && isVowel(word[i])) || (state % 2 == 0 && !isVowel(word[i]))){state++;}}}return state == n;
}

8. 神奇序列

问题描述： 小明想知道，满足以下条件的正整数序列的数量：

1. 第一项为 n；
2. 第二项不超过 n；
3. 从第三项开始，每一项小于前两项的差的绝对值。

请计算，对于给定的 n，有多少种满足条件的序列。

输入格式： 输入一行包含一个整数 n。
输出格式： 输出一个整数，表示答案。答案可能很大，请输出答案除以 10000 的余数。

样例输入： 4
样例输出： 7
样例说明：
以下是满足条件的序列：
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4

评测用例规模与约定： 对于 20% 的评测用例，1 <= n <= 5；对于 50% 的评测用例，1 <= n <= 10；对于 80% 的评测用例，1 <= n <= 100；对于 所有 评测用例，1 <= n <= 1000。

思路1

对于层层深入，我首先采用的是深度优先遍历（DFS）的算法，思路非常简单。

#include <iostream>
#include <cmath>
using namespace std;int res = 0;void DFS(int first, int second)
{for (int i = 1; i < abs(first - second); i++){res = (res + 1) % 10000;DFS(second, i);}
}int main()
{int n;cin >> n;for (int second = 1; second <= n; second++){res++;DFS(n, second);}cout << res << endl;return 0;
}

分析

对于思路1的算法，在 n 取到 30 时，耗费时间就已经是肉眼可见的慢了，对于 n 上限为 1000 的测试用例，这样的效率显然是无法接受的。

分析后猜想低效原因主要有两个，一个是调用 DFS 层数太深、次数太多，二是在前一部分搜索过的内容可能之后还会多次搜索（比如对于 131 来说，13 和 31 本质是一样的，但是前后搜索了两次）冗余程度较高。

从上面的分析可以联想到斐波那契数列（Fibonacci sequence），这两道题目有很高的相似性，想通了提高斐波那契数列时间效率对于本题或许就能迎刃而解。

斐波那契数列的定义如下：

f i b ( x ) = { 1 , x = 1 o r x = 2 f i b ( x − 1 ) + f i b ( x − 2 ) , x ≥ 2 fib(x)=\left\{ \begin{aligned} 1, \quad & x = 1 & or && x = 2\\ fib(x - 1) + fib(x - 2), \quad & {x \ge 2}\\ \end{aligned} \right. fib(x)={1,fib(x−1)+fib(x−2),​x=1x≥2​orx=2

最直接的算法依然是 DFS。

int Fibonacci(int n)
{return (n == 1 || n == 2) ? 1 : Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(40) = 102334155，这个数字已经很大了，计算速度也非常慢。

此时可以进行优化，将已经搜索过的数字保存起来。保存数字最直接想到用数组，但是 Fibonacci(n) 只与前两项有关，故用两个常量保存即可。

int Fibonacci(int n)
{if (n == 1 || n == 2){return 1;}int a = 1, b = 1;for (int i = 3; i <= n; i++){// 实现a = b, b = a + bb += a;a = b - a;}return b;
}

思路2

回到本题中来，设置二维数组v，v[first][second] 表示本位置前两个数为 first 和 second 时的序列数量。将搜索过的内容记录下来，后续需要时只需要调用即可。当 n = 1000 时得到结果比思路一要快得多。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;int DFS(vector<vector<int> > &v, int first, int second)
{int tmp = abs(first - second);if (tmp <= 1){return 0;}if (v[first][second] != 0){return v[first][second];}else{int res = 0;for (int i = 1; i < tmp; i++){res = (res + 1 + DFS(v, second, i)) % 10000;}v[first][second] = v[second][first] = res;return res;}
}int main()
{int n;cin >> n;vector<vector<int> > v(n + 1, vector<int>(n + 1, 0));int res = 0;for (int i = 1; i <= n; i++){res = (res + 1 + DFS(v, n, i)) % 10000;}cout << res << endl;return 0;
}

9. 草地延伸

问题描述： 小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

输入格式： 输入的第一行包含两个整数 n, m。接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。接下来包含一个整数 k。
输出格式： 输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

样例输入：
4 5
.g…
…
…g…
…
2
样例输出：
gggg.
gggg.
ggggg
.ggg.

**评测用例规模与约定：**对于 30% 的评测用例，2 <= n, m <= 20。对于 70% 的评测用例，2 <= n, m <= 100。对于 所有 评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

思路

广度优先遍历（BFS）一圈圈向外延展即可。

代码

#include <iostream>
#include <string>
#include <vector>using namespace std;int main()
{int n, m;cin >> n >> m;char grass[n][m];vector<pair<int, int>> v;for (int i = 0; i < n; i++){string s;cin >> s;for (int j = 0; j < m; j++){grass[i][j] = s[j];if (s[j] == 'g'){v.push_back(make_pair(i, j));}}}int k;cin >> k;// 当到达截止时间或无草可长时停止循环for (int time = 0; time < k && !v.empty(); time++){vector<pair<int, int>> next;for (vector<pair<int, int>>::iterator it = v.begin(); it != v.end(); it++){int i = it->first, j = it->second;if (i >= 1 && grass[i - 1][j] != 'g'){next.push_back(make_pair(i - 1, j));}if (i <= n - 2 && grass[i + 1][j] != 'g'){next.push_back(make_pair(i + 1, j));}if (j >= 1 && grass[i][j - 1] != 'g'){next.push_back(make_pair(i, j - 1));}if (j <= m - 2 && grass[i][j + 1] != 'g'){next.push_back(make_pair(i, j + 1));}}for (vector<pair<int, int>>::iterator it = next.begin(); it != next.end(); it++){grass[it->first][it->second] = 'g';}v = next; // 更新最外圈位置}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cout << grass[i][j];}cout << endl;}return 0;
}

10. 好看晚会

问题描述： 小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。

输入格式： 输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。第二行包含 n 个整数，依次为每个节目的好看值。
输出格式： 输出一行包含 m 个整数，为选出的节目的好看值。

样例输入：
5 3
3 1 2 5 4
样例输出：
3 5 4
样例说明： 选择了第1, 4, 5个节目。

评测用例规模与约定： 对于 30% 的评测用例，1 <= n <= 20；对于 60% 的评测用例，1 <= n <= 100；对于 所有 评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

思路

题目并不难，先将 n 个节目按好看程度排序，再将最好看的 m 个节目里按序号排序，输出前 m 个节目好看程度即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;struct node
{int number, look;// 按好看程度排序函数bool operator<(const node &y) const{if (look == y.look)return number <= y.number;return look > y.look;}
};// 最好看的m个节目里按序号排序函数
bool cmp(const node &x, const node &y)
{return x.number < y.number;
}int main()
{int n, m;cin >> n >> m;node a[n];for (int i = 0; i < n; i++){int look;cin >> look;a[i].number = i + 1;a[i].look = look;}sort(a, a + n);      // 按好看程度排序sort(a, a + m, cmp); // 最好看的m个节目里按序号排序for (int i = 0; i < m; i++){cout << a[i].look << " ";}return 0;
}