应该是最近最水的 ABC 了吧。
「ABC 205A」kcal
Link.
略
#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
ll a, b;
std::cin >> a >> b;
std::cout << b * a / 100.0 << "\n";
return 0;
}
「ABC 205B」Permutation Check
Link.
排序 / std::set 均可。
#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, cur = 0;
std::cin >> n;
std::vector<int> a(n);
for (int &x : a) {
std::cin >> x;
--x;
}
std::sort(all(a));
for (int x : a) {
if (cur != x) {
std::cout << "No\n";
return 0;
}
++cur;
}
std::cout << "Yes\n";
return 0;
}
「ABC 205C」POW
Link.
若 \(c\) 为偶数则 \(a:=|a|,b:=|b|\)，然后比较 \(a,b\) 大小即可。
#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int a, b, c;
std::cin >> a >> b >> c;
if (c % 2 == 0) {
a = std::abs(a);
b = std::abs(b);
}
if (a > b) std::cout << ">\n";
else if (a < b) std::cout << "<\n";
else std::cout << "=\n";
return 0;
}
「ABC 205D」Kth Excluded
Link.
预处理每一个数空出来的位置，然后询问时二分分类讨论。
#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<ll> a(n), b(n);
for (ll &x : a) std::cin >> x;
for (size_t i = 0; i < a.size(); ++i) b[i] = a[i] - i - 1;
for (ll k; q; --q) {
std::cin >> k;
ll pos = std::lower_bound(all(b), k) - b.begin();
if (pos == n) std::cout << a.back() + k - b.back() << "\n";
else std::cout << a[pos] - b[pos] + k - 1 << "\n";
}
return 0;
}
「ABC 205E」White and Black Balls
Link.
答案显然是 \(\binom{n+m}{n}-\binom{n+m}{n-k-1}\)。
#include <bits/stdc++.h>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
constexpr int MOD = 1e9 + 7;
int n, m, k;
std::cin >> n >> m >> k;
std::vector<ll> fac(n + m + 1), ifac(n + m + 1);
auto pow = [&] (ll x, int y) {
ll res = 1;
for (; y; y >>= 1, x = x * x % MOD)
if (y & 1) res = res * x % MOD;
return (res + MOD) % MOD;
};
fac[0] = ifac[0] = 1;
for (int i = 1; i < n + m + 1; ++i) {
fac[i] = fac[i - 1] * i % MOD;
ifac[i] = pow(fac[i], MOD - 2);
}
auto C = [&] (int n, int k) {return n < k ? 0 : fac[n] * ifac[n - k] % MOD * ifac[k] % MOD;};
if (n - m > k) std::cout << "0\n";
else std::cout << (C(n + m, n) - C(n + m, n - k - 1) + MOD) % MOD << "\n";
return 0;
}
「ABC 205F」Grid and Tokens
Link.
网络流板题。
#include <bits/stdc++.h>
#include <atcoder/maxflow>
using ll = long long;
#define all(x) (x).begin(), (x).end()
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int h, w, n;
std::cin >> h >> w >> n;
std::vector<std::vector<int>> obj(n, std::vector<int>(2));
std::vector<int> row(h), col(w);
auto id = [&] () {
static int cnt = 0;
return cnt++;
};
const int S = id(), T = id();
for (int &x : row) x = id();
for (int &x : col) x = id();
for (std::vector<int> &x : obj) x = std::vector<int>({id(), id()});
atcoder::mf_graph<int> G(id());
for (int x : row) G.add_edge(S, x, 1);
for (int x : col) G.add_edge(x, T, 1);
for (int i = 0; i < n; ++i) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
--a, --b;
G.add_edge(obj[i][0], obj[i][1], 1);
for (int j = a; j < c; ++j) G.add_edge(row[j], obj[i][0], 1);
for (int j = b; j < d; ++j) G.add_edge(obj[i][1], col[j], 1);
}
std::cout << G.flow(S, T) << "\n";
return 0;
}