没打网络赛，今年没机会了。但是23集训队佬ml拿了Cu %%%
浅浅练习一下~
gymlink
F
签到题, 判断有无元素出现次数过半
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <cstring> #include <map> #include <algorithm> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; map<string, int> m; for (int i = 1; i <= n; ++ i) { string col; cin >> col; m[col] ++; } for (auto [col, t]: m) { if (t + t > n) { cout << col << '\n'; return 0; } } cout << "uh-oh\n"; } |
E
map套vector
排序之后去绝对值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <unordered_map> using namespace std; using LL = long long; int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; unordered_map<int, vector<int>> ax, ay; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { int col; cin >> col; ax[col].push_back(i); ay[col].push_back(j); } auto calc = [](unordered_map<int, vector<int>> &a) -> LL { LL res = 0; for (auto &[col, v]: a) { sort(v.begin(), v.end()); int n = v.size(); for (int _i = 0; _i < n; ++ _i) { int i = _i + 1; res += (LL)(4 * i - 2 * n - 2) * v[_i]; } } return res; }; LL res = calc(ax) + calc(ay); cout << res << '\n'; } |
J
先求最小生成树, 然后不断加边更新res
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; using piii = pair<pair<int, int>, int>; using pii = pair<int, int>; const int N = 3e5 + 10; int fa[N]; vector<pii> Graph[N]; struct my2big { int d1, d2; my2big(): d1(0), d2(0) {} my2big(int d1, int d2): d1(d1), d2(d2) {} void updata(int d) { if (d > d1) d2 = d1, d1 = d; else if (d > d2) d2 = d; } int sum() { return d1 + d2; } void toMin(my2big x) { if (x.sum() < sum()) { d1 = x.d1, d2 = x.d2; } } } f[2][N]; // 维护到n的路径 my2big combine(my2big a, my2big b) { a.updata(b.d1); a.updata(b.d2); return a; } int find(int x) { return fa[x] == x ? x: fa[x] = find(fa[x]); } bool check(int x, int y) { return find(x) == find(y); } void merge(int x, int y) { fa[find(x)] = find(y); } void add(int a, int b, int c) { Graph[a].push_back({b, c}); } void dfs(int u, int father, my2big* f) { for (auto [to, w]: Graph[u]) { if (to == father) continue; f[to] = f[u]; f[to].updata(w); dfs(to, u, f); } } int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector<piii> edge, rest; for (int i = 0; i < m; ++ i) { int a, b, c; cin >> a >> b >> c; edge.push_back({{a, b}, c}); } sort(edge.begin(), edge.end(), [](piii a, piii b) -> bool { return a.second < b.second; } ); for (int i = 1; i <= n; ++ i) fa[i] = i; for (int i = 0; i < m; ++ i) { int a = edge[i].first.first; int b = edge[i].first.second; int c = edge[i].second; if (check(a, b)) { rest.push_back(edge[i]); } else { merge(a, b); add(a, b, c); add(b, a, c); } } dfs(n, n, f[0]); dfs(1, 1, f[1]); my2big res = f[1][n]; for (auto [p, c]: rest) { int a = p.first, b = p.second; res.toMin(combine(combine(f[1][a], my2big(c, 0)), f[0][b])); res.toMin(combine(combine(f[1][b], my2big(c, 0)), f[0][a])); } cout << res.sum(); } |
发表回复