活動地址： 牛客春招刷題訓練營 - 編程打卡活動

簡單題 小美的排列詢問

利用 存儲 在數(shù)組中的下標，即判斷 是否為 。

#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，這里用數(shù)組也一樣，將字符集中的元素映射到該字符集中的下一個元素，如果是最后一個元素則映射到第一個元素。
對原字符串進行映射后即為答案。

#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 數(shù)字計數(shù)

數(shù)位dp寫不出來，寫了個dfs。
記 的答案為 ，那答案就是 。
求 的過程如下：
dfs中參數(shù)： 表示第 位(從 下標開始)， 表示是否頂著上界， 表示當前數(shù)字，為方便將數(shù)字統(tǒng)一轉成 位并從 開始dfs。

1. 如果 ，則 位及之后的不能任意取，枚舉 從 到 ，如果 就 繼續(xù) dfs，否則 繼續(xù) dfs。
2. 如果 且第 位之前都不是 ，第 位及之后的數(shù)位可以任意取 到 ，共有 個數(shù)字，第 位之前的數(shù)位，除了前導零，計數(shù)都加上 ；第 位之后有 個數(shù)位，給 每個計數(shù)加上 。
3. 如果 且第 位之前都是 ，枚舉 從 到 ，設 繼續(xù)dfs。

時間復雜度 ， 表示字符串位數(shù)。

#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;
}