2020全国高校计算机能力挑战赛C++决赛代码分享

拼搏现实的明天。 2022-12-29 04:48 117阅读 0赞

样例均过(2020.1.3更新：一等奖)

1.模拟

#include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iomanip>
    using namespace std;
    
    int main() {
    	int n;
    	cin >> n;
    	double hun, su, zhushi, tang;
    	cin >> hun >> su >> zhushi >> tang;
    	double hot = 0, zhushiweight = 200, cost = 0;
    	bool flag = 0;
    	for (int i = 0; i < n; ++i) {
    		char sign;
    		double weight, perhot;
    		cin >> sign >> weight >> perhot;
    		if (sign == 'M') {
    			cost += hun * weight / 100;
    			hot += weight * perhot / 100;
    		}
    		else if (sign == 'V') {
    			cost += su * weight / 100;
    			hot += weight * perhot / 100;
    		}
    		else if (sign == 'R') {
    			zhushiweight -= weight;
    			if (flag) {
    				cost += zhushi * weight / 100;
    			}
    			else if (zhushiweight < 0) {
    				flag = 1;
    				cost += (-zhushiweight)*zhushi / 100;
    			}
    			hot += weight * perhot / 100;
    		}
    		else if (sign == 'S') {
    			cost += tang * weight / 100;
    			hot += weight * perhot / 100;
    		}
    	}
    	if (hot < 900) {
    		cost *= 0.9;
    	}
    	cout <<fixed<<setprecision(2)<< cost << endl;
            return 0;
    }

2.暴力

#include<iostream>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iomanip>
    using namespace std;
    
    int a[1005];
    vector<int> ans;
    long long fastPower(long long base, long long power) {
    	long long result = 1;
    	while (power > 0) {
    		if (power & 1)
    			result = result * base;
    		power >>= 1;
    		base = base * base;
    	}
    return result;
    }
    
    int main() {
    	int N;
    	cin >> N;
    	long long sum = 0;
    	for (int i = 0; i < N; ++i) {
    		cin >> a[i];
    		sum += fastPower(a[i], 3);
    	}
    	for (int i = 0; i < N; ++i) {
    		if (sum - fastPower(a[i], 3) == a[i]) {
    			ans.push_back(a[i]);
    		}
    	}
    	for (int i = 0; i < ans.size(); ++i) {
    		cout << ans[i] << " ";
    	}
         return 0;
    }

3.结构体排序

#include<iostream>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iomanip>
    #include<string>
    using namespace std;
    
    
    struct student{
    	string name;
    	string id;
    	double GPA;
    	double jiafen;
    	string school;
    	student(string pname, string pid, double pGPA, double pjiafen, string pschool) {
    		name = pname;
    		id = pid;
    		GPA = pGPA;
    		jiafen = pjiafen;
    		school = pschool;
    	}
    };
    
    vector<student> s;
    int main() {
    	int N, M;
    	cin >> N >> M;
    	for (int i = 0; i < N; ++i) {
    		string a, b, e;
    		double c, d;
    		cin >> a >> b >> c >> d >> e;
    		s.push_back(student(a, b, c, d, e));
    	}
    	sort(s.begin(), s.end(), [](student s1, student s2) {
    		return s1.GPA > s2.GPA;
    	});
    	for (int i = 0; i < M; ++i) {
    		cout << s[i].school << " ";
    	}
    	cout << endl;
    	sort(s.begin(), s.end(), [](student s1, student s2) {
    		return s1.jiafen > s2.jiafen;
    	});
    	for (int i = 0; i < M; ++i) {
    		cout << s[i].id << " ";
    	}
    	cout << endl;
    	sort(s.begin(), s.end(), [](student s1, student s2) {
    		return s1.jiafen+s1.GPA> s2.jiafen+s2.GPA;
    	});
    	for (int i = 0; i < M; ++i) {
    		cout << s[i].name << " ";
    	}
    	cout << endl;
           return 0;
    }

4.字符串+图论，离散化即可

