2024-第四批C++ 第二轮选拔赛（代码加解析）

第二轮比赛结束了，答案又出来了，充实的一天又过去了......

一、摘苹果

题目描述

小白同学种植了一颗苹果树，经过他悉心的照料，苹果树终于结果了，结出了很多苹果。

现在树上有 n 个苹果，因为体力有限，小白同学每分钟只能摘 m 个苹果，而且每过一分钟就会从树上掉落 1 个苹果（不包含在所摘的 m 个苹果之中）。请问小白同学最后能摘到多少个苹果？

输入格式

一行两个整数 n,m，表示苹果的数量和小白同学每分钟能摘的苹果数量。

输出格式

一行一个整数，表示小白同学最后能摘到多少个苹果。

样例数据

输入样例 #1

10 3

输出样例 #1

输入样例 #2

9 2

输出样例 #2

数据范围

对于 20% 的数据，n≤m；

另有 30% 的数据，n mod(m+1)=0；

对于 100% 的数据，1≤n,m≤106。

解析

这道题其实是一个数学问题，我们可以将m+1为一个组合，也就是每分钟树上会失去多少个苹果，用n/(m+1)则是计算过了多少分钟，由于过一分钟就会掉一个苹果，最后再将n减去算的分钟数，剩下的就是他捡到的。

代码

#include<bits/stdc++.h>
using namespace std;int main(){int n,m;cin>>n>>m;cout<<n-n/(m+1);return 0;
}

二、最长上下坡

题目描述

人生就好比一条上下坡路，有时候走的顺风顺水，有时候却是一波三折。

现在给你一条长度为 n 的路，路上有 n 个点，第 i 个点的高度为 hi。现在你需要找到一条连续的上坡或下坡路段，使得这段路的长度最长。

上坡路段的定义是：从某个点开始，往后的点的高度严格递增，即 hi+1>hi。

下坡路段的定义是：从某个点开始，往后的点的高度严格递减，即 hi+1<hi。

输入格式

第一行一个整数 n，表示路的长度。

第二行 n 个整数 h1,h2,⋯,hn，表示每个点的高度。

输出格式

一行一个整数，表示最长的上坡或下坡路段的长度。

样例数据

输入样例 #1

5
1 2 3 2 1

输出样例 #1

最长的上坡路段是 1,2,3, 长度为 3; 最长的下坡路段是 3,2,1, 长度为 3; 所以最长的上坡或者下坡路段的长度为 3。

输入样例 #2

6
3 1 3 3 2 1

输出样例 #2

数据范围

对于 20% 的数据，2≤n≤3；

对于 70% 的数据，2≤n≤500；

对于 100% 的数据，2≤n≤2×105，0≤hi≤109。

解析

这道题相对来说，比较简单。

我们可以定义两个变量up和down，以及求结果的maxx。

然后判断，如果a[i]>a[i-1]，那么up++（也就是把它判断为上升序列的其中的一个元素），否则up=1（也就是它如果不是一个上升序列，那么我们就将它设为1，也就是它停止了上升，就把他设为下一个上升序列的起电）；

如果a[i]<a[i-1]，那么down--（也就是把它判断为逆序列的其中的一个元素），否则的话down=1（也就是它如果不是一个逆序列，那么我们就将它设为1，也就是它停止了下降，就把他设为下一个逆序列的起点）。

最后使用max函数，比较maxx，up和down，结果就是所谓的 “最长上下坡”。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int up=1,down=1;int maxx=0;for(int i=2;i<=n;i++){if(a[i]>a[i-1])up++;else up=1;if(a[i]<a[i-1])down++;else down=1;maxx=max(maxx,max(up,down));}cout<<maxx;return 0;
}

三、历史长河

题目描述

在人类几千年的历史长河中，发生过无数的重要事件，有的影响世界的格局，有的影响人类的命运。

现在给出 n 个历史事件所出现的年份 ai (年份可能为负，为负表示公元前)，需要你来统计哪些年份发生过重要事件，以及每一年发生过多少个事件。

你需要按照年份从小到大的顺序输出年份以及此年发生过多少个事件。

输入格式

第一行一个整数 n，表示历史事件的数量。

第二行 n 个整数 a1,a2,⋯,an，表示每个历史事件所出现的年份。

输出格式

每一行输出两个整数，第一个整数表示年份，第二个整数表示此年发生过多少个事件，空格隔开。

按照年份从小到大的顺序输出。

样例数据

