ABC372(A-F)

A - delete .¶

题目大意

给你一个字符串 \(S\)，删除其所有的 .

参考代码

C++

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main()
{

    string s;
    cin >> s;
    s.erase(remove(s.begin(), s.end(), '.'), s.end());
    cout << s << endl;
    return 0;
}

B - 3^A ¶

题目大意

给你一个正整数 \(M(1 \le M \le 10 ^5)\)，找到一个正整数 \(N\) 和一组序列 \(A = (A_1, A_2, \cdots, A_N)\) 满足下列所有条件：

\(1 \le N \le 20\)
\(0 \le A_i \le 10(1 \le i \le N)\)
\(\sum\limits_{i = 1}^N3^{A_i} = M\)

输出任意一组解即可。

解题思路

可以枚举，也可以从最低位开始消除。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int m;
    cin >> m;
    vector<int> a;
    int p = 1, i = 0;
    while(3 * p < m)
    {
        p *= 3;
        i++;
    }
    while(m)
    {
        if(m >= p)
        {
            a.push_back(i);
            m -= p;
            continue;
        }
        p /= 3;
        i--;
    }
    cout << a.size() << endl;
    for(auto x : a)
        cout << x << ' ';
    return 0;
}

C - Count ABC Again ¶

题目大意

给你一个长度为 \(N(3 \le N \le 2 \times 10^5)\) 字符串 \(S\)，同时给你 \(Q(1 \le Q \le 2 \times 10^5)\) 个询问，每个询问包括一个整数 \(X_i\) 和一个字符 \(C_i\)，你需要将 \(S_{X_i}\) 替换成字符 \(C_i\)，然后回答出 \(S\) 有多少个 ABC 子串。

解题思路

读入字符串 \(S\) 马少处理出当前有多少个 ABC 子串，记为 ans

替换前需要判断 s.substr(x-2, 3)，s.substr(x-1, 3)，s.substr(x, 3) 是不是 ABC，如果是则 ans--。

替换前需要判断 s.substr(x-2, 3)，s.substr(x-1, 3)，s.substr(x, 3) 是不是 ABC，如果是则 ans++。

参考代码

C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int now = 0;
    for (int i = 0; i < n; i++)
        if (s.substr(i, 3) == "ABC")
            now++;
    while (q--)
    {
        int x;
        char c;
        cin >> x >> c;
        x--;
        if (s[x] == c)
        {
            cout << now << endl;
            continue;
        }
        if (x - 2 >= 0 && s.substr(x - 2, 3) == "ABC")
            now--;
        if (x - 1 >= 0 && s.substr(x - 1, 3) == "ABC")
            now--;
        if (s.substr(x, 3) == "ABC")
            now--;
        s[x] = c;
        if (x - 2 >= 0 && s.substr(x - 2, 3) == "ABC")
            now++;
        if (x - 1 >= 0 && s.substr(x - 1, 3) == "ABC")
            now++;
        if (s.substr(x, 3) == "ABC")
            now++;
        cout << now << endl;
    }
    return 0;
}

D - Buildings ¶

题目大意

有 \(N(1 \le N \le 2 \times 10^5)\) 个建筑，第 \(i\) 个建筑的高度是 \(H_i\)，对于每一个 \(i = 1, 2, \cdots, N\)，找到满足下列条件的 \(j(i < j \le N)\) 的个数：

在第 \(i\) 个建筑和第 \(j\) 个建筑中间不存在另一个建筑比第 \(j\) 个建筑高。

解题思路

对于一组满足条件的 \((i, j)\)，有 \(\max\{H_{i+1}, H_{i+2}, \cdots, H_{j-1}\} \le H_j\)。

如果固定 \(i\)，求出有多少个 \(j\) 满足条件是困难的，但如果固定 \(j\)，只需要知道 \(j\) 左边第一个比 \(H_j\) 大的位置，设这个位置为 \(t\)，则 \(j\) 可以给 \(t\) 到 \(j-1\) 的所有位置贡献 \(1\)。所以弄一个从左到右单调递增的单调栈，用差分数组维护每个 \(j\) 的贡献即可。

参考代码

C++

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> h(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    h[0] = n + 1;
    stack<int> st;
    st.push(0);
    for (int i = 1; i <= n; i++)
    {
        while (h[st.top()] < h[i])
            st.pop();
        int l = st.top();
        b[l]++;
        b[i]--;
        st.push(i);
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
        cout << b[i] << ' ';
    }
    return 0;
}

E - K-th Largest Connected Components ¶

题目大意

给你一个 \(N(1 \le N \le 2 \times 10^5)\) 个点的无向图，初始的时候没有任何边。给你 \(Q(1 \le Q \le 2 \times 10^5)\) 个询问，询问有两种类型：

类型 1：1 u v ，表示在点 \(u\) 和点 \(v\) 之间添加一条无向边。
类型 2：2 v k ，表示询问和点 \(v\) 连通的所有点中第 \(k(1 \le k \le 10)\) 大的点编号。如果和点 \(v\) 连通的点的数量小于 \(k\) 个，输出 -1。注：节点自身与自身连通。

解题思路

连通分量可以用并查集维护，注意到 \(k \le 10\)，每个连通分量再附加维护一个有序的 vector，至多存储 \(10\) 个节点的编号。合并的时候执行归并排序的流程，因此合并的时间复杂度 \(O(k)\)，查询复杂度 \(O(1)\)。

