AtCoder Beginner Contest 372seo优化

AtCoder Beginner Contest 372

news/2024/9/21 22:24:16

省流版

A. 暴力即可
B. 转换3进制即可
C. 考虑答案的组成，仅修改发生变化的部分即可
D. 维护答案数组$ans_i$，考虑枚举 $j$对哪些 $i$有贡献，通过单调栈找到对应的区间$i$ ，通过差分维护区间加法即可
E. 并查集维护连通块，$set$维护点标号大小，合并$set$时启发式合并，查询则从对应连通块的$set$最大值往前找$k$次即可
F. 考虑朴素$dp$，发现有效转移只有 $O(mk)$ 个，记忆化搜索即可

A - delete . (abc372 A)

题目大意

给定一个字符串，删除其中的.。

解题思路

依次判断每个字符，如果不是.就输出。

python可以一行，

神奇的代码

print(input().replace('.', ''))

B - 3^A (abc372 B)

题目大意

给定一个$m$，将其表达成若干个 $3$的幂的和。

解题思路

其实就是将$m$转换成三进制，看三进制下每一个幂的系数。

进制转换一下即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int m;cin >> m;vector<int> ans;for (int i = 0; i <= 10; ++i) {int cnt = m % 3;while (cnt--) {ans.push_back(i);}m /= 3;}cout << ans.size() << '\n';for (auto i : ans)cout << i << " ";cout << '\n';return 0;
}

C - Count ABC Again (abc372 C)

题目大意

给定一个字符串$s$，进行以下$q$次操作。

每次操作，将$s_x = c$。问操作完后，字符串 ABC在$s$的出现次数。

解题思路

记$f(i) = 1/0$表示 $s_is_{i+1}s_{i+2}$是/不是 ABC。

答案就是$\sum_{i = 1}^{n} f(i)$。

每次修改，其实只有 $3$个 $f(i)$的值可能发生变化。

因此先计算出 $\sum_{i = 1}^{n} f(i)$，然后对于每次修改，先减去$f(x-2)+f(x-1)+f(x)$个，然后修改字符后，重新计算$f(x-2)+f(x-1)+f(x)$即可得到新的答案，而不需要重新计算 $\sum_{i = 1}^{n} f(i)$。

时间复杂度就为$O(q)$。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, q;string s;cin >> n >> q >> s;int ans = 0;auto in_range = [&](int i) { return i >= 0 && i < n; };auto check = [&](int x) {for (int i = 0; i < 3; ++i)if (!in_range(x + i) || s[x + i] != 'A' + i)return false;return true;};for (int i = 0; i < n; ++i) {ans += check(i);}while (q--) {int x;string c;cin >> x >> c;--x;for (int i = x - 2; i <= x; ++i) {ans -= check(i);}s[x] = c[0];for (int i = x - 2; i <= x; ++i) {ans += check(i);}cout << ans << '\n';}return 0;
}

D - Buildings (abc372 D)

题目大意

给定$n$个数的数组 $a$，对于每个 $i \in [1,n]$ ，问$j$的数量满足 $(i,j]$中 $a_j$是最大值。

解题思路

如果枚举$i$，求 $j$，复杂度是 $O(n^2)$。

反过来，枚举 $j$，考虑它会对哪些 $i$有 $1$的贡献。会发现只要满足$\max(a[i+1..j]) \leq j$，那么这个 $j$就会对 $i$有 $1$的贡献。

即对于每个数$a_j$，我们找其左边第一个$a_l > a_j$，那么$ans[l..j-1] += 1$

对于第一个，如何找到其左边第一个$a_l > a_j$呢？这是一个经典问题，从右往左，用单调栈维护一个递减的数列即可（栈顶到栈底是递减的）。

对于第二个，有若干次区间加法，但最后只有一次查询，可以用差分数组将区间加变成单点修改，最后还原出答案数组即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;vector<int> h(n);for (auto& x : h)cin >> x;stack<int> s;vector<int> diff(n + 1);for (int i = n - 1; i >= 0; i--) {while (!s.empty() && h[s.top()] < h[i]) {diff[i]++;diff[s.top()]--;s.pop();}s.push(i);}while (!s.empty()) {diff[0]++;diff[s.top()]--;s.pop();}int ans = 0;for (int i = 0; i < n; ++i) {ans += diff[i];cout << ans << " \n"[i == n - 1];}return 0;
}

E - K-th Largest Connected Components (abc372 E)

题目大意

给定$n$个点，初始无边。维护两类操作。

1 u v，连一条无向边$u \to v$
2 v k，找$v$所在连通块的第 $k$大的点的标号。

$k \leq 10$。

解题思路

注意到$k \leq 10$，如果能用 $set$维护一个连通块的所有点的标号，那么直接从 rbegin()暴力数$k$个就是答案，

