A - Not Too Hard (abc328 A)
题目大意
给定\(n\)个数字和一个数 \(x\)。
问不大于 \(x\)的数的和。
解题思路
按找要求累计符合条件的数的和即可。
神奇的代码
#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, x;
cin >> n >> x;
int sum = 0;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
sum += a * (a <= x);
}
cout << sum << '\n';
return 0;
}
B - 11/11 (abc328 B)
题目大意
给定一年的月数和一个月的天数。
问有多少对\((i,j)\)，表示第 \(i\)个月的第 \(j\)日， \(i,j\)的数位上每个数字都是一样的。
解题思路
范围只有\(O(100^2)\)，枚举所有的 \((i,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;
int ans = 0;
auto ok = [&](int x, int y) {
int t = x % 10;
while (x) {
if (t != x % 10)
return false;
x /= 10;
}
while (y) {
if (t != y % 10)
return false;
y /= 10;
}
return true;
};
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
for (int j = 1; j <= x; ++j) {
ans += ok(i, j);
}
}
cout << ans << '\n';
return 0;
}
C - Consecutive (abc328 C)
题目大意
给定一个字符串\(s\)和若干个询问。
每个询问问 \(s[l..r]\)子串中，有多少对相邻相同字母的下标。
解题思路
令\(a[i]=1\)表示\(s[i] == s[i + 1]\)， \(a[i] = 0\)表示 \(s[i] \neq s[i + 1]\)。
每个询问就是问 \(\sum_{i=l}^{r-1} a[i]\)。
预处理数组\(a\)前缀和 即可\(O(1)\)回答询问。
神奇的代码
#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;
vector<int> sum(n);
for (int i = 0; i < n - 1; ++i) {
sum[i] = (s[i] == s[i + 1]);
if (i)
sum[i] += sum[i - 1];
}
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
int ans = 0;
if (r)
ans += sum[r - 1];
if (l)
ans -= sum[l - 1];
cout << ans << '\n';
}
return 0;
}
D - Take ABC (abc328 D)
题目大意
给定一个仅包含ABC的字符串\(s\)，每次将最左边的ABC删除，直至不能删。
问最后的字符串。
解题思路
可以从左到右依次将\(s\)的每个字符加入栈中，一旦栈顶构成ABC就弹栈。
模拟即可。
神奇的代码
#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);
string s;
cin >> s;
string st;
for (auto& i : s) {
st += i;
if (st.size() >= 3) {
int n = st.size();
if (st.substr(st.size() - 3) == "ABC") {
st.pop_back();
st.pop_back();
st.pop_back();
}
}
}
cout << st << '\n';
return 0;
}
E - Modulo MST (abc328 E)
题目大意
给定一张图，问模\(k\)意义下的最小生成树的代价。
解题思路
注意是模\(k\)意义下的最小代价，在求生成树过程中的每一个值都有可能在加入某条边后超过\(k\)而变的最小，成为最后的答案。
注意点数只有\(8\)，边数最多也只有 \(28\)，因此总的方案数只有 \(2^{28}=2e8\)。暴力可行。即可以保留中间的所有结果。
设想一下\(prim\)求生成树做法，从\(1\)号点不断往外拓展。借用这个想法，设 \(dp[i]\)表示所有点与\(1\)号点连通性为 \(i\)的情况下，所有生成树的结果（\(i\&1=0\)的所有情况都是不合法的)。很显然\(dp[1] = [0]\)
然后枚举下一条边连接，更新所有结果即可。由于可能会有重复的值（同一个生成树可以从不同的加边顺序得到），所以用 set。
神奇的代码
#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, m;
LL k;
cin >> n >> m >> k;
vector<vector<pair<int, LL>>> edge(n);
for (int i = 0; i < m; ++i) {
int u, v;
LL w;
cin >> u >> v >> w;
--u, --v;
edge[u].push_back({v, w});
edge[v].push_back({u, w});
}
int up = (1 << n);
int st = n - 1;
vector<set<LL>> candi(up);
candi[1].insert(0);
for (int i = 0; i < up; ++i) {
if (~i & 1)
continue;
for (int u = 0; u < n; ++u) {
if ((~i >> u) & 1)
continue;
for (auto& [v, w] : edge[u]) {
if ((i >> v) & 1)
continue;
for (auto& val : candi[i])
candi[i | (1 << v)].insert((val + w) % k);
}
}
}
cout << *ranges::min_element(candi.back()) << '\n';
return 0;
}
F - Good Set Query (abc328 F)
题目大意
给定数字\(n\)，依次给定\(q\)个条件 \((a_i,b_i,d_i)\)。
对于一个条件集合\(s\)，如果存在一个长度为\(n\)数组 \(x\)，对于这个集合里的所有条件，都满足\(x_{a_i} - x_{b_i} = d_i\)，那么这个集合是好的。
初始集合为空，依次对每个条件，如果加入到集合后，集合是好的，则加入到集合中。
问最后集合的元素。
解题思路
条件相当于是规定了数组\(x\)元素之间的差的关系。
对于一个条件\((a,b,d)\)，我们可以连一条 \(a\to b\)的边，边权为 \(d\)，反向边的边权为 \(-d\)。
考虑一个集合不是好时，此时形成的图是怎样的。
当加入一个条件\((a,b,d)\)，集合可能还是好的，但也可能变得不好，
如果还是好的，有两种情况：
- 一是\(a,b\)原先没有什么联系，即不连通，加了条边之后连通了，仅此而已。
- 二是\(a,b\)是连通的，加了 \(a\to b\)这条边后会形成一个环，环的边权和为 \(0\)，或者说 \(a\to b\)存在两条路径，其边权和相等。
在第二种情况下，这个条件就是多余的，我们可以不管这个条件，即不加这条边。此时图就没有环，即是一棵树（或森林）。
树是一个非常好的图，有着树上路径唯一的性质，因此情况二下， 我们可以很容易求出 \(a\to b\)的路径和，然后与 \(d\)比较，相等则说明加入这个条件后，集合还是好的。
而如果不相等，则说明不能加入这个条件，即有条件冲突了，说明 \(a\to b\)存在两条边权和不一样的路径。
所以问题就剩下，如何在动态加边的情况下，求出\(a\to b\)的长度。
如果是一棵静止的树，一个常用的方法就是预处理每个点到根节点的距离\(dis[i]\)，那么 \(a \to b\)距离就是 \(dis[a] - dis[b]\)，注意到反向边的边权是负值，所以\(lca\)到根的距离恰好抵销了。
而当两棵树合并时，有一棵树的 \(dis\)就要全部更新，为降低时间复杂度，可以采用启发式合并的策略，即节点树少的树合并到节点树多的树上，这样每次只用更新节点数少的树的 \(dis\)。更新就是从合并点开始\(DFS\)，更新\(dis\)数组。
为计算启发式合并的时间复杂度，可以考虑每个节点的\(dis\)的更新次数——每更新一次，其节点所在的连通块大小至少翻倍，那么每个节点最多更新 \(\log n\)次，其所在的连通块就包含了所有的节点，也就不会再更新了，因此启发式合并的复杂度是 \(O(n\log n)\)
用并查集维护连通性，然后树合并时采用启发式合并的策略更新\(dis\)数组 ，时间复杂度是 \(O(q + n\log n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> sz;
vector<LL> dis;
vector<vector<array<int, 2>>> edge;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
dis.resize(n);
edge.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
fill(dis.begin(), dis.end(), 0);
}
inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
inline void dfs(int u, int fa) {
for (auto& [v, w] : edge[u]) {
if (v == fa)
continue;
dis[v] = dis[u] - w;
dfs(v, u);
}
}
inline bool unite(int x, int y, int w) {
int fx = get(x);
int fy = get(y);
if (fx != fy) {
if (sz[fx] > sz[fy]) {
swap(x, y);
swap(fx, fy);
w = -w;
}
edge[x].push_back({y, w});
edge[y].push_back({x, -w});
dis[x] = dis[y] + w;
dfs(x, y);
p[fx] = fy;
sz[fy] += sz[fx];
return true;
} else {
return dis[x] == dis[y] + w;
}
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
dsu ji(n);
for (int i = 1; i <= q; ++i) {
int a, b, d;
cin >> a >> b >> d;
--a, --b;
if (ji.unite(a, b, d))
cout << i << ' ';
}
cout << '\n';
return 0;
}
G - Cut and Reorder (abc328 G)
题目大意
给定两个数组\(A,B\)，可以进行一下两种操作：
- 选择一个数\(x\)，将数组 \(A\)分成\(x+1\)个部分，然后重新排序，组成一个新数组。代价为\(xC\)
- 令\(A_i=A_i + k\)，代价为\(|k|\)
问最小的代价，使得\(A\)变成 \(B\)。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 328beginner atcoder contest 328 328 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315