一共5个编程题,第一题过了83,其他都AC了。
整体难度不是很难,都是比较常规的题,而且还挺裸的。比较恶心的是,需要自己统计有多少个物品等等,不是直接给的,算是比较恶心的了(对于我用cpp来讲,而且我不怎么会stringstream,最恶心的就是最后一题背包了,手动模拟读入,吐了)。
题目
1. 求首个出现的第二小值,若没有,则求首个出现的最小值。(top2做的,只过了83)
#include <iostream> #include <vector> #include <queue> using namespace std; typedef long long LL; const int N = 1e6 + 10; int n; string names[N]; LL w[N]; priority_queue<LL> q; int main(){ //读入 while (cin >> names[n] >> w[n]) { n ++; } //top2小 for (int i = 0 ; i < n ; i ++) { if (q.size() < 2) q.push(w[i]); else if (w[i] < q.top()) { q.pop(); q.push(w[i]); } } string res; LL m = q.top(); for (int i = 0 ; i < n ; i ++) { if (w[i] == m) { res = names[i]; break; } } cout << res; return 0; }
2. 并查集板子题,给定n个人,q次操作,要么是两个人结盟,要么查询两个人是否结盟。(并查集板子题)
#include <iostream> #include <vector> using namespace std; const int N = 1e5 + 10; int n, q; int p[N]; int find(int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } int main(){ cin >> n >> q; for (int i = 0 ; i < n ; i ++) p[i] = i; for (int i = 0 ; i < q ; i ++) { string c; int a, b; cin >> c >> a >> b; int pa = find(a), pb = find(b); if (c[0] == 'u') { if (pa != pb) { p[a] = pb; } } else if(c[0] == 'c') { if (pa == pb) cout << 1 << endl; else cout << 0 << endl; } } return 0; }
3.给定一个敌人坐标、三个炮台坐标,炮台攻击距离。输出有几个炮台能够攻击到敌人坐标(欧几里得距离)。
#include <iostream> #include <cmath> using namespace std; typedef pair<int,int> PAIR; const int N = 1e5 + 10; int dis; PAIR peo[4]; int get(int x,int y,int a,int b) { return abs(x - a) * abs(x - a) + abs(y - b) * abs(y - b); } int main(){ cin >> dis; dis = dis * dis; for (int i = 0 ; i < 4 ; i ++) { cin >> peo[i].first >> peo[i].second; } int x = peo[0].first, y = peo[0].second; int res = 0; for (int i = 1 ; i < 4 ; i ++) { int a = peo[i].first, b = peo[i].second; int d = get(x, y, a, b); if (d <= dis) res ++; } cout << res; return 0; }
4.给定n个点,每次读入一个点后,都输出集合中的中位数。(lc数据流的中位数,大小堆)
#include <iostream> #include <queue> using namespace std; int n; priority_queue<double> left_max; priority_queue<double,vector<double>,greater<double>> right_min; int cnt; void insert(double x) { if (left_max.empty() || x <= left_max.top()) { left_max.push(x); if (left_max.size() > right_min.size() + 1){ right_min.push(left_max.top()); left_max.pop(); } } else { right_min.push(x); if (right_min.size() > left_max.size()){ left_max.push(right_min.top()); right_min.pop(); } } } double get() { if (left_max.size() == right_min.size()) { return left_max.top(); } return left_max.top(); } int main(){ cin >> n; for (int i = 0 ; i < n ; i ++) { double x; cin >> x; insert(x); double res = get(); printf("%.2f\n", res); } return 0; }
5.01背包裸题,某个角色去采集物品,能够承受的重量有限,每个物品只能采一次,每个物品都有重量和价值,求采集物品的最大价值。(01背包裸题)
#include <iostream> using namespace std; const int N = 1e5 + 10; int f[N]; int n, m; int v[N], w[N]; int main() { //读入 cin >> m; getchar(); string s; getline(cin, s); n = 1; for (int i = 0 ; i < s.size() ; i ++) { if (s[i] == ' ') continue; int j = i; while (j < s.size() && s[j] >= '0' && s[j] <= '9') j ++; int t = stoi(s.substr(i, j - i)); v[n ++] = t; i = j; } getline(cin, s); n = 1; for (int i = 0 ; i < s.size() ; i ++) { if (s[i] == ' ') continue; int j = i; while (j < s.size() && s[j] >= '0' && s[j] <= '9') j ++; int t = stoi(s.substr(i, j - i)); w[n ++] = t; i = j; } //01背包 for (int i = 1 ; i <= n ; i ++) { for (int j = m ; j >= v[i] ; j --) { f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[m] << endl; return 0; }
全部评论
(0) 回帖