官方题解｜巅峰赛#16

アイドル

2024-12-23 11:04:04

发布于：浙江

150阅读

0回复

0点赞

ACGO 巅峰赛#16 题解

写在前面

本场排位赛的所有题目的难度评级为：

题目编号	题目标题	难度
A.	美丽数	入门
B.	环形回文串	入门
C.	无重复字符的子串	普及-
D.	统计满足条件的子串个数	普及+/提高
E.	考拉兹猜想	普及+/提高
F.	帕罗蒂克	普及+/提高

非常感谢大家参加本场巅峰赛！

题解简述

以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。

A - 美丽数

模拟

我们可以使用一个数组 cnt 来统计 $N$ 中各个数字出现的次数。

然后枚举 $[1, 9]$ 中每个数字进行检查，若 $N$ 中存在数字 $i$ ，且 $cnt_i \ne i$ ，那么说明不是 美丽数，直接输出 No，并结束程序；否则循环结束后，没有退出程序，则输出 Yes。

#include <bits/stdc++.h>

int main() {
    int n; std::cin >> n;
    int cnt[10]{};
    while (n > 0) {
        cnt[n % 10] += 1;
        n /= 10;
    }
    for (int i = 1; i < 10; ++i)
        if (cnt[i] and cnt[i] != i) {
            std::cout << "No\n";
            return 0;
        }
    std::cout << "Yes\n";
    return 0;
}

B - 环形回文串

枚举

我们考虑将 $2$ 个原字符串 $S$ ，前后拼接起来构造为字符串 $S'$ 。

然后枚举下标 $i (1 \le i \le \vert S \vert)$ 。检查在字符串 $S'$ 中，以 $i$ 开头的长度为 $\vert S \vert$ 的子串是否为回文串即可。

#include <bits/stdc++.h>

bool check(const std::string &s) {
    int n = s.size();
    for (int i = 0; i < n / 2; ++i)
        if (s[i] != s[n - 1 - i]) return false;
    return true;
}

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size();
    s = s + s;
    for (int i = 0; i < n; ++i)
        if (check(s.substr(i, n))) {
            std::cout << "Yes\n";
            return 0;
        }
    std::cout << "No\n";
    return 0;
}

C - 无重复字符的子串

模拟；枚举

由于不含重复字符的字符串最长为 $26$ ，所以我们可以暴力枚举每个起点为 $i (1 \le i \le \vert S \vert)$ 的子串，并使用数组 cnt 来统计每一个字符出现的次数，若在向后遍历的过程中，发现某个字符已经出现过，则停止向后遍历。

#include <bits/stdc++.h>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::string s; std::cin >> s;
    int n = s.size(), res = 0;
    for (int i = 0; i < n; ++i) {
        int cnt[26]{};
        for (int j = i; j < n; ++j) {
            if (++cnt[s[j] - 'a'] > 1) break;
            res += 1;
        }
    }
    std::cout << res << '\n';
    return 0;
}

D - 统计满足条件的子串个数

数据结构（树状数组，线段树，平衡树）；

使用「树状数组」等数据结构，ft[i][j] 维护字符串 $S$ 中字符 $i$ 在前 $j$ 个字符中出现的次数。

使用树状数组，预处理 cnt[i][j] 数组，表示字符串 S 中，以 $i$ 开头，以 $j$ 结尾的子串的个数。

对于每次修改操作，我们考虑删除字符 $S_X$ 对以 $i$ 开头以 $S_X$ 结尾和以 $S_X$ 开头以 $i$ 结尾的子串数量，即 $cnt_{i, S_X}$ 和 $cnt_{S_X, i}$ 的影响。

那么我们直接枚举 $i$ ：

对于 $cnt_{i, S_X}$ ，查询前 $X - 1$ 个字符中，字符 $i$ 出现的次数，并将其从 $cnt_{i, S_X}$ 减去。
对于 $cnt_{S_X, i}$ ，查询第 $X$ 个及以后的字符中，字符 $i$ 出现的次数，并将其从 $cnt_{S_X, i}$ 减去。

同时修改树状数组。

