链接：https://codeforc.es/gym/104076
A. Tower
枚举最后的取值，然后计算每个数变成这个取值的最⼩次数，去掉最大的 \(m\) 个，取 \(\min\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
// constexpr int M = 998244353;
// constexpr int M = 1000000007;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
set<int> s;
for (int i = 0; i < n; i++) {
cin >> a[i];
int x = a[i];
while (x) {
s.insert(x);
x >>= 1;
}
}
i64 ans = 9E18;
for (auto aim : s) {
auto get = [&](int x) {
if (x - aim <= 0) {
return aim - x;
}
int res = 0;
while (x / 2 >= aim) {
x /= 2;
res++;
}
int tmp = res + x - aim;
if (x / 2 > 0) {
x /= 2;
return min(tmp, res + 1 + aim - x);
} else {
return tmp;
}
};
vector<int> tmp;
for (int i = 0; i < n; i++) {
tmp.push_back(get(a[i]));
}
sort(tmp.begin(), tmp.end());
i64 res = 0;
for (int i = 0; i < n - m; i++) {
res += tmp[i];
}
ans = min(ans, res);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
D. Frozen Scoreboard
模拟，直接枚举子集。贪心分配时间。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
vector<char> ch(m);
vector<int> x(m), y(m);
int time = 0;
int cnt = 0;
vector<int> maybe;
for (int j = 0; j < m; j++) {
cin >> ch[j];
char useless;
if (ch[j] == '+') {
cin >> x[j] >> useless >> y[j];
cnt++;
time += 20 * (x[j] - 1) + y[j];
} else if (ch[j] == '?') {
cin >> x[j] >> y[j];
maybe.push_back(j);
} else if (ch[j] == '-') {
cin >> y[j];
}
}
int SIZE = maybe.size();
bool ok = 0;
for (int j = 0; j < (1 << SIZE); j++) {
int tmpcnt = cnt;
int mn = time, mx = time;
for (int k = 0; k < SIZE; k++) {
if (j >> k & 1) {
tmpcnt++;
mn += 240 + 20 * (y[maybe[k]] - x[maybe[k]]);
mx += 299 + 20 * (y[maybe[k]] - 1);
}
}
if (tmpcnt == a[i] && b[i] >= mn && b[i] <= mx) {
ok = 1;
b[i] -= mn;
for (int k = 0; k < SIZE; k++) {
if (j >> k & 1) {
int L = 240 + 20 * (y[maybe[k]] - x[maybe[k]]), R = 299 + 20 * (y[maybe[k]] - 1);
if (b[i] == 0) {
x[maybe[k]] = y[maybe[k]] - x[maybe[k]] + 1;
y[maybe[k]] = 240;
} else if (b[i] >= R - L) {
x[maybe[k]] = y[maybe[k]];
y[maybe[k]] = 299;
b[i] -= (R - L);
} else {
for (int l = 0; l < x[maybe[k]]; l++) {
int p = b[i] - l * 20;
if (p >= 0 && p <= 59) {
x[maybe[k]] = y[maybe[k]] - x[maybe[k]] + l + 1;
y[maybe[k]] = 240 + p;
b[i] = 0;
break;
}
}
}
ch[maybe[k]] = '+';
} else {
ch[maybe[k]] = '-';
}
}
break;
}
}
if (ok) {
cout << "Yes" << '\n';
for (int k = 0; k < m; k++) {
if (ch[k] == '+') {
cout << ch[k] << ' ' << x[k] << '/' << y[k] << '\n';
} else if (ch[k] == '-') {
cout << ch[k] << ' ' << y[k] << '\n';
} else {
cout << ch[k] << '\n';
}
}
} else {
cout << "No" << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
for (int _ = 0; _ < tt; _++) {
solve();
}
return 0;
}
E. Identical Parity
先分组，\(\lfloor \frac{n}{k}\rfloor\) 个长度为 \(k\) 的组，\(1\) 个长度为 \((n% k)\) 的组，前面 \(k\) 个组奇数偶数差不多一样多，那么每一组奇数的数量是 \(\lceil \frac{k}{2}\rceil\)，偶数的数量是 \(\lfloor \frac{k}{2}\rfloor\)，组内可以乱排，就看最后一组行不行。
\(n\) 个数，\(\lfloor \frac{n}{2}\rfloor\) 个偶数，\(\lceil \frac{n}{2}\rceil\) 个奇数。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
// constexpr int M = 998244353;
// constexpr int M = 1000000007;
void solve() {
int n, k;
cin >> n >> k;
if (k % 2 == 0) {
cout << "Yes" << '\n';
return;
}
int odd = (n + 1) / 2 - (k + 1) / 2 * (n / k);
int even = n / 2 - k / 2 * (n / k);
if (odd >= 0 && odd <= (k + 1) / 2 && even >= 0 && even <= k / 2) {
cout << "Yes" << '\n';
return;
}
cout << "No" << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
K. Stack Sort
签到，只有 \(a_i + 1\) 在前面出现过 \(ans\) 才不用加 \(1\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
// constexpr int M = 998244353;
// constexpr int M = 1000000007;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
vector<int> vis(n + 1);
int ans = 0;
for (int i = 0; i < n; i++) {
if (!vis[a[i] + 1]) {
ans++;
}
vis[a[i]] = 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
M. Best Carry Player
与顺序无关。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
// constexpr int M = 998244353;
// constexpr int M = 1000000007;
void solve() {
int n;
cin >> n;
i64 sum = 0;
i64 ans = 0;
for (int i = 0; i < n; i++) {
i64 x;
cin >> x;
string s = to_string(x);
for (auto x : s) {
ans += x - '0';
}
sum += x;
}
string s = to_string(sum);
for (auto x : s) {
ans -= x - '0';
}
cout << ans / 9 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}