L·S
首页
时间轴
标签
分类
友链
关于
avatar
文章
30
标签
28
分类
8
首页
时间轴
标签
分类
友链
关于
目录
  1. 1. 蓝桥杯校内模拟赛
    1. 1.1. 单位变换：
    2. 1.2. 约数
    3. 1.3. 多少个数字9
    4. 1.4. 叶节点数
    5. 1.5. 数位递增的数
    6. 1.6. 元音辅音元音辅音
    7. 1.7. 递增三元组中心
    8. 1.8. 种草问题
    9. 1.9. 奇怪的数列
    10. 1.10. 组织晚会
蓝桥杯校内模拟赛
|算法与数据结构
字数总计:3.1k|阅读时长: 12 分钟
|阅读量:

蓝桥杯校内模拟赛

单位变换：

问题描述
　　在计算机存储中，15.125GB是多少MB？
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：15.125*1024=15448

约数

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

答案：暴力

96

多少个数字9

问题描述
　　在1至2019中，有多少个数的数位中包含数字9？
　　注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：（暴力）544

叶节点数

问题描述
　　一棵包含有2019个结点的树，最多包含多少个叶结点？
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：2018(一个为根节点，其他全部为子节点)；

数位递增的数

问题描述
　　一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。
　　给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？
输入格式
　　输入的第一行包含一个整数 n。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
30
样例输出
26
评测用例规模与约定
　　对于 40% 的评测用例，1 <= n <= 1000。
　　对于 80% 的评测用例，1 <= n <= 100000。
　　对于所有评测用例，1 <= n <= 1000000。

思路：模拟，使用两个变量分别记录前一个值和现在的值；

代码:

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;
bool isri(int n)
{
	int tmp1=100,tmp2=100;
	bool flag=true;
	while(n)
	{
		tmp1=n%10;
		n=n/10;
	    if(tmp1<=tmp2)
	    {
	    	tmp2=tmp1;
	    	continue;
		}
		else
		{
			tmp2=tmp1;
			flag=false;
			break;
		}
	 } 
	 return flag;
}
int main()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=10;i<=n;i++)
	{
		if(isri(i))
		{
		ans++;
	}
	}
	cout<<ans+9<<endl;//加上一位数

}

元音辅音元音辅音

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

思路：模拟，将元音辅音分别换算为1和0，然后计算顺序是否符合要求，具体见代码：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
char vowel[]={'a','e','i','o','u'};
string s;
bool is_in(char s)
{
	if(s=='a'||s=='e'||s=='i'||s=='o'||s=='u')
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	string s;
	cin>>s;
	int check[1000]={0};
	for(int i=0;i<s.length();i++)
	{
		if(is_in(s[i]))
		{
			check[i]++;
		}
	}
	int cnt=0;
	int r[1000]={0};
	int k=0;
	for(int i=1;i<s.length();i++)
	{
		if(check[i]==1&&check[i-1]==0)
		{
			cnt++;
			r[k]=1;
			k++;
		}
		if(check[i]==0&&check[i-1]==1)
		{
			cnt++;
			r[k]=-1;
			k++;
		}
	}
	if(cnt==3&&r[0]==1&&r[1]==-1&&r[2]==1)
	{
		cout<<"yes"<<endl;
	}
	else
	{
		cout<<"no"<<endl;
	}
}

递增三元组中心

问题描述
　　在数列 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。

思路：可以使用双指针法，一个指针从前向后指向最小的值，另一个指针依次向后遍历，如果指针二后面存在>指针二的值ans++，如果指针二小于指针一，则将指针二设为指针一。

代码：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int a[1001];
int n;
bool maxa(int t)
{
	for(int i=t+1;i<n;i++)
	{
		if(a[i]>a[t])
		{
			return true;
		}
	}
	return false;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int minn=a[0];
	int ans=0;
	for(int i=1;i<n;i++)
	{
		if(a[i]>minn&&maxa(i))
		{
			ans++;
		}
		else if(a[i]<minn)
		{
			minn=a[i];
		}
		else
		{
			continue;
		}
	}
	cout<<ans<<endl;
}

种草问题

题目：

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

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

输出格式：
输出n行，每行包含m个字母，表示k个月后空地的状态。如果为小数点，表示为空地，如果字母为g表示长了草。

样例输入：

4 5
.g…
…..
…g.
…..
2

样例输出：

gggg.
ggggg
.gggg
..ggg

典型的bfs类型题，一次一次的累积向周边扩展，需要注意的是每次bfs结束的条件是当前种子区域的值。

代码：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<string.h>
#include<queue >
#define MAX 1001
using namespace std;
char map[MAX][MAX];
int vis[MAX][MAX]={0};
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
int n,m;
struct node{
	int x,y;
	node(int a,int b)
	{
		x=a;
		y=b;
	}
};
queue<node> q;	
int bfs(int t)
{
	int time=0;
	while(!q.empty()&&t--)
	{
		node a=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int tmpx=a.x+dir[i][0];
			int tmpy=a.y+dir[i][1];
			if(tmpx>=0&&tmpx<n&&tmpy>=0&&tmpy<m&&vis[tmpx][tmpy]==0)
			{
				vis[tmpx][tmpy]=1;
				q.push(node(tmpx,tmpy));
				map[tmpx][tmpy]='g';
			    time++;
			}
		}
	}
	return time;
}
int main()
{ 
	int t=0;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='g')
			{
				t++;
				vis[i][j]=1;
				q.push(node(i,j));
			}
		}
	}
	int num=0;
	int k;
	cin>>k;
	while(k--)
	{
	t=bfs(t);
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cout<<map[i][j];
		}
		cout<<endl;
	}
	return 0;
}

奇怪的数列

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

  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。

　　思路：
　　
　　此题应该是在考察dp，但我是在没有想到什么好的dp思路，于是在网上参考了别人的博客发现也没有太好的dp思路，于是d把fs+剪枝，改成dp数组记录。估计只能通过50%；

​ 代码：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include<math.h>
using namespace std;
const int N = 1001;
vector< vector<int> > dp(N, vector<int>(N, -1));

int countSeq(int first, int second)
{
    if (dp[first][second] != -1)
        return dp[first][second];
    int t = 1;
    for (int i = 1; i < abs(first - second); i++)
    {
        t += countSeq(second, i);
    }
    dp[first][second] = t % 10000;
    return dp[first][second];
}
int main()
{
    int n, ans(0);
    cin >> n;
    dp[1][1] = 1;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + countSeq(n, i)) % 10000;
    }
    cout << ans << endl;
    return 0;
}

组织晚会

问题描述
　　小明要组织一台晚会，总共准备了 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。

思路：两次自定义cmp的sort；

代码：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<math.h>
#include<algorithm>
#define MAX 100001
using namespace std;
struct node{
	int que;
	int val;
};
node a[MAX];
bool cmp1(node a,node b)
{
	return a.val>b.val;
}
bool cmp2(node a,node b)
{
	return a.que<b.que;
}
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].val;
		a[i].que=i;
	}
	sort(a,a+n,cmp1);
	sort(a,a+k,cmp2);
	for(int i=0;i<k;i++)
	{
		cout<<a[i].val<<" ";
	}
	cout<<endl;
	return 0;
}
文章作者: Liang Shuo
文章链接: http://yoursite.com/2020/03/24/%E8%93%9D%E6%A1%A5%E6%9D%AF%E6%A0%A1%E5%86%85%E6%A8%A1%E6%8B%9F%E8%B5%9B/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 L·S！
蓝桥杯
打赏
  • 微信
    微信
  • 支付宝
    支付宝
评论
繁