A – Not Too Hard (abc328 A)
题目大意
给定(n)个数字和一个数 (x)。
问不大于 (x)的数的和。
解题思路
按找要求累计符合条件的数的和即可。
神奇的代码
#include
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 > a;
sum += a * (a B – 11/11 (abc328 B)
题目大意
给定一年的月数和一个月的天数。
问有多少对((i,j))，表示第 (i)个月的第 (j)日， (i,j)的数位上每个数字都是一样的。
解题思路
范围只有(O(100^2))，枚举所有的 ((i,j))逐个判断即可。
神奇的代码
#include
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 > x;
for (int j = 1; j 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
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 sum(n);
for (int i = 0; i > l >> r;
--l, --r;
int ans = 0;
if (r)
ans += sum[r - 1];
if (l)
ans -= sum[l - 1];
cout D – Take ABC (abc328 D)
题目大意
给定一个仅包含ABC的字符串(s)，每次将最左边的ABC删除，直至不能删。
问最后的字符串。
解题思路
可以从左到右依次将(s)的每个字符加入栈中，一旦栈顶构成ABC就弹栈。
模拟即可。
神奇的代码
#include
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 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
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>> edge(n);
for (int i = 0; i > u >> v >> w;
--u, --v;
edge[u].push_back({v, w});
edge[v].push_back({u, w});
}
int up = (1 > candi(up);
candi[1].insert(0);
for (int i = 0; i > u) & 1)
continue;
for (auto& [v, w] : edge[u]) {
if ((i >> v) & 1)
continue;
for (auto& val : candi[i])
candi[i | (1 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))，我们可以连一条 (ato b)的边，边权为 (d)，反向边的边权为 (-d)。
考虑一个集合不是好时，此时形成的图是怎样的。
当加入一个条件((a,b,d))，集合可能还是好的，但也可能变得不好，
如果还是好的，有两种情况：
- 一是(a,b)原先没有什么联系，即不连通，加了条边之后连通了，仅此而已。
- 二是(a,b)是连通的，加了 (ato b)这条边后会形成一个环，环的边权和为 (0)，或者说 (ato b)存在两条路径，其边权和相等。
在第二种情况下，这个条件就是多余的，我们可以不管这个条件，即不加这条边。此时图就没有环，即是一棵树（或森林）。
树是一个非常好的图，有着树上路径唯一的性质，因此情况二下， 我们可以很容易求出 (ato b)的路径和，然后与 (d)比较，相等则说明加入这个条件后，集合还是好的。
而如果不相等，则说明不能加入这个条件，即有条件冲突了，说明 (ato b)存在两条边权和不一样的路径。
所以问题就剩下，如何在动态加边的情况下，求出(ato b)的长度。
如果是一棵静止的树，一个常用的方法就是预处理每个点到根节点的距离(dis[i])，那么 (a to b)距离就是 (dis[a] – dis[b])，注意到反向边的边权是负值，所以(lca)到根的距离恰好抵销了。
而当两棵树合并时，有一棵树的 (dis)就要全部更新，为降低时间复杂度，可以采用启发式合并的策略，即节点树少的树合并到节点树多的树上，这样每次只用更新节点数少的树的 (dis)。更新就是从合并点开始(DFS)，更新(dis)数组。
为计算启发式合并的时间复杂度，可以考虑每个节点的(dis)的更新次数——每更新一次，其节点所在的连通块大小至少翻倍，那么每个节点最多更新 (log n)次，其所在的连通块就包含了所有的节点，也就不会再更新了，因此启发式合并的复杂度是 (O(nlog n))
用并查集维护连通性，然后树合并时采用启发式合并的策略更新(dis)数组 ，时间复杂度是 (O(q + nlog n))。
神奇的代码
#include
using namespace std;
using LL = long long;
class dsu {
public:
vector p;
vector sz;
vector dis;
vector>> 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 > a >> b >> d;
--a, --b;
if (ji.unite(a, b, d))
cout G – Cut and Reorder (abc328 G)
题目大意
给定两个数组(A,B)，可以进行一下两种操作：
- 选择一个数(x)，将数组 (A)分成(x+1)个部分，然后重新排序，组成一个新数组。代价为(xC)
- 令(A_i=A_i + k)，代价为(|k|)
问最小的代价，使得(A)变成 (B)。
解题思路
神奇的代码
机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
