ACGO欢乐赛18题解完整版
2024-07-17 15:16:09
发布于：上海
45阅读
0回复
0点赞
声明：本人独立完成，非抄袭
ACGO愚人节欢乐赛18题解完整版
第一题：
读题：
给定n个数，从中选出m个数，使得这些数中的最大值与最小值差最小
思路：
先输入这些数据，再排序，这样能够保证连续的m个数中最大值与最小值之差尽可能小，再擂台找到这些的最小值
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int m,n,c=2147483647;
cin>>m>>n;
int s[n];
for(int i=0;i<n;i++)cin>>s[i];
sort(s,s+n);
for(int i=0;i<=n-m;i++)c=min(c,s[i+m-1]-s[i]);
cout<<c<<endl;
return 0;
}
第二题：
读题：
输入一串字符串，把里面出现过的不同字符数统计出来
思路：
因为它要求字符不重复，所以我们可以用set（集合）来存储，最后输出集合的大小
代码：
#include<iostream>
#include<set>
using namespace std;
set<char> st;
char c;
int main(){
while(1){cin>>c;if(c=='}')break;
if(c>96&&c<123)st.insert(c);}
cout<<st.size();
return 0;
}
第三题：
读题：
给定一串数列，求至少将相邻两个数字交换几次，才能够让整个数列变成头最大、尾最小的数列
思路：
这是全场最难的题！
想象一下，模拟做法假如超时该怎么办！（当然，由一只姜提供，模拟不会TLE）
那么我们可以转变为递推（像我给的新春欢乐赛第一题题解一样），找到一个规律
我们发现，能够擂台找到最大值的位置和最小值的位置，把最大值移到头需要abs(maxi-0)次，最小值移到尾需要abs(mini-(n-1))次
但是有没有想过最小的会在最大的前面？那如果这时我要把最大值放到最前面时，必须要和最小值交换一次，那么就需要减少一次！
还有一个问题：当有并列最大值或最小值时，我们选哪一个？
对于这个问题，我们再看一下题目：要求交换次数尽可能少，那么因为最大值要移到队首，所以我们最好选最靠前的最大值；同理，我们应该选最靠后的最小值。
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,s[100];
int main(){
cin>>n;
int maxn=0,maxi=0,minn=2147483647,mini=0;
for(int i=0;i<n;i++){
cin>>s[i];
if(s[i]>maxn)maxn=s[i],maxi=i;
if(s[i]<=minn)minn=s[i],mini=i;
}cout<<abs(mini-(n-1))+abs(maxi-0)-(mini<maxi);
return 0;
}
本人做本类型题喜欢找到递推公式，请勿见怪
建议各位做题时不要局限于模拟的思路，也可以想想如何用二分、递推等思路去完成
第四题：
读题：
给两个二进制数，不进位相加
思路：
用字符串形式存储两个二进制数，如果两位相等，那么和的该位为0，否则为1
代码：
#include<iostream>
#include<string>
using namespace std;
string a,b,c;
int main(){
cin>>a>>b;
for(int i=0;i<a.size();i++){
if(a[i]==b[i])c.append(1,'0');
else c.append(1,'1');
}cout<<c;
return 0;
}
第五题：
读题：
给你n个数，求哪个索引的数为当前的索引
思路：
用数组存储这些数，然后顺序查找查找，时间复杂度最高O(n2)
代码：
#include<iostream>
using namespace std;
int n,s[100];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(s[j]==i+1){
cout<<j+1<<" ";
break;
}
}
}return 0;
}
备注：
荧光
标注为考察知识点
下划线
标注为关键点
加粗体
标注为板块
分界线
标注为分界线
有帮助，赞一个