算法竞赛入门【码蹄集进阶塔335题】(MT2321-2325）

算法竞赛入门【码蹄集进阶塔335题】(MT2321-2325）

---

---

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

---

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。

---

目录

1. MT2321 最大的矩形面积

（1）题目描述
小码哥有一个奇形怪状的平面图型，想问你这个平面图形里可以容纳的面积最大的矩形。

但是小码哥觉得给你描述这个图形的样子过于麻烦，想要简化一下这个图形，经过多次简化后，这个图形可以看作是由 个等宽的长方形拼接而成的。这个长方形的一个宽边在同一条直线上，他们无缝并列的拼在一起，如图所示。

现在小码哥只需要给定每一个长方形的长边的长度，就可以表示出这个图像的全部信息。

长方形的宽为1 ，用一个序列a来表示长方形长边的长度，长方形的次序不可以更改。

现在小码哥想问你这个平面图形里可以容纳的面积最大的矩形的面积。矩形的长和宽必须和组成平面图形的长方形的长和宽平行。

格式

输入格式:
有多组数据
对于每一组数据输入一行第一个数字n表示这个图形由n个长方形拼接而成，后面n个数，依次表示每个长方形长边的长度。
当n =0 时，停止输入, n=0时，不用输出这一组数据的结果。
.
输出格式: 对于单行上的每个测试用例输出指定平面图形中最大矩形的面积。

样例1

输入格式:
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
.
输出格式:
8
4000

备注：

提示
n ≤20000
保证答案不会超过10的18次方
数据大，建议快读或者使用scanf输入对于第一组数据4×2的矩形是可行的对于第二组数据1000×4的矩形是可行的

（2）参考代码

#include 
using namespace std;
typedef long long LL;
const int maxn = 2e4 + 5;
int n;
LL ar[maxn];
int b[maxn], c[maxn];
int main( )
{
    scanf("%d", &n);
    while (n != 0) 
    {
        stack<LL> st1, st2;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &ar[i]);
            while (!st1.empty())
            {
                int k = st1.top();
                if (ar[k] < ar[i])
                {
                    break;
                }
                st1.pop();
            }
            if (st1.empty())
            {
                b[i] = 0;
            }
            else
            {
                b[i] = st1.top();
            }
            st1.push(i);
        }
        for (int i = n; i >= 1; i--)
        {
            while (!st2.empty())
            {
                int k = st2.top();
                if (ar[k] < ar[i])
                {
                    break;
                }
                st2.pop();
            }
            if (st2.empty())
            {
                c[i] = n + 1;
            }
            else
            {
                c[i] = st2.top();
            }
            st2.push(i);
        }    
        LL max_ = 0;
        for (int i = 1; i <= n; i++)
        {
            max_ = max(max_, (c[i] - b[i] - 1) * ar[i]);
        }
        printf("%lld\n", max_);         
        scanf("%d", &n);
    }
    return 0;
}
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

---

2. MT2322 战神的对称谜题

