A. Cut
模拟
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
rotate(a.begin(), a.begin()+(n-k), a.end());
rep(i, n) cout << a[i] << ' ';
return 0;
}
B. Decrease 2 max elements
模拟
代码实现
#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<int> a(n);
rep(i, n) cin >> a[i];
int ans = 0;
while (1) {
ranges::sort(a, greater<>());
if (a[1] <= 0) break;
a[0]--; a[1]--;
ans++;
}
cout << ans << '\n';
return 0;
}
C. Triple Attack
周期性
把 {1, 1, 3} 看成是一个组合技，用这 \(3\) 次攻击可以让敌人掉 \(5\) 点血
对每个敌人先尽可能地用组合技，如果还有剩余血量，就暴力模拟即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<int> h(n);
rep(i, n) cin >> h[i];
ll t = 0;
rep(i, n) {
int x = h[i]/5;
t += x*3;
h[i] -= x*5;
while (h[i] > 0) {
t++;
if (t%3 == 0) h[i] -= 3;
else h[i]--;
}
}
cout << t << '\n';
return 0;
}
D. Minimum Steiner Tree
一个点被保留当且仅当以它为根的子树中包含关键点
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<vector<int>> to(n);
rep(i, n-1) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> vs(k);
rep(i, k) cin >> vs[i], vs[i]--;
vector<bool> selected(n);
rep(i, k) selected[vs[i]] = true;
vector<int> num(n);
auto dfs = [&](auto& f, int v, int p=-1) -> void {
if (selected[v]) num[v]++;
for (int u : to[v]) {
if (u == p) continue;
f(f, u, v);
num[v] += num[u];
}
};
dfs(dfs, vs[0]);
int ans = 0;
rep(i, n) if (num[i] > 0) ans++;
cout << ans << '\n';
return 0;
}