牛客周赛 Round 141 题解

由于牛客的渲染问题，你可以点此链接进入我的博客查看

A 回文(version 1）

知识点：字符串，回文，读题

则称 为一个双回文数。

先判断是不是平方数：用整型存储 ，检查 是否成立。

然后检查 是否等于 ， 是否等于 即可，这步可以用 函数简单地实现。

时间复杂度 ，即数字位数。

void solve() {
    int x;
    cin >> x;
    int t = sqrt(x);
    auto check = [&](int x) {
        string s1 = to_string(x), s2 = s1;
        reverse(all(s2));
        return s1 == s2;
    };
    if (t * t == x && check(t) && check(x))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B 未知(version 1)

知识点：异或，构造

发现在 时，有当 时， ， 。

时间复杂度 

void solve() {
    int x, y;
    cin >> x >> y;
    cout << y << endl;
}

C 回文(version 2)

知识点：贪心

不妨把 看成 ，把 看成 ，那么最终的串，本质上就是把原来对应的权值串分隔成若干段，每段都是 或 ，所以我们直接贪心匹配，能配 就配 ，配不了就配 ，否则就失败。

关于贪心的证明：

如果当前两端都能组成 ，那说明这两端至少都“有余量”可以往里多吃一个字符。这时如果存在某个可行方案是先配 ，那么把两端各多吃掉一个 ，改成先配 ​ ，中间剩下的子问题仍然是同构的。

时间复杂度 

void solve() {
    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;
    while (l <= r) {
        bool f1 = s[l] == 'm' || l + 1 <= r && s[l] == 'n' && s[l + 1] == 'n', f2 = s[r] == 'm' || l <= r - 1 && s[r] == 'n' && s[r - 1] == 'n';
        if (f1 && f2)
            l += (s[l] == 'm' ? 1 : 2), r -= (s[r] == 'm' ? 1 : 2);
        else if (s[l] == 'n' && s[r] == 'n')
            ++l, --r;
        else {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

D 未知(version 2)

知识点：枚举，压缩解集

如果数组中存在两个 ，我们令 ， 即可。

如果数组中存在数字出现过两次，且数组中存在 ，我们令 ， ， 即可。

否则我们检查数组中所有小于 的数字 ，查看所有指数 ， 是否 和 均存在。

时间复杂度 

void solve() {
    int n;
    cin >> n;
    vector<int> a;
    unordered_map<int, int> mp;
    for (int i = 0, x; i < n; ++i) {
        cin >> x, mp[x]++;
        if (x <= 31622 && x != 1) a.pb(x);
    }
    if (mp[1] >= 2) {
        cout << "YES" << endl;
        return;
    }
    for (auto [u, v] : mp) {
        if (v >= 2 && mp[1]) {
            cout << "YES" << endl;
            return;
        }
    }
    for (auto v : a) {
        int x = v * v;
        for (int i = 2; x <= 1e9; ++i, x *= v) {
            if (mp[i] && mp[x]) {
                _(i, x);
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

E 未知(version 3)

知识点：树，构造，贪心

每个深度都要一个叶子和一个往下的内部点，最少的节点数是 ，最多的则是将每个深度的叶子都拆成互不共享路径，最多需要 个点。

我们构造每一层的节点数 ：

  • 对 ，设当前还要给 层分配 个节点；
  • 第 层最多不能超过 ，否则下一层接不上；
  • 同时还要给更浅的 层至少留下 个点。

所以可以取：

这样就能把总节点数正好分完。

最后连一下边，上下层的点一一对应，多余的点全部连到上一层的第一个节点即可。

时间复杂度 

void solve() {
    int n, m;
    cin >> n >> m;

    if (!(2 * m <= n && n <= 1 + m * (m + 1) / 2)) {
        cout << "NO" << endl;
        return;
    }

    vector<int> cnt(m + 1);
    cnt[m] = 1;

    int rest = n - 2;
    for (int d = m - 1; d >= 1; --d) {
        int x = min(cnt[d + 1] + 1, rest - 2LL * (d - 1));
        cnt[d] = x;
        rest -= x;
    }

    vector<PII> edges;

    int id = 2;
    vector<int> pa = {1};

    for (int d = 1; d <= m; ++d) {
        vector<int> cur(cnt[d]);
        for (int i = 0; i < cnt[d]; ++i) cur[i] = id++;

        int p = (int)pa.size();

        for (int i = 0; i < p; ++i) edges.pb({pa[i], cur[i]});

        for (int i = p; i < cnt[d]; ++i) edges.pb({pa[0], cur[i]});

        if (d < m) pa.assign(cur.begin(), cur.end() - 1);
    }

    cout << "YES" << endl;
    for (auto [u, v] : edges) cout << u << " " << v << endl;
}

F 回文(version 3)

知识点：计数，子序列，特殊构造

注意到 ，合法的回文子序列一定为以下形式：

  • ：单一字符，个数为 。
  • ：两个相同字符，区间内任选两个即可，个数为 。
  • ：形如 。假设我们在询问区间 内固定了外侧字母是 。对于区间内的任意一个位置 作为中间字母，它能组成的数量为 。记前 个字符中 出现了 次，令 ，得到：

展开得

所以我们维护 的前缀和 的前缀和即可。

时间复杂度 

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;

    vector<array<int, 26>> cnt(n + 1, array<int, 26>{}), sum(n + 1, array<int, 26>{}), pref(n + 1, array<int, 26>{});

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 26; ++j) {
            cnt[i][j] = cnt[i - 1][j] + (s[i - 1] - 'a' == j);
            sum[i][j] = sum[i - 1][j] + cnt[i][j];
            pref[i][j] = pref[i - 1][j] + 1LL * cnt[i - 1][j] * cnt[i][j];
        }
    }

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;

        if (x == 1) {
            cout << r - l + 1 << endl;
        } else if (x == 2) {
            int ans = 0;
            for (int c = 0; c < 26; ++c) {
                int k = cnt[r][c] - cnt[l - 1][c];
                ans += k * (k - 1) / 2;
            }
            cout << ans << endl;
        } else if (x == 3) {
            int ans = 0;
            for (int c = 0; c < 26; ++c) {
                int A = cnt[l - 1][c], B = cnt[r][c], len = r - l + 1;
                ans += B * (sum[r - 1][c] - ((l >= 2) ? sum[l - 2][c] : 0)) - (pref[r][c] - pref[l - 1][c]) - A * B * len + A * (sum[r][c] - sum[l - 1][c]);
            }
            cout << ans << endl;
        }
    }
}