非编程题就不看了，都是水题！

5、递增三元组

问题描述

在数列 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]，相邻的整数间用空格分隔，表示给定的数列。

输出格式

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

样例输入

1
2
5
1 2 5 3 5

样例输出

1
2

样例说明

a[2] 和 a[4] 可能是三元组的中心。

评测用例规模与约定

对于 50% 的评测用例，2 <= n <= 100，0 <= 数列中的数 <= 1000。

对于所有评测用例，2 <= n <= 1000，0 <= 数列中的数 <= 10000。

题解一：暴力题解（或许超时）

可以跨元素，并不是只能是挨着的三个！

前面可以用最小值来找，后面直接循环一遍即可！

我竟然没发现后面也可以存到数组去实现当前位置到最后元素的最大值！

参考题解二！

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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int a[N], n;

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];

	int mina = a[1], res = 0;
	for(int j = 2; j <= n - 1; j++)
	{
		bool flag1 = false, flag2 = false;
		mina = min(mina, a[j]);
		if(mina < a[j]) flag1 = true;
		for(int k = j + 1; k <= n; k++)
			if(a[j] < a[k])
			{
				flag2 = true;
				break;
			}
		if(flag1 && flag2) res ++;
	}
	cout << res << endl;
	return 0;
}

题解二：维护两个最大最小值数组

先线性扫描维护两个数组！

最小值数组，起点到当前位置的最小值；

最大值数组，终点到当前位置的最大值。

  • 从前往后维护一个最小值数组

  • 从后往前维护一个最大值数组

  • 时间复杂度: O(N)

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
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1010;
int a[N], n, small[N], big[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    small[1] = a[1], big[n] = a[n];
    for (int i = 2; i <= n; i++)
        if (a[i] < small[i - 1])
            small[i] = a[i];
        else
            small[i] = small[i - 1];

    for (int i = n - 1; i >= 1; i--)
        if (a[i] > big[i + 1])
            big[i] = a[i];
        else
            big[i] = big[i + 1];

    int res = 0;
    for (int i = 2; i <= n - 1; i++)
        if (small[i - 1] < a[i] && a[i] < big[i + 1])
            res++;
    cout << res << endl;
    return 0;
}

6、数位递增逆序数

问题描述

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

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

输入格式

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

输出格式

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

样例输入

1
30

样例输出

1
26

评测用例规模与约定

对于 40% 的评测用例，1 <= n <= 1000。

对于 80% 的评测用例，1 <= n <= 100000。

对于所有评测用例，1 <= n <= 1000000。

题解：直接扫描一遍即可

判断时可以用两个指针指向一前一后，进行判断即可！

具体看代码实现！

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
#include <iostream>
#include <algorithm>

using namespace std;

int n, sum;

void solve(int x)
{
	int next = 0x3f, pre;
	bool flag = true;
	while(x)
	{
		int pre = x % 10;
		x /= 10;
		if(pre > next)
		{
			flag = false;
			break;
		}
		next = pre;
	}
	if(flag) sum ++;
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) solve(i);

	cout << sum << endl;
	return 0;
}

7、元音辅音

问题描述

小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。

给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。

元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。

输入格式

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

输出格式

输出答案，或者为yes，或者为no。

样例输入

1
lanqiao

样例输出

1
yes

样例输入

1
world

样例输出

1
no

评测用例规模与约定

对于所有评测用例，单词中的字母个数不超过100。

题解：扫描一遍即可！

保证是辅音、元音、辅音、元音的顺序即可，并且只出现这四段，顺序也一样，多一段都不行！

直接while去循环直到元辅音出现变化结束即可！

使用flag可以控制他进入的顺序。。。

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
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int n, sum;
string str;
int fuyin, yuanyin, flag;