然后将 $S_X$ 修改为字符 $C$ ，使用与计算删除的影响相同的做法，即可得到修改后对 cnt 数组的影响。

对于每个查询，我们可以以 $\mathrm{O}(1)$ 的时间从 cnt 数组中得到答案。

令 $N$ 为字符串 $S$ 的长度， $M$ 为字符集的大小，整个算法，预处理 cnt 数组的时间复杂度为 $\mathrm{O}(NM\log_2{N})$ 。处理每个查询的时间复杂度为 $\mathrm{O}(M\log_2{N})$ ，整个算法时间复杂度为 $\mathrm{O}((N + Q) \times (M\log_2{N})$ 。

#include <bits/stdc++.h>

using i64 = long long;

// class FenwickTree {...}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    std::string s; std::cin >> s;
    std::vector<FenwickTree<int>> ft(26, FenwickTree<int>(n));
    for (int i = 0; i < n; ++i)
        ft[s[i] - 'a'].add(i, 1);
    i64 cnt[26][26]{};
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 26; ++j)
            cnt[s[i] - 'a'][j] += ft[j].sum(i, n);
    while (q--) {
        int t; std::cin >> t;
        if (t == 1) {
            int x; std::cin >> x, --x;
            char c; std::cin >> c;
            for (int i = 0; i < 26; ++i) {
                cnt[i][s[x] - 'a'] -= ft[i].sum(0, x);
                cnt[s[x] - 'a'][i] -= ft[i].sum(x, n);
            }
            ft[s[x] - 'a'].add(x, -1);
            s[x] = c;
            ft[s[x] - 'a'].add(x, +1);
            for (int i = 0; i < 26; ++i) {
                cnt[i][s[x] - 'a'] += ft[i].sum(0, x);
                cnt[s[x] - 'a'][i] += ft[i].sum(x, n);
            }
        }
        else {
            char a, b;
            std::cin >> a >> b;
            std::cout << cnt[a - 'a'][b - 'a'] << '\n';
        }
    }
    return 0;
}

E - 考拉兹猜想

数据结构（平方分割，等）；

编写程序计算， $10^5$ 内变为 $1$ ，需要操作次数最多的数为 $77031$ ，经过 $350$ 次操作后变为 $1$ 。这意味着，数组中的每个元素最多经过 $350$ 次操作后，后续的操作对其失效。

我们考虑将数组分割为 $\sqrt{N}$ 个部分，对于每个块，我们维护一个容器，存储块内不为 $1$ 的元素的下标，另外维护一个变量维护块内为 $1$ 的元素数量。每次修改操作， $[L, R]$ ：

对于未整体出现在同一个块内的元素，暴力更新。
对于整体出现在同一个块内的元素，只修改块内不为 $1$ 的元素，同时将修改后所有的变为 $1$ 的元素下标，从块内容器中删除，同时令块内为 $1$ 的元素数量增加。

由于每个元素最多被修改 $350$ 次后，变为 $1$ ，上述操作，第一部分时间复杂度为 $\mathrm{O}(\sqrt{N})$ ，第二部分同样为 $\mathrm{O}(\sqrt{{N}})$ 。

对于每个查询 $[L, R]$ ，也分为两个部分：

对于未整体出现在同一个块内的元素，暴力统计。
对于整体出现在同一个块内的元素，查询块内维护的块内为 $1$ 的元素数量。

两部分操作时间复杂度皆为 $\mathrm{O}(N\sqrt{N})$ 。

#include <bits/stdc++.h>
 
using i64 = long long;
 
template<class T>
class SquareRoot {
private:
    int n, len, cnt;
    std::vector<T> v;
    std::vector<T> sum;
    std::vector<std::vector<int>> block;
    std::vector<int> id;
    std::vector<std::vector<int>> rid;
public:
    SquareRoot() : SquareRoot(0) {}
    explicit SquareRoot(int n) : SquareRoot(std::vector<int>(n)) {}
    explicit SquareRoot(const std::vector<T> &a) : n(a.size()), v(a) {
        len = std::sqrt(n);
        cnt = (n + len - 1) / len;
        sum = std::vector<T>(cnt);
        block = std::vector<std::vector<int>>(cnt);
        id = std::vector<int>(n);
        rid = std::vector<std::vector<int>>(cnt);
        for (int i = 0; i < n; ++i) {
            id[i] = i / len;
            rid[id[i]].push_back(i);
            if (v[i] > 1)
                block[id[i]].push_back(i);
            else
                sum[id[i]] += 1;
        }
    }
 
