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 <= x);    }    cout << sum << '\n';    return 0;}


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 <= 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 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 << ans << '\n';    }    return 0;}


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 << 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 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>> 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 << n);    int st = n - 1;    vector<set> candi(up);    candi[1].insert(0);    for (int i = 0; i < up; ++i) {        if (~i & 1)            continue;        for (int u = 0; u > 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 using namespace std;using LL = long long;class dsu {  public:    vector p;    vector sz;    vector dis;    vector<vector<array>> 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 << 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\)

解题思路

神奇的代码