第十一届蓝桥杯大赛第一次模拟（软件类）真题（2020年3月，C++描述）

谁践踏了优雅 2022-11-27 10:10 229阅读 0赞

### 第一次模拟 ###

*  T1：15.125GB
 *  T2：约数个数
 *  T3：叶节点数
 *  T4：数字9
 *  T5：数位递增的数
 *  T6：递增三元组
 *  T7：音节判断
 *  T8：长草
 *  T9：序列计数
 *  T10：晚会节目单

# T1：15.125GB #

【问题描述】  
在计算机存储中，15.125GB是多少MB？

思路分析：1GB为1024MB，15.125\*1024=15488。  
答案：15488

# T2：约数个数 #

【问题描述】  
1200000有多少个约数（只计算正约数）？

思路分析：1200000不是很大，直接从1开始遍历并判断是否是约数即可。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const long long cons = 1200000;
    
    int main() { 
    	int res = 0;
    	for(long long  i = 1; i <= 1200000; ++i) { 
    		if(cons % i == 0) { 
    			res++;
    		}
    	}
    	cout<<res;
    	return 0;
    }

答案：96

# T3：叶节点数 #

【问题描述】  
一棵包含有2019个结点的二叉树，最多包含多少个叶结点？

思路分析：我们知道二叉树的结点数满足：

n0 = n2 + 1

其中n0表示叶子结点个数，n2表示度为2结点的个数。要想n0最大，那么显然n2需要最大。那显然当二叉树中没有度为1的结点的时候n2最大。即：

n0 + n2 = 2019

联立解得：

n0 = 1010

答案：1010

# T4：数字9 #

【问题描述】  
在1至2019中，有多少个数的数位中包含数字9？  
注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。

思路分析：循环判断每个数是否含有9即可。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    bool check(int x) { 
    	while(x) { 
    		if(x % 10 == 9) { 
    			return true;
    		}
    		x /= 10;
    	}
    	return false;
    } 
    
    int main() { 
    	int res = 0;
    	for(int i = 1; i <= 2019; i++) { 
    		if(check(i)) { 
    			res++;
    		}
    	}
    	cout<<res;
    	return 0;
    }

答案：544

# T5：数位递增的数 #

【问题描述】  
一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。  
给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？  
【输入格式】  
输入的第一行包含一个整数 n。  
【输出格式】  
输出一行包含一个整数，表示答案。  
【样例输入】  
30  
【样例输出】  
26  
【评测用例规模与约定】  
对于 40% 的评测用例，1 <= n <= 1000。  
对于 80% 的评测用例，1 <= n <= 100000。  
对于所有评测用例，1 <= n <= 1000000。  
  
思路分析：数据不是很大，直接暴力就好了。习惯把数字变成string来处理。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    long long n;
    
    bool check(int x) { 
    	stringstream ss;
    	string str;
    	ss << x;
    	ss >> str;
    	for(int i = 1;i < str.length(); i++) { 
    		if(str[i] < str[i-1]) { 
    			return false;
    		}
    	}
    	return true;
    }
    
    int main() { 
    	cin >> n;
    	int res = 0;
    	for(int i = 1;i <= n ;i++) { 
    		if(check(i)) { 
    			res++;
    		}
    	}
    	cout<<res;
    	return 0;
    }

# T6：递增三元组 #

【问题描述】  
在数列 a\[1\], a\[2\], …, a\[n\] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a\[i\]<a\[j\]<a\[k\]，则称 a\[i\], a\[j\], a\[k\] 为一组递增三元组，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。

思路分析：遍历数组，一个数要想成为递增三元组的中心，那么在它左边至少要有一个比它小的数，右边要有一个比它大的数。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    int a[1005], n;
    
    int main() { 
    	int res = 0;
    	cin >> n;
    	for(int i = 0; i < n; i++) { 
    		cin >> a[i];
    	}
    	for(int i = 1; i < n - 1; i++) { 
    		
    		int flag1 = 0, flag2 = 0;
    		
    		for(int j = 0; j < i; j++) { 
    			if(a[j] < a[i]) { 
    				flag1 = 1;
    				break;
    			}
    		}
    		
    		for(int j = i + 1; j < n; j++) { 
    			if(a[j] > a[i]) { 
    				flag2 = 1;
    				break;
    			}
    		}
    		
    		if(flag1 && flag2) { 
    			res++;
    		}
    	}
    	cout<<res;
    	return 0;
    }

# T7：音节判断 #

【问题描述】  
  小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。  
  给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。  
  元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。  