如果维护这个 $set$呢？连通块的信息自然用并查集维护，当合并两个连通块时，其 $set$也要合并，我们可以将小的 $set$合并到大的 $set$中，即启发式合并，每次合并 $set$最坏的复杂度是 $O(n)$，但最坏情况下，合并后的 $set$大小会翻倍，最多翻倍 $log$次就达到 $n$个点，即最坏情况的出现次数只有 $O(\log n)$次，因此启发式合并的时间复杂度是 $O(n \log n)$。

维护好 $set$后，直接从 $rbegin()$数 $k$个点即为答案。特判少于$k$个点的情况。

时间复杂度是 $O((n + qk) \log n)$

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;class dsu {public:vector<int> p;vector<int> sz;vector<set<int>> node;int n;dsu(int _n) : n(_n) {p.resize(n);sz.resize(n);node.resize(n);iota(p.begin(), p.end(), 0);fill(sz.begin(), sz.end(), 1);for (int i = 0; i < n; i++) {node[i].insert(i);}}inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }inline bool unite(int x, int y) {x = get(x);y = get(y);if (x != y) {if (sz[x] < sz[y])swap(x, y);node[x].insert(node[y].begin(), node[y].end());p[y] = x;sz[x] += sz[y];return true;}return false;}
};int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, q;cin >> n >> q;dsu d(n);while (q--) {int op;cin >> op;if (op == 1) {int u, v;cin >> u >> v;--u, --v;d.unite(u, v);} else {int v, k;cin >> v >> k;--v;int fa = d.get(v);if (d.node[fa].size() < k) {cout << -1 << '\n';} else {auto it = d.node[fa].rbegin();advance(it, k - 1);cout << *it + 1 << '\n';}}}return 0;
}

F - Teleporting Takahashi 2 (abc372 F)

题目大意

给定一张有向图，它首先是个环，然后在此基础上加了$m \leq 50$条有向边。

问从 $1$号点出发，走 $k$个点，所形成的点的路径 $(1,v_1,v_2,...,v_k)$的情况数。

解题思路

考虑朴素搜索，设$dp[u][k]$表示从 $u$号点走 $k$步的方案数，显然其答案就是 $\sum_{u \to v}dp[v][k-1]$。

但这复杂度是 $O(nk)$，显然过不了。

但注意到有很多点 $u \to v$的 $v$其实只有一个即 $u+1$，即只有一种走法，它们的转移显然是没必要的。我们可以只考虑有分叉点的 $u$。而这有分叉点的 $u$最多只有 $m$个。因此如果我们的转移是从 $u \to $分叉点，这样的时间复杂度就是 $O(mk)$，是可以通过的。

记当前点$u$，然后找到 $u$后第一个分叉点 $x$，其出度$> 1$，那么 $dp[u][k] = \sum_{x \to y}dp[y][k^\prime]$，转移后$k^\prime$可以通过简单的运算得到，即$k - dis(u \to x) - 1$。

有效的$u$就只有 $2m$个，对 $dp$进行记忆化搜索，复杂度即为 $O(mk)$。因为用$map$来记忆化会超时，所以只好离散化有效的 $u$，转成数组来记忆化了。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;const int mo = 998244353;int main(void) {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m, k;cin >> n >> m >> k;vector<vector<int>> edge(n);for (int i = 0; i < n; i++) {edge[i].push_back((i + 1) % n);}vector<int> tr;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;u--;v--;edge[u].push_back(v);tr.push_back(u);}for (int i = 0; i < n; i++) {sort(edge[i].begin(), edge[i].end());edge[i].erase(unique(edge[i].begin(), edge[i].end()), edge[i].end());}sort(tr.begin(), tr.end());tr.erase(unique(tr.begin(), tr.end()), tr.end());auto calc = [&](int u, int v) -> int {if (u > v)v += n;return v - u;};int ans = 0;if (m == 0) {ans = 1;} else {vector<int> nxt(n);for (int i = 0; i < n; i++) {auto it = lower_bound(tr.begin(), tr.end(), i);if (it == tr.end())it = tr.begin();nxt[i] = *it;}vector<int> id(n, -1);int cnt = 0;auto dfs_pre = [&](auto& dfs, int u) -> void {if (id[u] != -1)return;id[u] = cnt++;int it = nxt[u];for (int v : edge[it]) {dfs(dfs, v);}};dfs_pre(dfs_pre, 0);vector<vector<int>> dp(k + 1, vector<int>(cnt, -1));auto dfs = [&](auto& dfs, int u, int k) -> int {if (k == 0) {return 1;}if (dp[k][id[u]] != -1)return dp[k][id[u]];int it = nxt[u];int sum = 0;int nxt = (u + 1) % n;int cost = calc(u, it);if (cost >= k)return 1;for (int v : edge[it]) {sum += dfs(dfs, v, k - cost - 1);if (sum >= mo)sum -= mo;}return dp[k][id[u]] = sum;};ans = dfs(dfs, 0, k);}cout << ans << '\n';return 0;
}