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

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

简单题 小红的多彩糖葫芦

使用 数组记录字符是否出现过，如果出现过就输出当前走过的字符串的长度。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    bool vis[26] = {};
    int ans = 0;
    for (char c : s) {
        if (!vis[c - 'a']) {
            ans++;
            vis[c - 'a'] = true;
        } else break;
    }
    cout << ans << '\n';
    return 0;
}

中等题 小红的好数

可以用 层循环解决，不过很麻烦，直接用dfs。
dfs 前 位时，给当前位数设置成 至 再 dfs 下一位。
前 位枚举完后，检查这 位中有没有重复数字，可以给这 位数字排序后去重后检查去重后是否还为 个数字。
如果没有重复数字就加入答案。
最后给答案数组降序排序，并输出其中的第 个数。
注意输出需要前导 ，可以使用 setfill()和 setw() 或直接 printf("%05d")。

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> ans;
    auto dfs = [&](auto&& self, int d, vector<int> num)->void {
        if (d == 5) {
            auto num2 = num;
            sort(num2.begin(), num2.end());
            if (unique(num2.begin(), num2.end()) == num2.end()) {
                int x = 0;
                for (int i = 4; i >= 0; i--) {
                    x *= 10;
                    x += num[i];
                }
                ans.push_back(x);
            }
            return;
        } else {
            for (int i = 0; i <= 9; i++) {
                num[d] = i;
                self(self, d + 1, num);
            }
        }
    };
    dfs(dfs, 0, vector<int>(5));
    sort(ans.begin(), ans.end(), greater<>());
    int k;
    cin >> k;
    cout << setfill('0') << setw(5) << ans[k - 1] << '\n';
    // printf("%05d\n", ans[k - 1]);
    return 0;
}

困难题 滑雪

设 为滑到 的最长路径，其初值为 。
先单独看 ：
如果有 与 邻接，且 ，则有状态转移：。
因为最长的路径可能为 ，可以遍历整个二维数组 次，每一次都做如上的转移，可以获得答案。
但是时间复杂度太高了，考虑优化。
因为高度高的点不可能由高度低的点转移而来，换句话说，从高往低遍历，每个点只需要转移一次状态。
所以可以使用大小为 的数组存放 ，按 从大到小排序，然后遍历其中的 ：
如果其附近一邻接点 满足 ，则 。
答案是 的最大值。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[102][102];
int b[102][102];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r, c;
    cin >> r >> c;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            b[i][j] = 1;
    vector<pair<int, int>> v(r * c);
    int tot = 0;
    for (int x = 1; x <= r; x++)
        for (int y = 1; y <= c; y++, tot++)
            v[tot] = {x, y};
    sort(v.begin(), v.end(), [&](auto & x, auto & y) {
        return a[x.first][x.second] > a[y.first][y.second];
    });
    for (int i = 0; i < r * c; i++) {
        int x = v[i].first;
        int y = v[i].second;
        if (a[x][y - 1] > a[x][y])b[x][y] = max(b[x][y], b[x][y - 1] + 1);
        if (a[x][y + 1] > a[x][y])b[x][y] = max(b[x][y], b[x][y + 1] + 1);
        if (a[x - 1][y] > a[x][y])b[x][y] = max(b[x][y], b[x - 1][y] + 1);
        if (a[x + 1][y] > a[x][y])b[x][y] = max(b[x][y], b[x + 1][y] + 1);
    }
    int ans = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            ans = max(ans, b[i][j]);
    cout << ans;
    return 0;
}