int main()
{
	cin >> str;

	for(int i = 0; i < str.size();)
	{
		if(!flag)//辅音
		{
			flag = 1;
			bool flag1 = false;
			while(str[i] != 'a' &&  str[i] != 'e' && str[i] != 'i' && str[i] != 'o' && str[i] != 'u')
			{
				flag1 = true;
				i ++;
			}
			if(!flag1)
			{
				cout << "no" << endl;
				return 0;
			}
			fuyin ++;
		}
		else//元音
		{
			flag = 0;
			bool flag2 = false;
			while(str[i] == 'a' ||  str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u')
			{
				flag2 = true;
				i ++;
			}
			if(!flag2)
			{
				cout << "no" << endl;
				return 0;
			}
			yuanyin ++;
		}
	}

	if(fuyin == 2 && yuanyin == 2) cout << "yes" << endl;
	else cout << "no" << endl;
	return 0;
}

8、长草

问题描述

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。

请告诉小明，k 个月后空地上哪些地方有草。

输入格式

输入的第一行包含两个整数 n, m。

接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。

接下来包含一个整数 k。

输出格式

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

样例输入

1
2
3
4
5
6
7
8
9
10
11
4 5

.g...

.....

..g..

.....

2

样例输出

1
2
3
4
5
6
7
gggg.

gggg.

ggggg

.ggg.

评测用例规模与约定

对于 30% 的评测用例，2 <= n, m <= 20。

对于 70% 的评测用例，2 <= n, m <= 100。

对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

题解一：直接循环k个月

先将有草的地方存起来，再去循环k个月，每次循环都将起点置为上一次的终点，可以有效减少扫描次数，每个月都去扫描上一次新增加的地方！

貌似不会超时！

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
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
typedef pair<int, int> PII;

int n, m, k, r;
string str[N];
PII T[N * N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

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 >> str[i];
		for(int j = 0; j < m; j++)
			if(str[i][j] == 'g') T[r++] = {i, j};
	}
	cin >> k;

	int t = 0, s;
	while(k--)
	{
		s = t, t = r;
		for(int i = s; i < t; i++)
		{
			for(int j = 0; j < 4; j++)
			{
				int tx = T[i].first + dx[j], ty = T[i].second + dy[j];
				if(in(tx, ty) && str[tx][ty] != 'g') str[tx][ty] = 'g', T[r++] = {tx, ty};
			}
		}
	}

	for(int i = 0; i < n; i++) cout << str[i] << endl;

	return 0;
}

题解二：使用BFS

貌似和上面解法没区别，复杂度我认为也没什么区别。。。

第二层while循环循环上一次新增加的地方，即队列的大小，内循环结束一次，上一次队列存储的值就会清空一次，然后当前队列存储的就是本月新增的地方，外循环循环月份即可！

可能会发生某个月份长草时，已经全部长满了，则直接退出即可，即外循环增加一个非空判断条件即可！

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
// 使用BFS
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
typedef pair<int, int> PII;

int n, m, k, r;
string str[N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool in(int x, int y)
{
	return x >= 0 && x < n && y >= 0 && y < m;
}

queue<PII> q;

int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> str[i];
		for(int j = 0; j < m; j++)
			if(str[i][j] == 'g') q.push({i, j});
	}
	cin >> k;

	while(!q.empty() && k--)
	{
		int len = q.size();
		while(len--)
		{
			PII now = q.front(); q.pop();
			for (int i = 0; i < 4; i++)
			{
				int tx = now.first + dx[i], ty = now.second + dy[i];
				if(in(tx, ty) && str[tx][ty] != 'g')
				{
					str[tx][ty] = 'g';
					q.push({tx, ty});
				}
			}
		}
	}

	for(int i = 0; i < n; i++) cout << str[i] << endl;

	return 0;
}

9、序列数

问题描述

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

1. 第一项为 n；

2. 第二项不超过 n；

3. 从第三项开始，每一项小于前两项的差的绝对值。

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

输入格式

输入一行包含一个整数 n。

输出格式

输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。

样例输入

1
4

样例输出

1
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。

题解：DFS(暴力TLE)

直接DFS最多只能算到20几的数字，但本题数据范围为1000。。。

可以暴力跑一遍所有数组，存储起来，打表输出O(1)即可。。。

正确做法或许是记忆化搜索，动态规划之类。。。

就这样吧，打表或许是最好的选择！

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
#include <iostream>
#include <algorithm>
#define mod 10000

using namespace std;

int n, ans;

void dfs(int pre, int next)
{
	ans = (ans + 1) % mod;

	if(abs(pre - next) <= 1) return;

	for (int i = 1; i < abs(pre - next); i++) dfs(next, i);
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++) dfs(n, i);

	cout << ans << endl;

	return 0;
}

10、选节目

问题描述

小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。

这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。

小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。

小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。

输入格式

输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。

第二行包含 n 个整数，依次为每个节目的好看值。

输出格式

输出一行包含 m 个整数，为选出的节目的好看值。

样例输入

1
2
3
5 3

3 1 2 5 4

样例输出

1
3 5 4

样例说明

选择了第1, 4, 5个节目。

评测用例规模与约定

对于 30% 的评测用例，1 <= n <= 20；

对于 60% 的评测用例，1 <= n <= 100；

对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

题解：似乎不太对

简单的觉得先按好看值从大到小排序，再按序号从小到大排序即可！

似乎不是这么简单！

听说用到了好多算法。。。

放过，再说吧！

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100000;


struct Node
{
	int point, pos;
};

bool cmp(Node x, Node y)
{
	return x.point > y.point;
}

bool cmp1(Node x, Node y)
{
	return x.pos < y.pos;
}

int n, m;
Node a[N];

int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> a[i].point, a[i].pos = i;

	sort(a, a + n, cmp);
	sort(a, a + m, cmp1);

	for(int i = 0; i < m; i++) cout << a[i].point << " ";

	return 0;
}

记录一下这垃圾的蓝桥杯校赛！