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

文章目录

• 第二十一期竞赛题目
• • 一、合并序列
  • • 1、题目描述
    • 2、代码实现
  • 二、千问万问
  • • 1、题目描述
    • 2、代码实现
  • 三、连续子数组的最大和
  • • 1、题目描述
    • 2、代码实现
  • 四、降水量
  • • 1、题目描述
    • 2、代码实现

第二十一期竞赛题目

一、合并序列

1、题目描述

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

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

示例：

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

2、代码实现

解题步骤如下：

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

代码如下：

//合并序列
#include 
#include 
#include 
#include 
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;elsereturn false;
}
int main()
{int N;cin >> N;vector v(N);for (int i = 0; i < N; i++){cin >> v[i];}string T;cin >> T;//1、遍历输入的字符串，依次判断其是否以字符串T为前缀vector 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、题目描述

  给定大小为 nnn 的整数序列 AAA，现在会有 qqq 次询问，询问子区间的不同整数的数量。

• 输入描述： 第一行输入整数 n,q(1≤n,q≤1000)n,q(1≤n,q≤1000)n,q(1≤n,q≤1000)，第二行输入 nnn 个整数 (1≤num≤100000)(1≤num≤100000)(1≤num≤100000)，以下 qqq 行每行输入两个整数 l,r(1≤l,r≤100000)l,r(1≤l,r≤100000)l,r(1≤l,r≤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 
#include 
#include 
#include 
using namespace std;
int main()
{int n, q;cin >> n >> q;vector 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、题目描述

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

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

示例：

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

2、代码实现

解题步骤如下：

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

代码如下：

//连续子数组的最大和
#include 
#include 
#include 
#include 
using namespace std;
int main()
{int n;cin >> n;vector v(n);for (int i = 0; i < n; i++){cin >> v[i];}vector 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、题目描述

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

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

示例：

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

示例图示（降雨前）：

示例图示（降雨后）：

2、代码实现

解题步骤如下：

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

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

代码如下：

//降水量
#include 
#include 
#include 
using namespace std;
int main()
{int n;cin >> n;vector 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;
}