【ZCX-008-DIV2】智程星周赛 008 基础组题解

A. 九宫格映射

思路

按照题意读入每个字符串 $S_i$ ，只需要看它的首字母，然后求出对应的 $C_i$ 并拼接起来。

可以用一个字符串保存 a 到 z 对应的数字：

string StoC = "22233344455566677778889999";

这样字符 c 对应的数字就是 StoC[c - 'a']。逐个读入字符串，把 StoC[s[0] - 'a'] 加到答案末尾即可。

复杂度

时间复杂度 $O(N)$ ，空间复杂度 $O(1)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string StoC = "22233344455566677778889999";

    int n;
    cin >> n;

    string ans = "";
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        ans += StoC[s[0] - 'a']; // 用首字母下标找到对应数字。
    }

    cout << ans << '\n';
    return 0;
}

B. Drop Blocks

思路

直接模拟每个格子的方块数 $A_i$ ，但不要真的执行“所有格子都减一”。

设 mn 表示当前所有格子中的最小方块数。原题中一次整体删除，等价于在不删除的做法里把查询门槛加上 mn：

原题要问真实高度至少为 $y$ 的格子数；
不删除时，等价于问原始高度至少为 $y+mn$ 的格子数。

再设 c[j] 表示当前有多少个格子的原始高度至少为 $j$ 。每次执行 1 x 时， $A_x$ 加一，那么这个格子会新满足“至少为 $A_x$ ”，所以令 c[A[x]]++。

如果某次 c[A[x]] == n，说明所有格子高度都至少达到 A[x]，也就是最小高度变成了 A[x]，更新 mn = A[x]。

查询 2 y 时，答案就是 c[y + mn]。如果 y + mn > q，高度不可能达到，输出 0。

复杂度

每个操作只做常数次数组访问，时间复杂度 $O(N+Q)$ ，空间复杂度 $O(N+Q)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXQ = 300000 + 5;

int a[MAXQ], c[MAXQ];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    int mn = 0; // 当前所有格子的最小原始高度。

    for (int i = 1; i <= q; i++) {
        int op, x;
        cin >> op >> x;

        if (op == 1) {
            a[x]++;
            c[a[x]]++; // 多了一个高度至少为 a[x] 的格子。

            if (c[a[x]] == n) {
                mn = a[x];
            }
        } else {
            int need = x + mn;

            if (need > q) {
                cout << 0 << '\n';
            } else {
                cout << c[need] << '\n';
            }
        }
    }

    return 0;
}

C. 零食售卖

思路

题目要求相邻两个售卖点之间的最大距离，但输入的坐标不一定有序。

先把所有坐标从小到大排序，再枚举相邻两个坐标，取差值最大值即可。

复杂度

排序时间复杂度 $O(k \log k)$ ，空间复杂度 $O(k)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k;
    cin >> k;

    vector<int> a(k);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int ans = 0;
    for (int i = 1; i < k; i++) {
        ans = max(ans, a[i] - a[i - 1]);
    }

    cout << ans << '\n';
    return 0;
}

D. 字符串

思路

要让重排后任意相邻字符都不同，关键在出现次数最多的字符。

如果某个字符出现次数超过：

\frac{|S|+1}{2}

那么无论怎样安排，它都一定会有两个相同字符相邻，输出 No。

否则一定可以构造。用优先队列维护每种字符的剩余次数，每次取出当前剩余次数最多的字符。

如果它和上一个放入的字符不同，就直接放入；如果相同，就临时取第二多的字符放入，再把第一个字符放回队列。

复杂度

设字符串长度为 $L$ 。每个字符进出优先队列常数次，时间复杂度 $O(L \log 26)$ ，空间复杂度 $O(L)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int cnt[26];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        string s;
        cin >> s;

        int n = s.size();
        for (int i = 0; i < 26; i++) {
            cnt[i] = 0;
        }

        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
        }

        int mx = 0;
        for (int i = 0; i < 26; i++) {
            mx = max(mx, cnt[i]);
        }

        if (mx > (n + 1) / 2) {
            cout << "No\n";
            continue;
        }

        priority_queue<pair<int, char> > pq;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                pq.push(make_pair(cnt[i], char('a' + i)));
            }
        }

        string ans = "";

        while (!pq.empty()) {
            pair<int, char> first = pq.top();
            pq.pop();

            if (ans.empty() || ans.back() != first.second) {
                ans += first.second;
                first.first--;
                if (first.first > 0) {
                    pq.push(first);
                }
            } else {
                pair<int, char> second = pq.top();
                pq.pop();

                ans += second.second;
                second.first--;

                if (second.first > 0) {
                    pq.push(second);
                }
                pq.push(first);
            }
        }

        cout << "Yes\n" << ans << '\n';
    }

    return 0;
}

目前还没有评论...