（1）题目描述
小码哥认为一个物体如果是对称的才足够美好，因此小码哥希望俱乐部的东西都是对称的，尤其是科创部的东西更要对称(>__<，这描述你们敢信? ! ）。科创部里机智聪明的小码妹决定给他一个字符串，让他找出里面最长的对称子串的长度。

小码妹给出一个长度为n(n ≤5000)的非空字符串,请你帮助小码哥在规定时间内找到最长的对称子串的长度。(对于一个给定的字符串，空格也是其中的一部分)。

格式

输入格式:
输入在一行中给出长度不超过5000的非空字符串。
.
输出格式: 输出一个整数(最长的对称的子串）

样例1

输入格式:
NB Zhan&nahZ TianXiaDiYi
.
输出格式: 11

（2）参考代码

#include 
 
// 内部转换与空间顺序
using namespace std;
 
const int M = 1e5+1;
 
struct point{
	int x;
    int y;
    int z;
    int sum=0;
}p[M]; 
 
struct res{
	int start;
	int end;
}r[M];
 
bool com2(point p1, point p2){
    return p1.x < p2.x;
}
 
bool com3(res r1, res r2) {
	return r1.start < r2.start;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    int index;
    for(int i=0;i<m;i++){
        cin >> p[i].x >> p[i].y >>p[i].z;
        index = p[i].x;
        p[index].sum++;
    }
 
	int max = 0;
	int ans = 0;
	
	for(int i=0;i<m;i++){
		if(p[i].sum > max){
			max = p[i].sum;
			ans = i;
		}
	}
	
	sort(p,p+m, com2);
	int j=0;
	for(int i=0;i<m;i++){
		if(p[i].x == ans){
			r[j].start = p[i].y;
			r[j].end = p[i].z;
			j++;
		}
	}
	
	sort(r, r+j,com3);
	
	for(int i=1;i<j;i++){
		if(r[i-1].start==r[i].start && r[i-1].end > r[i].end) {
			int temp = r[i].end;
			r[i].end = r[i-1].end;
			r[i-1].end = temp;
		}
	}
	
	//	出边最多的节点 
	cout << ans << endl;
	
	for(int i=0;i<j;i++){
		cout << r[i].start << " " << r[i].end << endl;
	}
	
    return 0;
}
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
75
76
77

---

3. MT2323 求和

（1）题目描述
小码哥最近在数学课上新学了等差数列的求和公式，于是他就想在程序上实现一下，他去问小码妹有没有什么题目给他练一练，小码妹就给他出了一道题:对于正整数X，求所有的区间[a,b] (a、b为正整数），使得每一个区间内正整数相加的和等于X，如果不存在这样的区间则输出No。

---

格式

输入格式: 输入一个正整数X
.
输出格式:
输出若干行，每行两个正整数代表一个满足条件的区间的a和b。按照α的升序依次输出。

样例1

输入格式: 15
.
输出格式:
1 5
4 6
7 8

备注：

a≠ b，X≤2000000 ,
等差数列的求和公式为:(首项＋末项)x项数/2

（2）参考代码

#include
#include
#include
#include
using namespace std;
int cnt,n,k;
int ans[1000010];
bool flag[10000010];
int next(int num){
    int ans=0;
    ans+=num;
    while(num!=0){
        ans+=num%10;
        num/=10;
    }
    return ans;
}
int main(){
    memset(flag,true,sizeof(flag));
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        if(flag[i]){
            ans[++cnt]=i;
            int now=next(i);
            while(now<=n&&flag[now]) {
                flag[now]=false;
                now=next(now);
            }
        }
    printf("%d\n",cnt);
    int t=0;
    for(int i=1;i<=k;i++){
        scanf("%d",&t);
        printf("%d ",ans[t]);
    }
}
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

---

4. MT2324 字符串之谜

（1）题目描述
在所给字符串中找出至少出现两次的最长子串的长度。

---

格式

输入格式:
一行一个字符串，并且人为规定这一定是非空的字符串，并由小写字母组成，长度不会超过2e4个字符。
.
输出格式: 输出一个数。这个数是子串中最少出现两次的最长子串的长度。

样例1

输入格式: ababa
.
输出格式: 3

（2）参考代码

#include 
#include 
int main()
{
    char s1[100005],s2[100005],a[100005];
    gets(s1);
    gets(s2);
    int i,j,c;
    for (i = 0; s1[i] != '\0'; i++){
    a[i]=s1[i];}
    for (j = 0; s2[j] != '\0'; j++){
        a[i+j]=s2[j];
    }
    c=i+j;
   puts(a);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

5. MT2325 元音字母

（1）题目描述
元音字母在英语中有着重要的意义，小码哥深知这点，于是他对这些字母有着独特的热情。

刚学字符串的小码哥立即就给你一个字符串s和整数k，让你求s串的长度为k的子串中可能包含的最大元音字母数。

元音字母包括(a，e， i，o，u) 。

---

格式

输入格式:
第一行输入s串
第二行输入整数k
.
输出格式: 返回最大元音字母数

样例1

输入格式:
abciiidef
3
.
输出格式: 3

备注：

其中: 1≤s.length ≤100000，s由小写英文字母组成，1≤ k ≤s.length

（2）参考代码

def main():
    s = input()
    k = int(input())
    length = len(s)
    nums = []
    yuanyin = ['a','e','i','o','u']
    out = 0
    temp = 0
    for i in range(length):
        if i<= k-1:
            if s[i] in yuanyin:
                nums.append(1)
                out+=1
            else:
                nums.append(0)
        else:
            out-=nums.pop(0)
            if s[i] in yuanyin:
                out+=1
                nums.append(1)
            else:
                nums.append(0)
            if out>temp:
                temp=out
    print(temp)
if __name__ == '__main__':
    main()
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

---

结语

希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。