输入样例 #1

5
2020 2021 1999 2021 2020

输出样例 #1

1999 1
2020 2
2021 2

输入样例 #2

5
2023 -200 200 2023 2023

输出样例 #2

-200 1
200 1
2023 3

数据范围

对于 30% 的数据， $1\leq n\leq 100 ,0\leq a_{i}\leq 2024$ ，且不存在重复的年份。

对于 60% 的数据， $1\leq n\leq 2\times 10^{5}$ ， $0\leq a_{i}\leq 2024$ 。

对于 100% 的数据， $1\leq n\leq 2\times 10^{5}$ ， $-2024\leq a_{i}\leq 2024$ 。

解析

这道题考的是桶排，比较简单。我们直接用一个数组记录每一个年份的重大事件。但是我们要考虑年份是有负数的，所以我们可以让每一个年份加上2025，那么数据范围由-2024~2024到数据范围1~4049。那么，不就好求了嘛。直接输入k，上桶排！

最后输出时，只要将i减去2025，不就是之前的年份了？再输出它有多少个历史事件就OK了。

代码

#include<bits/stdc++.h>
using namespace std;
int k,c[4050];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>k;c[k+2025]++;}for(int i=1;i<=4049;i++){if(c[i]) cout<<i-2025<<" "<<c[i]<<endl;}return 0;
}

四、变换阵型

题目描述

盛隆同学刚学完C++的二维数组和函数部分，于是他自己写了2个函数对二维数组进行练习。两个函数如下：

int n, a[1005][1005];
// 注意，这里的n和数组a是全局变量
void f1() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {int t = a[i][j];a[i][j] = a[j][i];a[j][i] = t;}}
}
void f2() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n - i + 1; j++) {int t = a[i][j];a[i][j] = a[n-j+1][n-i+1];a[n-j+1][n-i+1] = t;}}
}

现给出一个 n×n 的矩阵 a，矩阵的行列下标均从 1 开始，也就是说矩阵中的第 i 行第 j 列的元素保存在 a[i][j] 中。

现在盛隆同学想要对矩阵 a 进行 Q 次操作，操作共有三种，参数分别如下：

1：调用函数 f1。
2：调用函数 f2。
3 x y：输出矩阵 a 目前第 x 行第 y 列的元素。

输入格式

第一行两个整数 n,Q，表示矩阵的大小和操作的次数。

接下来 n 行，每行 n 个整数，表示矩阵 a。

接下来 Q 行，每行一个操作，操作格式如题目描述。

输出格式

对于每个操作 3 x y，输出一行一个整数，表示矩阵 a 目前第 x 行第 y 列的元素。

样例数据

输入样例 #1

输出样例 #1

原矩阵经过 2 次操作后的矩阵如下：

9 8 7
6 5 4
3 2 1

所以 a[1][2]=8。

输入样例 #2

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

输出样例 #2

5
10

数据范围

对于 20% 的数据，没有操作一和操作二，只有操作三。

对于 50% 的数据，1≤n≤500，1≤Q≤100。

对于 100% 的数据，1≤n≤1000，1≤Q≤10000， 0≤aij≤109，1≤x,y≤n。

解析

50pts

由于Q是小于等于100，那么时间复杂度就比较低，直接复制题目代码，带进去就可以得个50分。

100pts

在题目所给的代码中，我们经过观察，发现它是有规律的。

f1()是把从左到右的对角线两边的数反过来；f2()是把从右到左的对角线两边的数反过来；

那么，如果说我将f1()或f2()进行偶数倍的操作，会发现矩形是不变的！

所以题目所给的代码其实是在骗你。~~（真**的恶心）~~

代码

#include<bits/stdc++.h>
using namespace std;
int n, a[1005][1005];/*
// 注意，这里的n和数组a是全局变量
void f1() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {int t = a[i][j];a[i][j] = a[j][i];a[j][i] = t;}}
}
void f2() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n - i + 1; j++) {int t = a[i][j];a[i][j] = a[n-j+1][n-i+1];a[n-j+1][n-i+1] = t;}}
}*/
int main(){int n,Q;cin>>n>>Q ;int b=1,c=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=Q;i++){int s,x,y;cin>>s;if(s==1) b++;else if(s==2) c++;else{cin>>x>>y;if(b%2==0){swap(x,y);}if(c%2==0){int t=x;x=n-y+1;y=n-t+1;}cout<<a[x][y]<<endl;}}return 0;
}