ACGO欢乐赛#31题解

北辞

2024-10-21 11:50:50

发布于：广东

98阅读

0回复

0点赞

转眼间ACGO欢乐赛就到31次了，~~不知道以后有多少次呢？~~
蒟蒻第一次写题解，有更优解欢迎吐槽~
这次欢乐赛比较简单，我也趁此写写题解。

正文

T1

思路：
相信这道题目大家都会做。题目要求我们从 $a$ , $b$ , $c$ 当中选2个数，并将它们相减，使得差最大。明显可以将最大数与最小数相减即可。
这里我的代码直接用sort排序。~~懒得写if了🙂~~

AC Code

本题考察比较等语法。

#include<iostream>
#include<algorithm>//sort函数库
using namespace std;
int main(){
	int a[4];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);//从小到大排序
	cout<<a[2]+a[1];//将最大数与最小数相减并输出
	return 0;
}

T2

思路：
这道题目要求我们输出数组距离的长度，并告诉我们数组距离定义为：数组中任意两个元素的差的绝对值。并让我们求该数组最大的数组距离。

理解了本题的思路，我们就容易思考如何解题了。既然是输出数组里两数差的最大绝对值，那么我们就可以想到，要使绝对值最大，直接将最大数与最小数相减即可。😄

AC Code

本题考察比较等语法。

//我的方法是将数据输入后，对a数组进行从小到大排序，最后直接输出最大值与最小值的差。
#include<iostream>
#include<algorithm>
using namespace std;
int a[200005];//注意题目范围
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){//数据的输入
		cin>>a[i];
	}
	sort(a,a+n);//还是sort排序
	cout<<a[n-1]-a[0];//最大数减最小数，绝对值可不写
	return 0;
}

T3

思路：
T3是一道有关字符拼接的语法题目，题目输入s1和s2两个字符串，并输出新的字符串，告诉我们新的字符串是这样构成的：
$s1[0]+s2[0]+s1[1]+s2[2]+s1[2]+s2[2]+...+s1[n]+s2[n]$
由此可见是由s1和s2的每个字符依次拼接成。
我们可以这样写代码：定义1个char数组s3，定义1个idx索引变量，通过for循环n次，将 $s1[i]$ 和 $s2[i]$ 拼接在新s3里。记得s1拼接后，使idx++，s2同理。😁

AC Code

本题考察字符串等语法。

#include<iostream>
using namespace std;
string s1,s2;
char s3[205];//定义char数组,方便s1和s2拼接
int n,idx;//idx为s3的索引变量
int main(){
	cin>>n;
	cin>>s1>>s2;
	for(int i=0;i<n;i++){
		s3[idx]=s1[i];//将s1[i]放在s3[idx]里
		idx++;//因为s3[idx]已经放了s1[i],所以下一次是s3[idx+1],也就是idx++
		s3[idx]=s2[i];//上方同理
		idx++;
	}
	for(int i=0;i<idx;i++)cout<<s3[i];//输出s3数组里的每个char元素
	return 0;
}

T4

思路：
该题目总的意思就是要我们用两个变量依次自增目前数组最大的数，并除去这个数。
如何找到最大的数？明显可以通过排序解决。

我们首先将输入的数组排序，如果用sort不写cmp函数，那么我们就从小到大排序，并用for循环从大到小依次枚举数组里每个数，因为通过排序，我们能保证每次遍历到的数都是数组[i~0]中最大的那个，然后我们就可以通过定义一个bool函数flag，实现sum1和sum2的依次自增。由于sum1是第一个增加的，所以最后直接输出sum1与sum2的差即可。✌

AC Code

本题考察数组等语法。

//省略头文件和命名空间
int sum1,sum2;
int a[1005];
bool flag=0;
int n;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);//不写cmp函数，默认数组从小到大排序
	for(int i=n-1;i>=0;i--){//从小到大排序，那么我们的i就要从最后一个数开始遍历
		if(!flag){//用flag实现sum1和sum2依次增加a[i]
			sum1+=a[i];
			flag=1;
		}else{
			sum2+=a[i];
			flag=0;
		}
	}
	cout<<sum1-sum2;//sum1是最先加的，不用考虑正负情况，直接相减即可
	return 0;
} 
//如果写cmp函数，那么将会是这样的代码：
bool cmp(int x,int y)return x>y;//cmp从大到小函数
-----
for(int i=0;i<n;i++){//cmp是从大到小排序，那么我们的i就要从第一个数开始遍历
		if(!flag){
			sum1+=a[i];
			flag=1;
		}else{
			sum2+=a[i];
			flag=0;
		}
	}

T5

思路：
T5是一道类似模拟法的题目，我们可以通过题目给出的样例进行模拟并尝试找相同数值，同时观察for循环的i和j的变化，从而发现规律。
以下是模拟过程：

注： $A^T$ 改为t，A改为a

我们可以马上发现，其实将a数组反转就是将i和j进行相互换位，但是也要注意循环范围哦~😘

AC Code

考察模拟、数组等语法

//省略头文件和命名空间
int a[1005][1005];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];//二维数组的输入
		}
	}
	for(int i=0;i<m;i++){//因为要进行反转，i相当于j，因此i要从0循环到m
		for(int j=0;j<n;j++){//同理，j相当于i，因此j要从0循环到n
			cout<<a[j][i]<<" ";//将i和j互换位置并输出
		}
		printf("\n");//换行
	}
	return 0;
}

T6

思路：
该题目要求我们在一个数组里找到k个数字，并将最大值与最小值相减，使得差最小并输出。
明显要使差最小，我们可以不断比较k个数字的差，如果比min小，那么就更新min的值，以此来类推。

我们可以先将数组从小到大排序，方便找到最优解，然后定义min函数设为无穷大，for循环从0到n-k，并定义临时变量m储存当前差，再与min比较，最后输出min。😉

AC Code

考察模拟、数组等语法

#include<iostream>
#include<algorithm>
using namespace std;
int a[200005];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];//数据输入
    sort(a,a+n);//从小到大排序
    int minn=0x3f3f3f3f;//将minn设为无穷大
    for(int i=0;i<=n-k;i++){//n-k表示留出k个数字，防止越界
        int m=a[i+k-1]-a[i];//将当前差值保存到临时变量名m，其中的-1是因为数组输入时是从0开始的
        if(m<minn)minn=m;//进行比较，如果比minn还要小，那么更新minn
    }
    cout<<minn;//我们能保证minn是数组里k个数字的最小值
    return 0;
}