AtCoder Beginner Contest 372

2024-09-21 22:23 由 ~Lanly~ 发表于 #其他

省流版

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;
}

G - Ax + By < C (abc372 G)

题目大意

给定三个$n$个数的数组$a,b,c$，问 $(x,y)$的数量，满足

$a_i x + b_i < c$，对任意 $i \in [1,n]$

多组数据。

解题思路

一眼只会$O(na_i)$。

神奇的代码