【输入格式】  
输入一行，包含一个单词，单词中只包含小写英文字母。  
【输出格式】  
输出答案，或者为yes，或者为no。  
【样例输入】  
lanqiao  
【样例输出】  
yes  
【样例输入】  
world  
【样例输出】  
no  
【评测用例规模与约定】  
对于所有评测用例，单词中的字母个数不超过100。

思路分析：初始化一个字符串长度的整形数组，如果字符串某个位置为元音字母，则整型数组该位置为1，否则为0。然后遍历整形数组：**首先遍历直到不为0时停下，接着遍历直到不为1时停下，然后重复上述两个操作。如果最后位置指针落在最后一位，说明满足条件，否则不满足条件。**

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    string seq = "aeiou";
    int a[100] = { 0}; 
    
    int main() { 
    	string str;
    	cin >> str;
    	for(int i = 0; i< str.length(); i++) { 
    		if(seq.find(str[i]) != -1) { 
    			a[i] = 1;
    		}
    	}
    	if(a[0] == 1) { 
    		cout << "no";
    		return 0;
    	}
    	int i = 1;
    	while(a[i] == 0) { 
    		i++;
    	}
    	while(a[i] == 1) { 
    		i++;
    	}
    	while(a[i] == 0) { 
    		i++;
    	}
    	while(a[i] == 1 && i < str.length()) { 
    		i++;
    	}
    	if(i == str.length()) { 
    		cout << "yes";
    	}else { 
    		cout << "no";
    	}
    	return 0;
    }

# T8：长草 #

【问题描述】  
  小明有一块空地，他将这块空地划分为 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。** 我们初始化一个结构体，包含坐标以及月份数，即该草是第几个月长出来。初始时我们把长草的坐标以及月份（0）初始化为一个结点然后入队。当队不为空，我们得到队头结点，如果当前月份不是k，那么就把它四周的结点都长草然后入队（或者出队时长草），**如果当前月份就是k那么就啥也不做，因为它已经是第k个月长出来的了，队列一定有队空的时候，队空就结束。**

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    int n, m, k;
    const int maxn = 1e6 + 5;
    string mat[1005];
    
    struct grass { 
    	int x;
    	int y;
    	int month;
    	grass(){ }
    	grass(int x, int y, int month) { 
    		this->x = x;
    		this->y = y;
    		this->month = month;
    	}
    	
    };
    
    queue<grass*> q;
    int dir[4][2] = { { 0, 1}, { 0, -1}, { 1, 0}, { -1, 0}};
    bool in(int x, int y) { 
    	return x >= 0 && x < n && y >= 0 && y < m;
    }
    
    int main() { 
    	cin >> n >> m;
    	for(int i = 0; i < n ;i++) { 
    		cin >> mat[i];
    		for(int j = 0; j < m; j++) { 
    			if(mat[i][j] == 'g') { 
    				grass* temp = new grass(i, j, 0);
    				q.push(temp);
    			}
    		}
    	}
    	cin >> k;
    	while(!q.empty()) { 
    		grass* temp = q.front();
    		mat[temp->x][temp->y] = 'g';
    		q.pop();
    		if(temp->month != k) { 
    			for(int i = 0; i < 4; i++) { 
    				int x = temp->x + dir[i][0];
    				int y = temp->y + dir[i][1];
    				if(in(x, y)) { 
    					grass* temp_1 = new grass(x, y, temp->month + 1);
    				    q.push(temp_1);
    				}
    				
    			}
    		}
    	}
    	for(int i = 0; i < n; i++) { 
    		cout << mat[i] << endl;
    	}
    	return 0;
    }

# T9：序列计数 #

【问题描述】  
小明想知道，满足以下条件的正整数序列的数量：  
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。  
  
思路分析：“从第三项开始，每一项小于前两项的差二等绝对值”，从这句话很容易想到用递归，有点类似求最长公共子序列长度那题了。但是我还是没有好的思路。。。。

# T10：晚会节目单 #

【问题描述】  
小明要组织一台晚会，总共准备了 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个数，并按照原先的顺序输出。** 我的思路是定义一个结构体，结构体包含两个变量：序号以及权值。我们首先对输入后的结构体数组按照权值从大到小排序，这样权值最大的就在第一个，但是它的序号大概率不是0；然后再对结构体数组的前m个最大的数按照序号从小大到大进行二轮排序，这样我们要输出的m个最大的数就按照序号从小到大排好了，然后依次输出就好了。但显然并不是这样，等我学会了线段树再补上。