ABC424

C. New Skill Acquired

多源bfs

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;int main() {int n;cin >> n;vector<vector<int>> to(n);vector<int> got;rep(i, n) {int a, b;cin >> a >> b;if (a == 0) {got.push_back(i);}else {--a; --b;to[a].push_back(i);to[b].push_back(i);}}vector<bool> used(n);queue<int> q;for (int v : got) {used[v] = true;q.push(v);}while (q.size()) {int v = q.front(); q.pop();for (int u : to[v]) {if (used[u]) continue;used[u] = true;q.push(u);}}int ans = 0;rep(i, n) if (used[i]) ans++;cout << ans << '\n';return 0;
}

D. 2x2 Erasing 2

容易发现答案不超过 \(9\)
那么最多有 \(C(49, 9)\) 种方案，于是直接暴搜即可

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;void solve() {int h, w;cin >> h >> w;vector<string> s(h);rep(i, h) cin >> s[i];int ans = 9;auto f = [&](auto& f, int now) -> void {if (now >= ans) return;rep(i, h-1)rep(j, w-1) {int cnt = 0;rep(di, 2)rep(dj, 2) if (s[i+di][j+dj] == '#') cnt++;if (cnt == 4) {rep(dj, 2) {s[i+1][j+dj] = '.';f(f, now+1);s[i+1][j+dj] = '#';}return;}}ans = min(ans, now);};f(f, 0);cout << ans << '\n';
}int main() {int t;cin >> t;while (t--) solve();return 0;
}

E. Cut in Half

用大根堆来维护二元组 (值，数量)，批量处理相同长度的木棍的切割操作

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;void solve() {int n, k, x;cin >> n >> k >> x;using P = pair<double, int>;priority_queue<P> q;rep(i, n) {int a;cin >> a;q.emplace(a, 1);}while (k) {auto [l, c] = q.top(); q.pop();if (k < c) {q.emplace(l, c-k);c = k;}k -= c;q.emplace(l/2, c*2);}while (1) {auto [l, c] = q.top(); q.pop();x -= c;if (x <= 0) {printf("%.10f\n", l);return;}}
}int main() {int t;cin >> t;while (t--) solve();return 0;
}

F. Adding Chords

性质：

区间