写在前面：

Long time no see, R U OK?😄 因为疫情原因 蓝桥杯推迟举办了，所以官网发布公告：①开放练习系统VIP权限；②举办模拟考试；③开放蓝桥杯历届真题微课。今天下午这个是校内模拟赛。好久都没有写代码和博客了，我最近在刷《高数18讲》然后做《接力题典1800》还有复习《李永乐复习全书》的线代部分。头铁就完事了，冲冲冲！下面简单地记录我做这套模拟题的解题思路。（还没出成绩，不能保证我的代码和答案的正确性，只是简单记录一下个人的解题思路。提交之后发现没有题目描述和测试样例了，于是呼叫我的宝贝憨憨帮忙。）

填空题：

（官网描述）这些结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

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

解题思路：编写代码计算可以得到结果——96

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n = 1200000,cnt = 0;for(int i = 1; i*i <= n; i++){if(n%i==0) cnt+=2;}cout << cnt << endl;return 0;
}

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

解题思路：编写代码计算可以得到结果——15488

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);double n = 15.125;cout << (n*1024) << endl;return 0;
}

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

这题我测试的时候算错了，我当时写的是1009，交卷之后我的憨憨说答案是1010。

解题思路：叶结点就是出度为0的结点，即没有子结点的结点。

①假设n为完全二叉树的结点总数，n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数。

②由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2。

③将上述公式把n2消去可得：n= 2n0+n1-1。

④由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n＋1)/2或n0=n/2。

⑤题目要算的是最多的叶子结点数，根据完全二叉树的结点总数n=2019可以计算出叶子结点数n0=(n+1)/2=1010。

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

（注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。）

解题思路：编写代码计算可以得到结果——544

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n = 2019,cnt = 0;for(int i = 1; i <= n; i++){stringstream ss; ss << i;string str;ss >> str;for(int j = 0; j < str.length(); j++){if(str[j]=='9'){cnt++;break;}}}cout << cnt << endl;return 0;
}

编程题：

5、问题描述：一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？

输入格式：输入的第一行包含一个整数 n。

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

样例输入：

30

样例输出：

26

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

解题思路：

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n, cnt = 0;cin >> n;for (int i = 1; i <= n; i++){stringstream ss; ss << i;string str;ss >> str;int t = str[0];bool flag = true;for(int j = 0; j < str.length(); j++){if(str[j]>=t){t = str[j];}else{flag = false;break;}}if(flag) cnt++;}cout << cnt << endl;return 0;
}

6、问题描述：在数列 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;
const int maxn = 10001;int a[maxn];int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);memset(a,0,sizeof(a));int n;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}set<int> s;   //递增三元组的中心for(int i = 1; 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]){s.insert(a[j]);}}}}int ans = s.size();cout << ans << endl;return 0;
}

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

输入格式：输入一行，包含一个单词，单词中只包含小写英文字母。

输出格式：输出答案，或者为yes，或者为no。

样例输入：

lanqiao

样例输出：

yes

样例输入：

world

样例输出：

no

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

解题思路：感觉这题写到最后有点凌乱了，或许用个hash来记录第一段第二段第三段第四段的字母个数更好。

#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);set<char> s;   //用来存放元音字母s.insert('a'),s.insert('e'),s.insert('i'),s.insert('o'),s.insert('u');string str;getline(cin,str);bool ans = true;int n = str.length();int a[n];memset(a,-1,sizeof(a));for(int i = 0; i < str.length(); i++){//第一段由一个或多个辅音字母组成while(s.count(str[i])==0){a[i] = 1;i++;}//第二段由一个或多个元音字母组成while(s.count(str[i])==1){a[i] = 2;i++;}//第三段由一个或多个辅音字母组成while(s.count(str[i])==0){a[i] = 3;i++;}//第四段由一个或多个元音字母组成while(s.count(str[i])==1){a[i] = 4;i++;}break;}for(int i = 0; i < n-1; i++){if(a[i]>a[i+1]){ans = false;break;}}if(a[0]!=1||a[n-1]!=4) ans = false;cout << (ans?"yes":"no") << endl;return 0;
}

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。

解题思路：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1001;int a[maxn][maxn];int fun(int x,int y)
{if(a[x][y]!=0) return a[x][y];for(int i = abs(x-y)-1; i >= 0; i--){a[x][y] += fun(y,i);}a[y][x] = a[x][y];return a[x][y];
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n,cnt = 0;cin >> n;memset(a,0,sizeof(a));for(int i = 1; i <= n; i++){a[i][i] = 1;a[i][0] = 1;a[0][i] = 1;}for(int i = 1; i <= n; i++){cnt += fun(n,i);cnt %= 10000;}cout << cnt << 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。

解题思路：dfs就完事了，在存储空地状况的时候我把这个'.'和'g'分别替换成了0和1，即空地0有草1。然后用pair记录下了空地初始状态有草的点（pair的first是横坐标，second是纵坐标），然后对有草的点进行dfs，这里我用了一个(a,b)来表示有草的点的上下左右，一开始也想用pair记录后来觉得用俩个数组会更方便，当(x,y)上下左右的点(newx,newy)仍在空地范围内时继续深度优先搜索，当k小于0时结束深度优先搜索。最后将空地状态输出即可（输出的时候记得把0、1换回'0','g'）。

#include <bits/stdc++.h>
using namespace std;
#define P pair<int,int>
#define mp(x,y) make_pair(x,y)
const int maxn = 1024;int n,m;  //n行m列
int G[maxn][maxn];   //0空地,1有草
int a[4] = {0,0,-1,1};
int b[4] = {1,-1,0,0};
//(a,b)分别为上下左右void dfs(int x,int y,int k)   //k个月后空地的状态
{if(k < 0) return;G[x][y] = 1;  //给爷长草for(int i = 0; i < 4; i++){int newx = x+a[i];int newy = y+b[i];if(newx>=1 && newx<=n && newy>=1 && newy<=m){dfs(newx,newy,k-1);}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);memset(G,0,sizeof(G));cin >> n >> m;vector<P> v;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){char c;cin >> c;if(c == 'g'){G[i][j] = 1;v.push_back(mp(i,j));}}}int k;   //k个月后空地的状态cin >> k;for(int i = 0; i < v.size(); i++){dfs(v[i].first,v[i].second,k);}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cout << (G[i][j]==0?'.':'g');}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。

解题思路：用俩个vector来解决，其中一个是原始序列v、另一个是降序排列后的序列order。将order中的前m个数insert到set中，然后再对v进行无脑遍历来输出set中的元素，即按照原始序列输出前m个分高的节目。

#include <bits/stdc++.h>
using namespace std;vector<int> v,order;  //原始序列v,出场顺序orderint main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n,m;   //节目数n,要选择m个cin >> n >> m;for(int i = 1; i <= n; i++){int _;cin >> _;v.push_back(_);order.push_back(_);}sort(order.begin(),order.end(),greater<int>());  //降序排列set<int> s;for(int i = 0; i < m; i++){s.insert(order[i]);}bool virgin = true;for(int i = 0; i < n; i++){if(s.count(v[i])==1){cout << (virgin?"":" ") << v[i];virgin = false;}}return 0;
}