A
\(235\)
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string t = "5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";
int N = t.size();
auto check = [&](string &s, string &t) {
int j = 0;
for (int i = 0; i < N; i++) {
if (j < (int) s.size() && s[j] == t[i]) {
j++;
}
}
if (j == s.size()) {
return 1;
}
return 0;
};
int ans = 0;
string p = "2023";
int d[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int i = 1; i <= 12; i++) {
string k = to_string(i);
if (k.size() == 1) {
k = "0" + k;
}
for (int j = 1; j <= d[i]; j++) {
string q = to_string(j);
if (q.size() == 1) {
q = "0" + q;
}
string f = p + k + q;
if (check(f, t)) {
ans++;
}
}
}
cout << ans << '\n';
return 0;
}
B
\(11027421\)
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
double eps = 1E-4;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto get = [&](int x, int y) {
double zero = 1.0 * x / (1.0 * (x + y));
double one = 1.0 * y / (1.0 * (x + y));
return -(x * zero * log2(zero) + y * one * log2(one));
};
for (int i = 0; i <= 23333333; i++) {
if (abs(get(i, 23333333 - i) - 11625907.5798) <= eps) {
cout << i << '\n';
return 0;
}
}
return 0;
}
C
复杂度 \(O(n)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int mx = 1E9, mn = 0;
for (int i = 0; i < n; i ++) {
int a, b;
cin >> a >> b;
mx = min(mx, a / b);
mn = max(mn, a / (b + 1) + 1);
}
cout << mn << ' ' << mx;
return 0;
}
D
全排列，复杂度 \(O(\sum (n!))\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<array<int, 3>> a(n);
for (int i = 0; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
a[i] = {x, y, z};
}
vector<int> p(n);
for (int i = 0; i < n; i++) {
p[i] = i;
}
do {
bool ok = 1;
int j = p[0];
i64 time = a[j][0] + a[j][2];
for (int i = 1; i < n; i++) {
int j = p[i];
if (time >= a[j][0] && time <= a[j][0] + a[j][1]) {
time += a[j][2];
} else {
ok = 0;
break;
}
}
if (ok) {
cout << "YES\n";
return;
}
} while (next_permutation(p.begin(), p.end()));
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E
dp。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> pre(10, -1);
vector<int> f(n);
int ans = 0;
for (int i = 0; i < n; i++) {
int x = a[i][0] - '0';
int y = a[i].back() - '0';
if (pre[x] != -1) {
f[i] = f[pre[x]] + 1;
} else {
f[i] = 1;
}
ans = max(ans, f[i]);
pre[y] = i;
}
cout << n - ans << '\n';
return 0;
}
G
二分，复杂度 \(O(n\log n)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
string s;
char c[2] = {'a', 'a'};
cin >> k >> s >> c[0] >> c[1];
int n = s.size();
vector<vector<int>> p(2);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
if (s[i] == c[j]) {
p[j].push_back(i);
}
}
}
i64 ans = 0;
for (int i = 0; i < (int) p[0].size(); i++) {
int j = p[0][i] + k - 1;
if (p[1].back() < j) {
continue;
}
int I = lower_bound(p[1].begin(), p[1].end(), j) - p[1].begin();
int val = (int) p[1].size() - I;
ans += val;
}
cout << ans << '\n';
return 0;
}
H
优先队列，复杂度 \(O(n\log n)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 0; i < n; i++) {
q.push({a[i], i});
}
vector<int> pre(n), nex(n);
for (int i = 0; i < n; i++) {
pre[i] = i - 1;
}
for (int i = 0; i < n; i++) {
nex[i] = i + 1;
}
nex[n - 1] = -1;
while (!q.empty()) {
auto Top = q.top();
int ai = Top.first;
int i = Top.second;
q.pop();
if (ai != a[i]) {
q.push({a[i], i});
continue;
}
a[i] = -1;
int Nex = nex[i];
int Pre = pre[i];
if (Nex < n) {
a[Nex] += ai;
pre[Nex] = Pre;
}
if (Pre >= 0) {
a[Pre] += ai;
nex[Pre] = Nex;
}
k--;
if (k == 0) {
break;
}
}
vector<int> ans;
for (int i = 0; i < n; i++) {
if (a[i] != -1) {
ans.push_back(a[i]);
}
}
for (int i = 0; i < (int) ans.size(); i++) {
cout << ans[i] << " \n"[i == (int) ans.size() - 1];
}
return 0;
}
I
LCA 板子。
#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<pair<int, int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
vector<int> depth(n + 1, 1);
vector<vector<int>> p(n + 1, vector<int>(__lg(n + 1) + 1));
vector<i64> sum(n + 1);
function<void(int, int)> dfs = [&](int v, int father) {
p[v][0] = father;
for (int i = 1; i <= __lg(depth[v]); i++) {
p[v][i] = p[p[v][i - 1]][i - 1];
}
for (auto [x, w] : g[v]) {
if (x != father) {
depth[x] = depth[v] + 1;
sum[x] = sum[v] + w;
dfs(x, v);
}
}
};
dfs(1, 0);
auto lca = [&](int x, int y) {
if (depth[x] < depth[y]) {
swap(x, y);
}
for (int i = (int) __lg(depth[x] - depth[y]); i >= 0; i--) {
if(depth[p[x][i]] >= depth[y]) {
x = p[x][i];
}
}
if (x == y) {
return x;
}
for (int i = (int) __lg(depth[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];
};
vector<int> a(m + 2, -1);
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
vector<i64> b(m);
i64 all = 0;
vector<i64> D(m + 2);
for (int i = 1; i < m; i++) {
D[i] = dis(a[i], a[i+1]);
all += D[i];
}
for (int i = 1; i <= m; i++) {
i64 res = 0;
if (a[i - 1] != -1) {
res += D[ i- 1];
}
if (a[i + 1] != -1) {
i64 d = D[i];
res += d;
}
b[i - 1] = res;
}
for (int i = 0; i < m; i++) {
cout << all - b[i] << " \n"[i == m - 1];
}
return 0;
}