题目较为简单,但是第一题也是醉了,交了好多次才完全通过。😂😂😂
第一题:直接排序
#include <bits/stdc++.h> using namespace std; void solve() { int n, k; cin >> n >> k; vector<int> a(n); for (int &x : a) { cin >> x; } sort(a.begin(), a.end()); if (k == 0) { cout << "YES\n"; cout << 1 << '\n'; } else { int ans = a[k - 1] + 1; int t = lower_bound(a.begin(), a.end(), ans) - a.begin(); if (ans <= n && t == k) { cout << "YES\n"; cout << ans << '\n'; } else { cout << "NO\n"; } } } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); int T; cin >> T; while (T--) { solve(); } return 0; }
第二题:简单的字符串处理
import sys line = sys.stdin.readline().strip() pre = "$" ans = [] for c in line: if c != pre and c != " ": ans.append(c) if c != " ": pre = c print("".join(ans))
第三题:有序集合(注意数据溢出)
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); int n, x; long long ans = 0; set<int> S; cin >> n; for (int i = 1; i <= n; ++i) { cin >> x; auto it = S.lower_bound(x); if (it != S.begin()) { --it; ans += 1LL * i * (*it); } S.emplace(x); } cout << ans << '\n'; return 0; }
第四题:并查集
#include <bits/stdc++.h> using namespace std; #define N 100005 int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); vector<int> fa(N), size(N); for (int i = 0; i < N; ++i) { fa[i] = i; size[i] = 1; } function<int(int)> find_set = [&](int x) { return x == fa[x] ? x : (fa[x] = find_set(fa[x])); }; auto union_sets = [&](int x, int y) -> bool { x = find_set(x), y = find_set(y); if (x == y) { return false; } if (size[x] < size[y]) { swap(x, y); } fa[y] = x; size[x] += size[y]; return true; }; int n; cin >> n; vector<int> a(n); for (int &x : a) { cin >> x; } for (int i = 0; i < n / 2; ++i) { if (a[i] != a[i + n / 2]) { union_sets(a[i], a[i + n / 2]); } } unordered_map<int, vector<int>> mp; for (int i = 0; i < N; ++i) { mp[find_set(i)].emplace_back(i); } int ans = 0; for (auto it = mp.cbegin(); it != mp.cend(); ++it) { ans += it->second.size() - 1; } cout << ans << '\n'; return 0; }
第五题:二叉树中序遍历,直接模拟交换
#include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); int n, m, k, l, r, x; cin >> n >> m >> k; vector<TreeNode *> nodes(n + 1); for (int i = 1; i <= n; ++i) { nodes[i] = new TreeNode(i); } nodes[0] = nullptr; for (int i = 1; i <= n; ++i) { cin >> l >> r; nodes[i]->left = nodes[l]; nodes[i]->right = nodes[r]; } while (m--) { cin >> x; swap(nodes[x]->left, nodes[x]->right); } vector<int> ans; function<void(TreeNode *)> Dfs = [&](TreeNode *root) { if (!root) { return; } Dfs(root->left); ans.emplace_back(root->val); Dfs(root->right); }; Dfs(nodes[k]); for (int i = 0; i < n; ++i) { cout << ans[i] << " \n"[i == n - 1]; } return 0; }
全部评论
(3) 回帖