    bool singalUpdate(int i) {
        if (v[i] == 1) return true;
        if (v[i] & 1)
            v[i] = v[i] * 3 + 1;
        else
            v[i] /= 2;
        if (v[i] == 1) sum[id[i]] += 1;
        return v[i] == 1;
    }
 
    void blockUpdate(int i) {
        std::vector<int> st;
        for (auto &j : block[i])
            if (!singalUpdate(j))
                st.push_back(j);
        block[i] = std::move(st);
    }
 
    void apply(int l, int r) {
        if (l >= r) return;
        int sid = id[l], eid = id[r - 1];
        if (sid == eid) {
            for (int i = l; i < r; ++i)
                singalUpdate(i);
            return;
        }
        for (int i = l; id[i] == sid; ++i)
            singalUpdate(i);
        for (int i = sid + 1; i < eid; ++i)
            blockUpdate(i);
        for (int i = r - 1; id[i] == eid; --i)
            singalUpdate(i);
    }
 
    T prod(int l, int r) {
        if (l >= r) return 0;
        T sm = 0;
        int sid = id[l], eid = id[r - 1];
        if (sid == eid) {
            for (int i = l; i < r; ++i)
                sm += v[i] == 1;
            return sm;
        }
        for (int i = l; id[i] == sid; ++i)
            sm += v[i] == 1;
        for (int i = sid + 1; i < eid; ++i)
            sm += sum[i];
        for (int i = r - 1; id[i] == eid; --i)
            sm += v[i] == 1;
        return sm;
    }
};
 
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    SquareRoot<int> data(a);
    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        if (t == 1)
            data.apply(l, r + 1);
        else
            std::cout << data.prod(l, r + 1) << '\n';
    }
    return 0;
}

F - 帕罗蒂克

状态压缩动态规划

定义 $dp[i][mask][j]$ 为第 $i$ 位朋友，已经经过的站点集合为 $mask$ ，此时位于车站 $j$ 的可行性。

那么我们就可以对每一位朋友分开考虑，并使用状态压缩动态规划，在 $\mathrm{O}(KN^22^N)$ 的时间复杂度内，计算出上述 $DP$ 数组。

然后我们定义 $turn[step][i]$ 表示，经过 $step$ 次移动，位于车站 $i$ 的朋友的集合。根据已经得出的 $dp$ 数组，我们可以很容易计算出 $turn$ 数组。

最后根据 $turn[step][i]$ 中的存储的集合是否为所有朋友的全集，来判断，是否可以在站点 $i$ 汇合即可。

#include <bits/stdc++.h>

constexpr int N = 15;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> a(k);
    for (auto &x : a) std::cin >> x, --x;
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v, --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int dp[N][1 << N][N]{};
    for (int i = 0; i < k; ++i)
        dp[i][1 << a[i]][a[i]] = 1;
    for (int i = 0; i < k; ++i)
        for (unsigned mask = 0; mask < (1u << n); ++mask)
            for (int j = 0; j < n; ++j) if (dp[i][mask][j])
                for (auto &nj : g[j]) if (~mask >> nj & 1)
                    dp[i][mask | 1 << nj][nj] = 1;
    int turn[N + 1][N]{};
    for (int i = 0; i < k; ++i)
        for (unsigned mask = 0; mask < (1u << n); ++mask)
            for (int j = 0; j < n; ++j) if (dp[i][mask][j])
                turn[__builtin_popcount(mask)][j] |= 1 << i;
    for (int step = 0; step <= n; ++step)
        for (int i = 0; i < n; ++i)
            if (turn[step][i] == (1 << k) - 1) {
                std::cout << i + 1 << '\n';
                return 0;
            }
    std::cout << -1 << '\n';
    return 0;
}