CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/35

第二十一期竞赛题目

一、合并序列

1、题目描述

  有 $N$ 个单词和字符串 $T$，按字典序输出以字符串 $T$ 为前缀的所有单词。

• 输入描述： 第一行输入整数 $N$，接下来 $N$ 行，每行输入一个单词，长度不超过100，最后一行输入字符串 $T$。（所有字符均为小写字母）
• 输出描述： 按字典序升序输出答案。

示例：

输入：6
   na
   no
   ki
   ki
   ka
   ku
   k
输出：ka
   ki
   ki
   ku

2、代码实现

解题步骤如下：

1. 遍历输入的字符串，依次判断其是否以字符串T为前缀，判断时进行逐个字符比较即可。
2. 将以字符串T为前缀的字符串按字典序进行升序排序。

代码如下：

//合并序列
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
//判断字符串str是否以字符串T为前缀
bool Judge(const string& str, const string& pre)
{
	if (str.size() < pre.size())
		return false;
	size_t i = 0;
	while (i < pre.size() && str[i] == pre[i])
		i++;
	if (i == pre.size())
		return true;
	else
		return false;
}
int main()
{
	int N;
	cin >> N;
	vector<string> v(N);
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}
	string T;
	cin >> T;
	//1、遍历输入的字符串，依次判断其是否以字符串T为前缀
	vector<string> ans;
	for (int i = 0; i < N; i++)
	{
		if (Judge(v[i], T))
			ans.push_back(v[i]);
	}
	//2、将以字符串T为前缀的字符串按字典序进行升序排序
	sort(ans.begin(), ans.end());
	
	for (auto& e : ans)
	{
		cout << e << endl;
	}
	return 0;
}

二、千问万问

1、题目描述

  给定大小为 $n$ 的整数序列 $A$，现在会有 $q$ 次询问，询问子区间的不同整数的数量。

• 输入描述： 第一行输入整数 $n,q(1\le n,q\le 1000)$，第二行输入 $n$ 个整数 $(1\le num\le 100000)$，以下 $q$ 行每行输入两个整数 $l,r(1\le l,r\le 100000)$。
• 输出描述： 输出区间内的整数数量。

示例：

输入：10 3
   1 2 3 4 5 6 7 8 9 10
   1 1
   1 2
   1 3
输出：1
   2
   3

2、代码实现

解题步骤如下：

1. 将整数序列进行升序排序，以便查找子区间的左右边界。
2. 对于每一次询问，先找到区间的左边界，即在整数序列中从左向右找到第一个大于等于left的位置，如果整数序列中不存在大于等于left的值，则直接输出0。
3. 在找到区间的右边界，即在整数序列中从左边界开始向后找到最后一个小于等于right的位置，在寻找右边界的同时统计区间内不同整数的个数即可。

代码如下：

//千问万问
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	//1、将整数序列进行升序排序，以便查找子区间的左右边界
	sort(v.begin(), v.end());
	for (int i = 0; i < q; i++)
	{
		int left, right;
		cin >> left >> right;
		//2、找到区间的左边界，即在整数序列中从左向右找到第一个大于等于left的位置
		int begin = 0;
		while (begin < n&&v[begin] < left)
			begin++;
		if (begin == n) //整数序列中不存在大于等于left的值，输出0
		{
			cout << 0 << endl;
			continue;
		}
		//2、找到区间的右边界，即在整数序列中从左边界开始向后找到最后一个小于等于right的位置
		int end = begin, count = 0, prev = -1;
		while (end < n&&v[end] <= right)
		{
			//寻找右边界的同时统计区间内不同整数的个数
			if (v[end] != prev)
			{
				count++;
				prev = v[end];
			}
			end++;
		}
		cout << count << endl;
	}
	return 0;
}

三、连续子数组的最大和

1、题目描述

  给定一个整数数组 $nums$，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 输入描述： 第一行输入整数数组的大小 $n(2\le n\le 1000)$，第二行给出 $n$ 个整数 $a(-1e5\le 1e5)$。
• 输出描述： 输出答案。

示例：

输入：9
   -2 1 -3 4 -1 2 1 -5 4
输出：6

2、代码实现

解题步骤如下：

1. 遍历整数数组，依次找到整数数组中以每个数为结尾的连续子数组的最大和。
2. 以某个数为结尾的连续子数组最大和 = max(这个数本身，以这个数的前一个数为结尾的连续子数组最大和)。
3. 在计算以每个数为结尾的连续子数组的最大和的同时，找出整数数组中连续子数组的最大和即可。

代码如下：

//连续子数组的最大和
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	vector<int> tmp(n);
	tmp[0] = v[0];
	int Max = tmp[0];
	for (int i = 1; i < n; i++)
	{
		//1、以下标为i的元素结尾的连续子数组的最大和
		tmp[i] = max(v[i], v[i] + tmp[i - 1]);
		//2、更新整数数组中连续子数组的最大和
		Max = max(Max, tmp[i]);
	}
	cout << Max << endl;
	return 0;
}

四、降水量

1、题目描述

  给定 $n$ 个柱面的高度，表示降雨某地 $n$ 块区域的海拔高度。计算降雨之后该地最大储水面积。如果低于地平线，也就是小于0，则一定积水。

• 输入描述： 第一行输入整数 $n(1\le n\le 10000)$，第二行输入 $n$ 个高度整数 $h(-10000\le h\le 10000)$。
• 输出描述： 输出答案。

示例：

输入：12
   0 1 0 2 1 0 1 3 2 1 2 1
输出：6

示例图示（降雨前）：

示例图示（降雨后）：

2、代码实现

解题步骤如下：

1. 依次统计每个区域的降水量，如果某区域的海拔高度低于水平面，则先统计该区域水平面下的积水面积，并将该区域的海拔高度设置为0，便于后续统计该区域水平面上的积水面积。
2. 找到该区域左边区域的最高海拔。
3. 找到该区域右边区域的最高海拔。
4. 该区域水平面上的积水面积，等于左右最高海拔的较小值减去该区域的海拔高度。

需要注意的是，对于海拔高度低于水平面的区域，在统计完水平面下的积水面积后其海拔高度被设置成了0，因此第四步统计的就是其水平面上的积水面积，不会出现重复统计的情况。

代码如下：

//降水量
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	int water = 0;
	for (int i = 0; i < n; i++)
	{
		//1、如果该区域的海拔高度低于水平面，则先统计该区域水平面下的积水面积
		if (v[i] < 0)
		{
			water += (-v[i]);
			v[i] = 0; //将该区域的海拔高度设置为0，便于后续统计该区域水平面上的积水面积
		}
		//2、找到该区域左边区域的最高海拔
		int lmax = 0;
		for (int j = i; j >= 0; j--)
		{
			lmax = max(lmax, v[j]);
		}
		//3、找到该区域右边区域的最高海拔
		int rmax = 0;
		for (int j = i; j < n; j++)
		{
			rmax = max(rmax, v[j]);
		}
		//4、该区域水平面上的积水面积，等于左右最高海拔的较小值减去该区域的海拔高度
		water += min(lmax, rmax) - v[i];
	}
	cout << water << endl;
	return 0;
}