#include<iostream>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iomanip>
    #include<string>
    using namespace std;
    
    
    unordered_map<string, int> mp;
    int num = 0;
    vector<vector<string> > vec(100, vector<string>());
    int main() {
    	string s,t1,t2;
    	cin >> s;
    	int i = 0, j = 0;
    	while (j < s.size()) {
    		if (s[j] == '-') {
    			t1 = s.substr(i + 1, j - i - 1);
    			if (!mp.count(t1)) {
    				mp[t1] = num++;
    			}
    			i = j;
    		}
    		else if (s[j] == ']') {
    			t2 = s.substr(i + 1, j - i - 1);
    			if (!mp.count(t2)) {
    				mp[t2] = num++;
    			}
    			vec[mp[t1]].push_back(t2);
    			vec[mp[t2]].push_back(t1);
    			i = j + 1;
    		}
    		++j;
    	}
    	string tofind;
    	cin >> tofind;
    	if (!mp.count(tofind)) {
    		cout << "NULL" ;
    	}
    	else {
    		int tt = mp[tofind];
    		for (int i = 0; i < vec[tt].size(); ++i) {
    			cout << vec[tt][i] << " ";
    		}
    	}
    	return 0;
    }

5.图论求无向图连通分支，运用并查集可求解

#include<iostream>
    #include<vector>
    #include<map>
    #include<set>
    #include<stack>
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iomanip>
    #include<string>
    using namespace std;
    
    
    unordered_map<string, int> mp;
    unordered_set<int> st;
    int num = 0;
    struct DSU {
    	vector <int> parent;
    	vector<int> rank;
    	DSU(int n) {
    		parent.resize(n);
    		rank.resize(n);
    		for (int i = 0; i < n; ++i) {
    			parent[i] = i;
    			rank[i] = 0;
    		}
    	}
    	int find(int index) {
    		return index == parent[index] ? index : parent[index] = find(parent[index]);
    	}
    	bool union_(int u, int v) {
    		int rootu = find(u), rootv = find(v);
    		if (rootu == rootv) return 0;
    		else {
    			if (rank[rootu] > rank[rootv])  parent[rootv] = rootu;
    			else if (rank[rootu] < rank[rootv])  parent[rootu] = rootv;
    			else {
    				parent[rootu] = rootv;
    				++rank[rootv];
    			}
    			return 1;
    		}
    	}
    };
    
    int main() {
    	int n;
    	cin >> n;
    	DSU dsu(105);
    	for (int i = 0; i < n; ++i) {
    		string s1, s2;
    		cin >> s1 >> s2;
    		if (!mp.count(s1)) {
    			mp[s1] = num++;
    			dsu.parent[mp[s1]] = mp[s1];
    		}
    		if (!mp.count(s2)) {
    			mp[s2] = num++;
    			dsu.parent[mp[s2]] = mp[s2];
    		}
    		dsu.union_(mp[s1], mp[s2]);
    	}
    	for (int i = 0; i < num; ++i) {
    		st.insert(dsu.parent[i]);
    	}
    	cout << st.size();
    	return 0;
    }

6.计算几何

#include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    struct AC{
    	int x,y,id;
    	double theta;
    }point[1010];
    bool cmp(AC x,AC y){
    	return x.theta<y.theta;
    }
    double angle(AC o,AC s,AC e) 
    { 
    	double cosfi,fi,norm; 
    	double dsx = s.x - o.x; 
    	double dsy = s.y - o.y; 
    	double dex = e.x - o.x; 
    	double dey = e.y - o.y; 
    	cosfi=dsx*dex+dsy*dey; 
    	norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey); 
    	cosfi /= sqrt( norm ); 
     
    	if (cosfi >=  1.0 ) return 0; 
    	if (cosfi <= -1.0 ) return -3.1415926; 
    	fi=acos(cosfi); 
    	if (dsx*dey-dsy*dex>0) return fi;     
    	return -fi; 
    }
    int main(){
    	int n,m,p,t;
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>point[i].x>>point[i].y;
    		point[i].id=i;
    	}
    	p=point[m].x;
    	t = point[m].y;
    	point[m].id=point[n].id;
    	point[m].x=point[n].x;
    	point[m].y=point[n].y;
    	point[n].x=p;
    	point[n].y=t;
    	for(int i=1;i<n;i++){
    		point[0].x=point[n].x+10;
    		point[0].y=point[n].y;
    		point[i].theta=angle(point[n],point[0],point[i]);
    		if(point[i].theta<0){
    			point[i].theta+=100;
    		}
    	}
    	sort(point+1,point+n,cmp);
    	cout<<point[1].id;
           return 0;
    }