22蓝桥杯训练6
题目一：小蓝与操作序列
Description:
小蓝学习并掌握了新的数据结构——栈；它作为一种只允许在其顶端执行增删操作的独特线性数据结构具有重要的应用价值；其首端被称为基底位置；为了实现基本功能小蓝成功构建了一个支持基本运算功能的数据结构——堆叠；其中包含四个核心运算功能分别是推入弹出获取以及清空；但在实际应用过程中由于经验不足经常会出现错误的情况；为了检验自己对这种抽象数据类型的掌握程度他记录下了一系列的操作序列希望得到反馈结果；根据相关理论知识一个合法的操作序列应当满足以下条件即在一个完全清空的堆叠基础上按照正确的顺序执行每一个指令动作过程中都不会出现异常情况；因此通过观察这一特定的操作序列我们就可以判断其是否符合规范
input:
这一行将提供一个整数N ， 其表示操作序列的具体操作数量。这些将由N个单独的字符串组成。每个这样的字符串必定属于push、pop、top和clear这四个预定义的操作之一。具体来说就是指push、pop、top和clear这四种原始操作中的其中一种（不包含引号）。
output:
程序将执行两步指令：首先判断该操作序列是否有效；如果判断结果为真，则会打印‘Yes’；接着会打印最后栈中的元素数目信息；否则的话就会出错；错误会在第几步发生？
sample input:
输入样例1
5
push
push
top
pop
push
输入样例 2
5
push
top
push
clear
pop
sample output:
输出样例1
Yes
2
输出样例 2
No
5
#include <bits/stdc++.h>
using namespace std;
int main()
{
stack<int> s;
int n;
string str;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>str;
if(str=="push") s.push(1);
else if(str=="clear") while(!s.empty()) s.pop();
else if(str=="top")
{
if(s.empty())
{
cout<<"No\n"<<i;
return 0;
}
}
else
{
if(s.empty())
{
cout<<"No\n"<<i;
return 0;
}
s.pop();
}
}
cout<<"Yes\n"<<s.size();
return 0;
}
cpp
题目二：小兰与角谷猜想
Description:
l,r
l,r
l,r
input:
输入包含一行，共两个整数 l 和r ， 表示小蓝想查询的区间。
output:
输出一行整数，在区间 [l, r] 内等于1 的步骤出现次数最多的那个整数值
sample input:
样例输入1
1 10
输入样例 2
999999900 1000000000
sample output:
样例输出1
9
输出样例 2
999999906
#include <iostream>
#include <algorithm>
using namespace std;
int collatzSteps(long long n) {
int steps = 0;
while (n != 1) {
if (n % 2 != 0) {
n = n * 3 + 1;
} else {
n = n / 2;
}
steps++;
}
return steps;
}
int main() {
long long l, r;
int maxSteps = 0;
long long maxNum = 0;
cin >> l >> r;
for (long long i = l; i <= r; i++) {
int steps = collatzSteps(i);
if (steps > maxSteps) {
maxSteps = steps;
maxNum = i;
}
}
cout << maxNum <<endl;
return 0;
}
cpp
题目三：小兰与名氏距离
Description:
input:
最前端的一行将包含一个整数 N 代表二维空间内点的数量。随后会有 N 行数据每个数据行由两个整数组成分别对应着该点对的 X 和 Y 坐标值。
output:
输出一行，包含一个整数， 表示距离与p 无关的点对数目。
sample input:
3
0 1
1 0
1 1
sample output:
2
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;
struct pos {
int x;
int y;
};
int main() {
int n;
cin >> n;
vector<pos> sa(n);
for (int i = 0; i < n; i++)
cin >> sa[i].x >> sa[i].y;
unordered_map<int, int> x_count, y_count;
// 计算每个x坐标和y坐标的出现次数
for (int i = 0; i < n; i++) {
x_count[sa[i].x]++;
y_count[sa[i].y]++;
}
long long num = 0;
// 计算具有相同x坐标或y坐标的点对数量
for (int i = 0; i < n; i++) {
num += x_count[sa[i].x] - 1;
num += y_count[sa[i].y] - 1;
}
cout << num / 2 << endl; // 每对点对会被计算两次，所以除以2
return 0;
}
cpp
题目四：小兰与线段
Description:
给定一个仅包含 0和1，大小为N*M的矩阵。 小蓝想找到其中最长线段的长度。
input:
输入的第一行为两个整数N和M（其中N代表矩阵的行数、M代表矩阵的列数）。之后每行为N个元素（其中每一行为矩阵的一行）。
output:
输出一行，包含一个整数，表示矩阵中最长线段的长度。
sample input:
3 3
0 1 1
1 1 0
0 1 0
sample output:
3
1<=N,M<=1000,数字仅包含0和1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1000][1000],cnt0=0,cnt1=0,ans=0;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j])
{
cnt1++;
ans=max(ans,cnt0);
cnt0=0;
}
else
{
cnt0++;
ans=max(ans,cnt1);
cnt1=0;
}
}
ans=max(ans,cnt0);
ans=max(ans,cnt1);
cnt0=cnt1=0;
}
cnt0=cnt1=0;
for(int j=0;j<m;j++)
{
for(int i=0;i<n;i++)
{
if(a[i][j])
{
cnt1++;
ans=max(ans,cnt0);
cnt0=0;
}
else
{
cnt0++;
ans=max(ans,cnt1);
cnt1=0;
}
}
ans=max(ans,cnt0);
ans=max(ans,cnt1);
cnt0=cnt1=0;
}
cout<<ans;
return 0;
}
cpp
题目五：小兰与子数组
Description:
范围内即为该数组最大与最小元素之差；对于小蓝而言，则是轻而易举可求得其范围；然而目前他却想要了解该所有可能子集中对应子范围的最大值与第二大的数值；这些子集则由原序列中的一个或多个连续整数构成序列
input:
文本由两部分组成。 第一段包含一个整数N ，代表数组的规模。 第一段详细描述了数组中各个元素的具体数值。
output:
输出一行，包含两个整数，表示子数组范围的最大值和次大值。
sample input:
5
4 3 2 1 4
sample output:
3 3
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,maxn;
cin>>n;
int a[n+1];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
maxn=a[n-1]-a[0];
cout<<maxn<<" ";
if((a[n-1]-a[n-2])>(a[1]-a[0]))
cout<<a[n-1]-a[1];
else cout<<a[n-2]-a[0];
return 0;
}
cpp
