2023 蓝桥杯国赛 C++ B 组
A
5484660609
\(O(|s|)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
for (int i = 1; i <= 2023; i++) {
s += to_string(i);
}
int N = s.size();
vector<i64> f(4);
for (int i = 0; i < N; i++) {
if (s[i] == '2') {
f[0]++;
f[2] += f[1];
} else if (s[i] == '0') {
f[1] += f[0];
} else if (s[i] == '3') {
f[3] += f[2];
}
}
cout << f[3] << '\n';
return 0;
}
B
947303
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 l = 2333;
i64 r = 23333333333333;
sieve(1E7);
i64 res = 0;
i64 ans = 0;
int N = primes.size();
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (1LL * primes[i] * primes[i] * primes[j] * primes[j] > r) {
break;
}
if (1LL * primes[i] * primes[i] * primes[j] * primes[j] <= r && 1LL * primes[i] * primes[i] * primes[j] * primes[j] >= l) {
ans++;
}
}
}
cout << ans << '\n';
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;
vector<int> mp(n + 1);
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]]++;
}
int p = 0, q = 0;
int ans = 0;
for (int i = 0; i <= n; i++) {
if (mp[i] == 1) {
p++;
} else if (mp[i] > 2) {
mp[i] -= 2;
q += mp[i];
ans += mp[i];
}
}
ans += (p - q) / 2;
cout << ans << '\n';
return 0;
}
D
瞎搞一下就行，\(O(\max(n,m))\)。
E
\(O(n^2\log n)\)
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Point = complex<i64>;
#define x real
#define y imag
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
map<pair<int, int>, int> vis;
int n;
cin >> n;
vector<Point> a(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a[i] = Point(x, y);
vis[{x, y}] = 1;
}
i64 ans = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
unordered_map<i64, int> mp;
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
mp[norm(a[i] - a[j])]++;
Point p = 2LL * a[i] - a[j];
if (vis.count({p.x(), p.y()})) {
cnt++;
}
}
for (auto &x : mp) {
ans += 1LL * x.second * (x.second - 1) / 2;
}
ans -= cnt / 2;
}
cout << ans << '\n';
return 0;
}
F
无向图缩边双跑 \(\text{tarjan}\)。
#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<pair<int, int>>> g(n);
vector<array<int, 2>> e(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back({v, i});
g[v].push_back({u, i});
e[i] = {u, v};
}
vector<int> dfn(n, -1), low(n, -1), be(n, -1);
int tot = 0;
vector<int> ban(m);
function<void(int, int)> tarjan = [&](int cur, int pre) {
dfn[cur] = low[cur] = tot++;
for (auto &[nex, j] : g[cur]) {
if (nex != pre) {
if (dfn[nex] == -1) {
tarjan(nex, cur);
low[cur] = min(low[cur], low[nex]);
if (low[nex] > dfn[cur]) {
ban[j] = 1;
}
} else {
low[cur] = min(low[cur], dfn[nex]);
}
}
}
};
for (int i = 0; i < n; i++) {
if (dfn[i] == -1) {
tarjan(i, -1);
}
}
int cnt = 0;
vector<int> vis(n);
function<void(int)> dfs = [&](int cur) {
be[cur] = cnt;
vis[cur] = 1;
for (auto &[nex, j] : g[cur]) {
if (!vis[nex] && !ban[j]) {
dfs(nex);
}
}
};
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i);
cnt++;
}
}
i64 sum = 0;
vector<int> sz(cnt);
for (int i = 0; i < n; i++) {
sz[be[i]] += a[i];
sum += a[i];
}
vector<vector<int>> G(cnt);
for (int i = 0; i < m; i++) {
if (ban[i]) {
int u = e[i][0];
int v = e[i][1];
u = be[u];
v = be[v];
if (u == v) {
continue;
}
G[u].push_back(v);
G[v].push_back(u);
}
}
if (cnt <= 1) {
cout << -1 << '\n';
return 0;
}
function<void(int, int)> dfs1 = [&](int cur, int pre) {
for (auto &nex : G[cur]) {
if (nex != pre) {
dfs1(nex, cur);
sz[cur] += sz[nex];
}
}
};
dfs1(0, -1);
i64 ans = 1E18;
for (int i = 0; i < cnt; i++) {
ans = min(ans, abs(sum - sz[i] - sz[i]));
}
cout << ans << '\n';
return 0;
}
G
dp 一下，\(O(n\cdot m)\)。
H
\(O(2\cdot 10^6)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int N = 2E6;
i64 sum[N + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
l *= 2;
r *= 2;
int m = (l + r) >> 1;
sum[m]++;
}
for (int i = 1; i <= N; i++) {
sum[i] += sum[i - 1];
}
for (int i = 0; i < m; i++) {
int L, R;
cin >> L >> R;
L *= 2;
R *= 2;
cout << sum[R] - sum[L - 1] << '\n';
}
return 0;
}