Atcoder Beginner Contest 372 题解

竞赛结果：Contestant,3675th,-2。

A.Delete .

思路

遍历字符串，非’.’输出即可。

代码

void solve()
{
    string str;
    cin >> str;
    for (auto &ch : str)
        if (ch != '.')
            cout << ch;
}

B.3^A

思路

从高到低枚举 pow(3,i)是否小于等于 n，是则相减，易得构造出来的数列一定在 20 个以内。

代码

void solve()
{
    int m;
    cin >> m;
    vector<int> ans;
    while (m)
        for (int i = 10; i >= 0; i--)
            while (pow(3, i) <= m)
                m -= pow(3, i),ans.push_back(i);
    cout << ans.size() << endl;
    for (auto &v : ans)
        cout << v << " ";
}

C.Count ABC Again

思路

单个字符的修改最多会影响其字符-3 到字符+3 位置的 ABC 的数量，预处理后每次查询小规模暴力即可。

代码

void solve()
{
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;
    set<int> pos;
    for (int i = 0; i <= n - 3; i++)
        if (str[i] == 'A' && str[i + 1] == 'B' && str[i + 2] == 'C')
            pos.insert(i);
    while (q--)
    {
        int idx;
        char ch;
        cin >> idx >> ch;
        idx--;
        str[idx] = ch;
        for (int i = max(0, idx - 4); i <= min(n - 3, idx + 4); i++)
        {
            if (pos.find(i) != pos.end() && !(str[i] == 'A' && str[i + 1] == 'B' && str[i + 2] == 'C'))
                pos.erase(i);
            if (pos.find(i) == pos.end() && (str[i] == 'A' && str[i + 1] == 'B' && str[i + 2] == 'C'))
                pos.insert(i);
        }
        cout << pos.size() << endl;
    }
}

---

以下为补题部分。

D.Buildings

思路

$O(N^2)$ 的暴力好实现，主要是如何优化时间复杂度使得答案不会 TLE。

使用单调栈数据结构可以做到这点。

代码

void solve()
{
    int n;
    cin >> n;
    pair<int, int> hs;
    stack<pair<int, int>> st;
    st.push({INT_MAX, 0});
    vector<i64> ans(n + 1);
    for (int i = 1; i <= n; i++)
    {
        hs.second = i;
        cin >> hs.first;
        while (st.top().first <= hs.first)
            st.pop();
        ans[st.top().second]++;
        ans[hs.second]--;
        st.push(hs);
    }
    for (int i = 1; i <= n; i++)
    {
        ans[i] = ans[i - 1] + ans[i];
        cout << ans[i] << ' ';
    }
}

E.K-th Largest Connected Components

并查集维护每个节点的父节点，在父节点处维护前 10 大的子节点即可。

因为一开始没注意到 $k=10 $ 所以 TLE 了好几发。赛后才过的。

代码

struct dsu
{
    vector<size_t> pa, size;
    map<size_t, vector<size_t>> components;
    explicit dsu(size_t size_) : pa(size_), size(size_, 1)
    {
        iota(pa.begin(), pa.end(), 0);
        for (size_t i = 0; i < size_; ++i)
        {
            components[i] = {i};
        }
    }
    size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    void unite(size_t x, size_t y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return;
        if (size[x] < size[y])
            swap(x, y);
        pa[y] = x;
        size[x] += size[y];
        vector<int> n;
        sort(all(components[x]), greater<>());
        sort(all(components[y]), greater<>());
        for (int i = 0; i < min(10, (int)components[x].size()); i++)
            n.push_back(components[x][i]);
        for (int i = 0; i < min(10, (int)components[y].size()); i++)
            n.push_back(components[y][i]);
        sort(all(n), greater<>());
        components[x].clear();
        for (int i = 0; i < min((int)n.size(), 10); i++)
            components[x].push_back(n[i]);
        components.erase(y);
    }
    vector<size_t> connected(size_t x)
    {
        return components[find(x)];
    }
};

void solve()
{
    int n, q;
    cin >> n >> q;
    dsu d(n + 1);
    while (q--)
    {
        int op, a, b;
        cin >> op >> a >> b;
        if (op & 1)
            d.unite(a, b);
        else
        {
            vector res = d.connected(a);
            if (res.size() >= b)
                cout << res[b - 1] << endl;
            else
                cout << -1 << endl;
        }
    }
}