C++组2020高校计算机能力挑战赛-决赛赛题解析

第一题

#include<bits/stdc++.h>
using namespace std;

struct student{
          
   
	int k;
	int t;
	int id;
};
bool cmp(struct student &a,struct student &b){
          
   
    if(a.k*a.t==b.k*b.t){
          
   
		if(a.t==b.t) return a.id<b.id;
		else return a.t>b.t;
	}
	return a.k*a.t>b.k*b.t;
}

int main(){
          
   
	int n;
	cin>>n;
	struct student a[n+1];
	for(int i=1;i<=n;i++){
          
   
		cin>>a[i].t>>a[i].k;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
          
   
		cout<<a[i].id<<" ";
	}
	return 0;
}

第二题

#include<bits/stdc++.h>
using namespace std;

typedef struct student{
          
   
	string name;
	int id;
	double grade;
	string unit;
	int month_monry;
	int month;
}M;

bool cmp1(M &a,M &b){
          
   
	return a.month_monry>b.month_monry; 
}

bool cmp2(M &a,M &b){
          
   
	return a.grade>b.grade; 
}

bool cmp3(M &a,M &b){
          
   
	return a.month_monry*a.month>b.month_monry*b.month; 
}

int main(){
          
   
	int n,m;
	cin>>n>>m;
	vector<M>v(n);
	for(int i=0;i<n;i++){
          
   
		cin>>v[i].name>>v[i].id>>v[i].grade>>v[i].unit>>v[i].month_monry>>v[i].month;
	
	} 
	vector<M>v1(v);
	sort(v1.begin(),v1.end(),cmp1);
	for(int i=0;i<m;i++){
          
   
		printf("%.1f ",v1[i].grade);
	}
	cout<<endl;
	vector<M>v2(v);
	sort(v2.begin(),v2.end(),cmp2);
	for(int i=0;i<m;i++){
          
   
		printf("%d ",v1[i].id);
	}
	cout<<endl;
	vector<M>v3(v);
	sort(v3.begin(),v3.end(),cmp3);
	for(int i=0;i<m;i++){
          
   
		cout<<v1[i].unit;
		if(i!=m-1) cout<<" ";
	}
	
	return 0;
}

第三题

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include <iostream> 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//using namespace std;

int main(int argc, char *argv[]) {
          
   
int i,j,a,c,n;
int b[a];
scanf("%d",&a);
for(i =0;i<a;++i){
          
   
scanf("%d",&b[i]);
c = c+b[i];
n = c/a;
}
for(j=0;j<a;++j){
          
   
	if( abs(b[j]) > n)
	printf("%d   ",b[j]);
}

	return 0;
}

第四题

#include<bits/stdc++.h>
using namespace std;

multimap<int,int>m;

int main()
{
          
   
	string s,s1;
	cin>>s>>s1;
	int last_num=0,cur_num=0;
	for(int i=0; i<s.size(); i++)
	{
          
   
		if(isdigit(s[i]))
		{
          
   
			cur_num=cur_num*10+s[i]-48;
		}
		if(s[i]==-)
		{
          
   
			last_num=cur_num;
			cur_num=0;
		}
		if(s[i]==])
		{
          
   
			m.emplace(last_num,cur_num);
			m.emplace(cur_num,last_num);
			last_num=0;
			cur_num=0;
		}
	}
	int c=0;
	for(int i=4; i<s1.size(); i++)
	{
          
   
		c+=c*10+s1[i]-48;
	}
	for(auto &i:m)
	{
          
   
		if(i.first==c) cout<<"node"<<i.second<<" ";
	}
	return 0;
}

第五题 并查集实现

#include<bits/stdc++.h>
using namespace std;

class unionfind{
          
   
private:vector<int>parent;
vector<int>ans;
public:
    unionfind(){
          
   
        parent.resize(50);
        ans.resize(50);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int x){
          
   
     /*隔代压缩
        while(parent[x]!=x){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
      */
     return x == parent[x] ?x:parent[x]=find(parent[x]);//完全压缩
    }
    void unon(int x1,int x2,int sum){
          
   
         parent[find(x2)]=find(x1);
         ans[find(x1)]+=sum;
    }
    void c(){
          
   
    	sort(ans.begin(),ans.end());
    	cout<<ans[ans.size()-1];
	}
};
//力扣 990题 

int main(){
          
   
    int n;
	cin>>n;
	int t1,t2;
	int sum=0;
	unionfind m;
	for(int i=0; i<n; i++)
	{
          
   	
		cin>>t1>>t2>>sum;
		m.unon(t1,t2,sum);
	}
	m.c();
}