A
\(\text{379187662194355221}\)。
\(\text{dp}\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<vector<i64>> f(2023, vector<i64>(11));
f[0][0] = 1;
for (int i = 1; i <= 2022; i++) {
for (int j = 1; j <= 10; j++) {
if (i >= j) {
f[i][j] = f[i - j][j - 1] + f[i - j][j];
}
}
}
cout << f[2022][10] << '\n';
return 0;
}
B
\(\text{4 48 0}\)
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int s = 0; s <= 6; s++) {
for (int f = 0; f < 60; f++) {
for (int m = 0; m < 60; m++) {
double S = s * 30 + f * 0.5 + m * (1.0 / 120);
double F = f * 6 + m * 0.1;
double M = m * 6;
double A = abs(F - S);
if (A > 180) {
A = 360 - A;
}
double B = abs(F - M);
if (B > 180) {
B = 360 - B;
}
if (A == 2 * B) {
cout << s << ' ' << f << ' ' << m << '\n';
}
}
}
}
return 0;
}
C
二分，\(O(n\log n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
i64 m;
cin >> n >> m;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
int l = 0, r = 1E9;
int ans = 0;
auto check = [&](int x) {
int res = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= x) {
continue;
}
if (x - a[i] > b[i]) {
return false;
}
res += x - a[i];
}
return res <= m;
};
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
cout << ans << '\n';
return 0;
}
D
\(\text{dfs}\)，\(O(2^{17})\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int a, b;
cin >> s >> a >> b;
i64 ans = 0;
int len = s.size();
function<void(int, i64)> dfs = [&](int j, i64 res) {
if (j == len) {
ans = max(ans, res);
return;
}
int num = s[j] - '0';
int o1 = min(a, 9 - num);
a -= o1;
dfs(j + 1, res * 10 + num + o1);
a += o1;
if (b - num > 0) {
b -= num + 1;
dfs(j + 1, res * 10 + 9);
b += num + 1;
}
};
dfs(0, 0);
cout << ans << '\n';
return 0;
}
E
\(\text{dijkstra}\) 板题。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<array<int, 2>>> g(n);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].push_back({v, w + a[v]});
g[v].push_back({u, w + a[u]});
}
constexpr i64 inf = 1E18;
vector<i64> dis(n, inf);
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
dis[0] = 0;
q.push({0, 0});
while (!q.empty()) {
auto d = q.top().first;
auto cur = q.top().second;
q.pop();
if (d > dis[cur]) {
continue;
}
for (auto p : g[cur]) {
int nex = p[0];
int w = p[1];
if (dis[nex] > d + w) {
dis[nex] = d + w;
q.push({dis[nex], nex});
}
}
}
cout << dis[n - 1] - a[n - 1] << '\n';
return 0;
}
H
\(\text{lca}\)，\(O(m\log n+n\log n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> dep(n + 1, 0);
vector<vector<int>> p(n + 1, vector<int>(__lg(n + 1) + 1));
vector<i64> sum(n + 1);
function<void(int, int)> dfs = [&](int cur, int pre) {
p[cur][0] = pre;
dep[cur] = dep[pre] + 1;
for (int i = 1; i <= __lg(dep[cur]); i++) {
p[cur][i] = p[p[cur][i - 1]][i - 1];
}
for (auto nex : g[cur]) {
if (nex != pre) {
sum[nex] = sum[cur] + (int) g[nex].size();
dfs(nex, cur);
}
}
};
dfs(1, 0);
auto lca = [&](int x, int y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
for (int i = __lg(dep[x] - dep[y]); i >= 0; i--) {
if(dep[p[x][i]] >= dep[y]) {
x = p[x][i];
}
}
if (x == y) {
return x;
}
for (int i = __lg(dep[x]); i >= 0; i--) {
if(p[x][i] != p[y][i]) {
x = p[x][i];
y = p[y][i];
}
}
return p[x][0];
};
auto dis = [&](int x, int y) {
int LCA = lca(x, y);
return sum[x] + sum[y] - 2 * sum[LCA] + (int) g[LCA].size();
};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
cout << dis(u, v) << '\n';
}
return 0;
}
I
枚举倍数，\(O(n\log n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
constexpr int N = 2E5;
vector<int> ok(N + 1);
vector<int> cnt(N + 1);
vector<int> ans(N + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ok[x] = 1;
cnt[x]++;
if (cnt[x] >= 2) {
ans[1] = 1;
}
}
if (n == 1) {
ans[1] = 1;
}
for (int i = 1; i <= N; i++) {
for (int j = 2; i * j <= N; j++) {
if (ok[i] && ok[i * j]) {
ans[j] = 1;
}
}
}
for (int i = 0; i < m; i++) {
int x;
cin >> x;
cout << (ans[x] ? "YES" : "NO") << '\n';
}
return 0;
}