|
|
个人题解，仅供参考。QAQ
A
签到。
4430091。
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 = 100000000;
int ans = 0;
for (int i = 1; i <= n; i++) {
string s = to_string(i);
int m = s.size();
if (m % 2 == 0) {
int half = 0, sum = 0;
for (auto &si : s) {
sum += si - &#39;0&#39;;
}
for (int j = 0; j < m / 2; j++) {
half += s[j] - &#39;0&#39;;
}
if (half + half == sum) {
ans++;
}
}
}
cout << ans << &#39;\n&#39;;
return 0;
}
B
搜索。
8335366。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int ans = 0;
function<void(int, int)> dfs = [&](int i, int sum) {
if (sum == 70) {
ans++;
}
if (sum == 100) {
return;
}
if (i == 30) {
return;
}
dfs(i + 1, sum + 10);
dfs(i + 1, 0);
};
dfs(0, 0);
cout << ans << &#39;\n&#39;;
return 0;
}
C
打表找规律，复杂度 O(1)。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int l, r;
cin >> l >> r;
auto get = [&](int x) {
if (x == 0) {
return 0;
}
if (x <= 2) {
return 1;
}
x -= 2;
return x / 4 * 3 + x % 4 + 1;
};
cout << get(r) - get(l - 1) << &#39;\n&#39;;
return 0;
}
D
dp，复杂度 O(n^{2})。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
constexpr int N = 5000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> a(n);
for (int i = 0; i < n; i++) {
a = s - &#39;0&#39;;
}
vector<bitset<N + 1>> f(n);
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (a[l] == a[r]) {
f[l][r] = f[l + 1][r - 1];
} else if (a[l] > a[r]) {
f[l][r] = 1;
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ans += f[j];
}
}
cout << ans << &#39;\n&#39;;
return 0;
}
E
树上启发式合并，\text{totcnt} 表示子树中出现了多少种不同的颜色，\text{res} 表示子树中出现次数等于出现最多颜色出现次数的颜色数，复杂度 O(n\log n)。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> c(n), f(n);
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
cin >> c >> f;
f--;
c--;
if (f != -1) {
g[f].push_back(i);
}
}
int ans = 0;
vector<i64> siz(n);
vector<int> l(n), r(n), dfn(n), son(n, -1), cnt(n);
i64 res = 0, mxc = 0, totcnt = 0;
int tot = -1;
auto add = [&](int cur) {
if (cnt[c[cur]] == 0) {
totcnt++;
}
cnt[c[cur]]++;
if (cnt[c[cur]] == mxc) {
res++;
} else if (cnt[c[cur]] > mxc) {
mxc = cnt[c[cur]];
res = 1;
}
};
auto del = [&](int cur) {
cnt[c[cur]]--;
if (cnt[c[cur]] == 0) {
totcnt--;
}
res = mxc = 0;
};
function<void(int, int)> dfs = [&](int cur, int pre) {
l[cur] = ++tot;
dfn[tot] = cur;
siz[cur] = 1;
for (auto &nex : g[cur]) {
if (nex != pre) {
dfs(nex, cur);
siz[cur] += siz[nex];
if (son[cur] == -1 || siz[son[cur]] < siz[nex]) {
son[cur] = nex;
}
}
}
r[cur] = tot;
};
function<void(int, int, bool)> dfs_again = [&](int cur, int pre, bool ok) {
for (auto &nex : g[cur]) {
if (nex != pre && nex != son[cur]) {
dfs_again(nex, cur, 0);
}
}
if (son[cur] != -1) {
dfs_again(son[cur], cur, 1);
}
for (auto &nex : g[cur]) {
if (nex != pre && nex != son[cur]) {
for (int i = l[nex]; i <= r[nex]; i++) {
add(dfn);
}
}
}
add(cur);
ans += (res == totcnt);
if (!ok) {
for (int i = l[cur]; i <= r[cur]; i++) {
del(dfn);
}
}
};
dfs(0, -1);
dfs_again(0, -1, 0);
cout << ans << &#39;\n&#39;;
return 0;
}
F
折半搜索，复杂度 O(3^{\frac{n}{2}})。
B=0 表示切一刀并买那个瓜，B=1 表示不切并买那个瓜，B=2 表示不买。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
m *= 2;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a;
}
int N = n / 2;
unordered_map<int, int> mp(1024);
mp.max_load_factor(0.25);
mp[0] = 0;
function<void(int, int, int, i64)> dfs = [&](int j, int B, int res, i64 sum) {
if (sum >= m || j == N) {
if (sum <= m) {
mp[sum] = res;
}
return;
}
if (B == 0) {
sum += a[j];
res++;
} else if (B == 1) {
sum += a[j] * 2;
}
for (int i = 0; i < 3; i++) {
dfs(j + 1, i, res, sum);
}
};
for (int i = 0; i < 3; i++) {
dfs(0, i, 0, 0);
}
int ans = 1E9;
function<void(int, int, int, i64)> dfs_again = [&](int j, int B, int res, i64 sum) {
if (sum >= m || j == n) {
if (sum <= m && mp.count(m - sum)) {
ans = min(ans, mp[m - sum] + res);
}
return;
}
if (B == 0) {
sum += a[j];
res++;
} else if (B == 1) {
sum += a[j] * 2;
}
for (int i = 0; i < 3; i++) {
dfs_again(j + 1, i, res, sum);
}
};
for (int i = 0; i < 3; i++) {
dfs_again(N, i, 0, 0);
}
cout << ans << &#39;\n&#39;;
return 0;
}
G
kruskal 重构树，lca，复杂度 O(n\log n+m\log n+q\log n)。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
struct UnionFind {
int n;
vector<int> f;
UnionFind(const int &n) : n(n), f(n) {
iota(f.begin(), f.end(), 0);
}
int get(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unite(int x, int y) {
int gx = get(x), gy = get(y);
if (gx != gy) {
f[gx] = gy;
return 1;
}
return 0;
}
bool united(int x, int y) {
return get(x) == get(y);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 3>> e(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
e = {w, u, v};
}
sort(e.begin(), e.end(), greater<array<int, 3>>());
int N = 2 * n + 1;
UnionFind f(N);
int node = n + 1;
vector<int> val(N);
vector<vector<int>> g(N);
for (int i = 0; i < m; i++) {
int w = e[0];
int u = e[1];
int v = e[2];
int gu = f.get(u);
int gv = f.get(v);
if (gu != gv) {
f.unite(u, node);
f.unite(v, node);
val[node] = w;
g[node].push_back(gu);
g[node].push_back(gv);
node++;
if (node == N - 1) {
break;
}
}
}
vector<int> dep(node, 1);
vector<int> vis(node);
vector<vector<int>> p(node, vector<int>(__lg(node) + 1));
function<void(int, int)> dfs = [&](int cur, int pre) {
p[cur][0] = pre;
vis[cur] = 1;
for (int i = 1; i <= __lg(dep[cur]); i++) {
p[cur] = p[p[cur][i - 1]][i - 1];
}
for (auto &nex : g[cur]) {
if (nex != pre) {
dep[nex] = dep[cur] + 1;
dfs(nex, cur);
}
}
};
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]] >= dep[y]) {
x = p[x];
}
}
if (x == y) {
return x;
}
for (int i = __lg(dep[x]); i >= 0; i--) {
if (p[x] != p[y]) {
x = p[x];
y = p[y];
}
}
return p[x][0];
};
for (int i = node - 1; i >= 1; i--) {
if (!vis) {
dfs(i, 0);
}
}
for (int i = 0; i < q; i++) {
int u, v;
cin >> u >> v;
if (!f.united(u, v)) {
cout << -1 << &#39;\n&#39;;
} else {
cout << val[lca(u, v)] << &#39;\n&#39;;
}
}
return 0;
}
H
先跑个异或前缀和，按位算贡献，令 xor(l,r) 表示第 l 项到第 r 项的异或和，考虑第 j 位为 1，当且仅当 xor(0,r) 与 xor(0,l-1) 第 j 位的值不同，固定右端点 r，算出有多少个 l 使得 xor(l,r) 第 j 位的值为 1。复杂度 O(21\cdot n)。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a;
}
vector<int> xorsum(n + 1);
for (int i = 0; i < n; i++) {
xorsum[i + 1] = xorsum ^ a;
}
i64 ans = 0;
for (int j = 0; j < 21; j++) {
int c[] = {1, 0};
int add = 0;
for (int i = 0; i < n; i++) {
int B = xorsum[i + 1] >> j & 1;
add += c[B ^ 1];
c[B]++;
}
ans += (1 << j) * add;
}
cout << ans << &#39;\n&#39;;
return 0;
}
I
分行，搜索，剪枝，由于题目保证有唯一解，所以搜索的复杂度是正确的。
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a;
}
vector<vector<int>> ans(n, vector<int>(m, -1));
auto get = [&](int i, int j) {
array<int, 3> res = {0, 0, 0};
for (int mx = -1; mx <= 1; mx++) {
for (int my = -1; my <= 1; my++) {
int I = i + mx;
int J = j + my;
if (I < 0 || I >= n) {
continue;
}
if (J < 0 || J >= m) {
continue;
}
if (ans[I][J] == 1) {
res[1]++;
} else if (ans[I][J] == 0) {
res[0]++;
} else {
res[2]++;
}
}
}
return res;
};
auto check = [&](int i) {
for (int j = 0; j < m; j++) {
if (a[j] >= &#39;0&#39; && a[j] <= &#39;9&#39;) {
int num = a[j] - &#39;0&#39;;
auto x = get(i, j);
int zero = x[0];
int one = x[1];
int no = x[2];
if (one > num) {
return false;
}
if (no + one < num) {
return false;
}
}
}
return true;
};
function<void(int, int)> dfs = [&](int i, int j) {
if (i == n) {
for (int I = 0; I < n; I++) {
for (int J = 0; J < m; J++) {
cout << ans[I][J];
}
cout << &#39;\n&#39;;
}
return;
}
if (j == m) {
if (i > 0) {
if (check(i - 1) && check(i)) {
dfs(i + 1, 0);
}
} else if (check(i)) {
dfs(i + 1, 0);
}
return;
}
ans[j] = 1;
dfs(i, j + 1);
ans[j] = 0;
dfs(i, j + 1);
ans[j] = -1;
};
dfs(0, 0);
return 0;
}
J
莫比乌斯函数绝对值求和。
就是求 \sum\limits_{i=1}^{n}\mu^{2}(i)。
给出 O(\sqrt{n}) 的解法，70\%。
\mu^{2}(i)=\sum\limits_{d^{2}|i}\mu(d)
\sum\limits_{i=1}^{n}\mu^{2}(i)=\sum\limits_{i=1}^{n}\sum\limits_{d^{2}|i}\mu(d)=\sum\limits_{d=1}^{\lfloor\sqrt{n}\rfloor}\mu(d)\sum\limits_{d^{2}|i}1=\sum\limits_{d=1}^{\lfloor\sqrt{n}\rfloor}\mu(d)\cdot \lfloor\frac{n}{d^{2}}\rfloor
C++ Code
#include &#34;bits/stdc++.h&#34;
using namespace std;
using i64 = long long;
vector<int> isprime;
vector<int> primes;
vector<int> mu;
void sieve(int N) {
isprime.assign(N + 1, 1);
mu.assign(N + 1, 0);
mu[1] = 1;
for (int i = 2; i <= N; i++) {
if (isprime) {
primes.push_back(i);
mu = -1;
}
for (auto p : primes) {
if (i * p > N) {
break;
}
isprime[i * p] = 0;
if (i % p == 0) {
break;
}
mu[i * p] = -mu;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n;
cin >> n;
int N = sqrt(n);
sieve(N);
i64 ans = 0;
for (int i = 1; i <= N; i++) {
ans += 1LL * mu * (n / (1LL * i * i));
}
cout << ans << &#39;\n&#39;;
return 0;
}
本文使用 Zhihu On VSCode 创作并发布 |
|
发表于 2023-4-19 19:52:22