如果 \(k\) 比较大的话，可以参照官方题解优化。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

const int MAXK = 10;

struct DSU
{
    vector<int> parent_or_size;
    vector<vector<int>> top_k;

    DSU(int n) : parent_or_size(n, -1), top_k(n)
    {
        top_k.reserve(n);
        for (int i = 0; i < n; i++)
            top_k[i].push_back(i);
    }

    int leader(int u) { return parent_or_size[u] < 0 ? u : parent_or_size[u] = leader(parent_or_size[u]); }

    void merge(int u, int v)
    {
        u = leader(u);
        v = leader(v);
        if (u == v)
            return;
        if (-parent_or_size[u] > -parent_or_size[v])
            swap(u, v);
        const vector<int> &tu = top_k[u];
        const vector<int> &tv = top_k[v];
        int us = tu.size(), i = 0;
        int vs = tv.size(), j = 0;
        int len = min(MAXK, us + vs), k = 0;
        vector<int> t(len);
        while (i < us && j < vs && k < len)
            t[k++] = tu[i] > tv[j] ? tu[i++] : tv[j++];
        while (i < us && k < len)
            t[k++] = tu[i++];
        while (j < vs && k < len)
            t[k++] = tv[j++];
        parent_or_size[v] += parent_or_size[u];
        parent_or_size[u] = v;
        top_k[v] = t;
    }

    int kth(int u, int k)
    {
        u = leader(u);
        if (-parent_or_size[u] < k)
            return -1;
        return top_k[u][k - 1];
    }
};

int main()
{
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            dsu.merge(u, v);
        }
        else
        {
            int u, k;
            cin >> u >> k;
            u--;
            cout << dsu.kth(u, k) + 1 << endl;
        }
    }
    return 0;
}

F - Teleporting Takahashi 2 ¶

题目大意

给你一个 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个点，\(N+M\) 条边的有向图，图中有两类边：

第一类边：\(1 \rightarrow 2, 2 \rightarrow 3, \cdots, N-1 \rightarrow N, N \rightarrow 1\)，这种边一共有 \(N\) 条。
第二类边：输入 \(M\) 对整数 \((X_i, Y_i)\)，表示存在一条 \(X_i \rightarrow Y_i\) 的边。这种边一共有 \(M(1 \le M \le 50)\) 条。

问：从点 \(1\) 出发，有多少条长度为 \(K\) 的路径？答案对 \(998244353\) 取模。

解题思路

考虑到 \(M \le 50\)，所以第二种类型的边是非常少的，图中大多数的点 \(i\) 只有 \(i \rightarrow i+1\) 一条边，一旦访问到对于这样类型的点，只能一路 \(i \rightarrow i+1 \rightarrow i+2 \rightarrow \cdots\)，所以考虑对图中的点进行缩点处理，把相邻的出度和入度为 \(1\) 的点缩成一个，缩点的同时记录下每个点的集合大小。显然锁完点之后图中最多有 \(4 \times M\) 个点，然后考虑 \(dp\)，定义 \(dp[i][j]\) 表示走到点 \(i\) 的长度为 \(j\) 的路径数量，按照定义后向的传播即可。

实现的时候要注意点 \(1\) 不能被缩，其次就是特殊处理最终结果停留在某条链的中间的情况。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> x(m), y(m);
    vector<bool> deg(n + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> x[i] >> y[i];
        deg[x[i]] = deg[y[i]] = true;
    }
    int idx = 0;
    vector<int> p(n + 1), cnt(n + 1, 1);
    p[1] = ++idx;
    for (int u = 2; u <= n;)
    {
        p[u] = ++idx;
        if (!deg[u])
        {
            int v = u + 1;
            while (v <= n && !deg[v])
            {
                p[v++] = p[u];
                cnt[p[u]]++;
            }
            u = v;
        }
        else
            u++;
    }
    vector<vector<int>> edge(idx + 1);
    for (int i = 0; i < m; i++)
    {
        int u = p[x[i]], v = p[y[i]];
        edge[u].push_back(v);
    }
    for (int u = 1; u < idx; u++)
        edge[u].push_back(u + 1);
    edge[idx].push_back(1);
    vector<vector<int>> dp(k + 1, vector<int>(idx + 1));
    dp[0][1] = 1;
    for (int i = 0; i < k; i++)
        for (int u = 1; u <= idx; u++)
        {
            if (dp[i][u] == 0)
                continue;
            for (auto v : edge[u])
            {
                int j = min(k, i + cnt[v]);
                dp[j][v] = (dp[j][v] + dp[i][u]) % MOD;
            }
        }
    int ans = 0;
    for (int u = 1; u <= idx; u++)
        ans = (ans + dp[k][u]) % MOD;
    cout << ans << endl;
    return 0;
}

最后更新: 2024-12-19
创建日期: 2024-12-08

ABC372(A-F)

A - delete .¶

B - 3^A¶

C - Count ABC Again¶

D - Buildings¶

E - K-th Largest Connected Components¶

F - Teleporting Takahashi 2¶

B - 3^A ¶

C - Count ABC Again ¶

D - Buildings ¶

E - K-th Largest Connected Components ¶

F - Teleporting Takahashi 2 ¶