牛客春招刷题训练营-2025.5.7题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小美的排列询问

利用 存储 在数组中的下标，即判断 是否为 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), pos(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    int x, y;
    cin >> x >> y;
    if (abs(pos[x] - pos[y]) == 1) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

中等题 小红的字符串构造

如果字符集大小为 ，则无解。
否则，建一个map，这里用数组也一样，将字符集中的元素映射到该字符集中的下一个元素，如果是最后一个元素则映射到第一个元素。
对原字符串进行映射后即为答案。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    set<char> st;
    for (auto it : s)st.insert(it);
    vector<char> a;
    for (auto it : st)a.push_back(it);
    int n = a.size();
    if (n == 1) {
        cout << -1;
        return 0;
    }
    vector<char> b(n);
    for (int i = 0; i < n; i++) {
        b[(i + 1) % n] = a[i];
    }
    vector<char> mp(256);
    for (int i = 0; i < n; i++) {
        mp[a[i]] = b[i];
    }
    for (auto& it : s)it = mp[it];
    cout << s;
    return 0;
}

困难题 [ZJOI2010]COUNT 数字计数

数位dp写不出来，写了个dfs。
记 的答案为 ，那答案就是 。
求 的过程如下：
dfs中参数： 表示第 位(从 下标开始)， 表示是否顶着上界， 表示当前数字，为方便将数字统一转成 位并从 开始dfs。

1. 如果 ，则 位及之后的不能任意取，枚举 从 到 ，如果 就 继续 dfs，否则 继续 dfs。
2. 如果 且第 位之前都不是 ，第 位及之后的数位可以任意取 到 ，共有 个数字，第 位之前的数位，除了前导零，计数都加上 ；第 位之后有 个数位，给 每个计数加上 。
3. 如果 且第 位之前都是 ，枚举 从 到 ，设 继续dfs。

时间复杂度 ， 表示字符串位数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    vector<ll> power_10(19);
    power_10[0] = 1;
    for (int i = 1; i <= 18; i++)
        power_10[i] = power_10[i - 1] * 10;
    long long l, r;
    cin >> l >> r;
    l--;
    vector<ll> ans1(10), ans2(10);
    vector<int> al(13), ar(13), tmp(13);
    for (int i = 12; i >= 0; i--) {
        al[i] = l % 10;
        l /= 10;
        ar[i] = r % 10;
        r /= 10;
    }
    auto dfs = [&](auto&& self, int d, bool b, vector<int>& tmp, vector<ll>& ans, vector<int>& num)->void {
        if (b && d <= 12) {
            for (int i = 0; i <= 9; i++) {
                tmp[d] = i;
                if (tmp[d] < num[d])
                    self(self, d + 1, false, tmp, ans, num);
                else if (tmp[d] == num[d])
                    self(self, d + 1, true, tmp, ans, num);
                else break;
            }
        } else {
            if (count(tmp.begin(), tmp.begin() + d, 0) == d) {
                if (d == 13)ans[0]++;
                else {
                    for (int i = 0; i <= 9; i++) {
                        tmp[d] = i;
                        self(self, d + 1, false, tmp, ans, num);
                        tmp[d] = 0;
                    }
                }
            } else {
                bool flag = false;
                for (int i = 0; i < d; i++) {
                    if (tmp[i] != 0)flag = true;
                    if (flag)ans[tmp[i]] += power_10[13 - d];
                }
                for (int i = 0; i <= 9; i++)
                    if (d <= 12)
                        ans[i] += (13 - d) * power_10[12 - d];
            }
        }
    };
    fill(tmp.begin(), tmp.end(), 0);
    dfs(dfs, 0, true, tmp, ans1, ar);
    fill(tmp.begin(), tmp.end(), 0);
    dfs(dfs, 0, true, tmp, ans2, al);
    for (int i = 0; i <= 9; i++)
        cout << ans1[i] - ans2[i] << ' ';
    return 0;
}