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

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

简单题 字符串加密

按题意模拟。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    bool vis[26] = {};
    vector<int> v;
    for (auto it : s) {
        if (!vis[it - 'a'])
            v.push_back(it - 'a');
        vis[it - 'a'] = 1;
    }
    for (int i = 0; i < 26; i++) {
        if (!vis[i])
            v.push_back(i);
        vis[i] = 1;
    }
    for (auto it : t) {
        cout << (char)(v[it - 'a'] + 'a');
    }
    return 0;
}

中等题 从单向链表中删除指定值的节点

观察到值域不大，可以用数组模拟链表。
表示 的节点的下一个节点。 可以设 号节点为头节点，遍历时从 号节点的下一个节点开始遍历。

#include <bits/stdc++.h>
using namespace std;
int nxt[10002];
int main() {
    int n;
    cin >> n;
    int head;
    cin >> head;
    nxt[0] = head;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        nxt[a] = nxt[b];
        nxt[b] = a;
    }
    int k;
    cin >> k;
    for (int i = 0; i <= 10000; i++) {
        if (nxt[i] == k) {
            nxt[i] = nxt[k];
        }
    }
    for (int i = nxt[0]; i != 0; i = nxt[i])
        cout << i << ' ';
    return 0;
}

困难题 走方格的方案数

动态规划。
设起点坐标 ， 表示走到坐标 的方案数。
当 或 时，只有 种方案，就是沿着坐标轴走。
否则即为走到上方格点的方案数加走到左方格点的方案数。
转移方程：

#include <bits/stdc++.h>
using namespace std;
int dp[9][9];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)dp[i][0] = 1;
    for (int i = 0; i <= m; i++)dp[0][i] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    cout << dp[n][m] << '\n';
    return 0;
}