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

简单题：字符串加密

【模拟】【set】

“去重”一般使用STL的set比较方便，出现过了就插入集合。

然后按照题目要求模拟即可。

#include <iostream>
#include <set>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    string p = "";
    set<char> vis;
    for(char c: s) {
        if(vis.count(c)) continue;
        vis.insert(c);
        p += c;
    }
    for(char c='a'; c<='z'; c++) {
        if(!vis.count(c)) {
            p += c;
        }
    }
    for(char c: t) {
        cout << p[c-'a'];
    }
    return 0;
}

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

【链表】

链表模版题，其实虽然我个人写链表都是直接上来就写双向链表，因为双向的功能比单向要全面。

不过这道题的标题里就要求用“单向链表”，那就讲一下单向链表的做法。

首先观察到这道题插入数值的范围是1e4，那就不需要离散化了，直接开个1e4的数组就好。

然后因为考虑到题给的头结点h也是可能被删除的，所以为了方便起见，我手动引入了一个头结点，值为0（肯定不会和插入的节点重复）。最后按普遍习惯，把-1作尾结点。

然后其实就是比较基础的单向链表的模板，就不赘述了。不熟悉的小伙伴请自行去补充知识点。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e4+5;
int nxt[N];
int main() {
    int n;
    cin >> n;
    int h;
    cin >> h;
    nxt[0] = h;
    nxt[h] = -1;
    for(int i=1; i<n; i++) {
        int a, b;
        cin >> a >> b;
        nxt[a] = nxt[b];
        nxt[b] = a;
    }
    int k;
    cin >> k;
    for(int i=0; i!=-1; i=nxt[i]) {
        if(nxt[i] == k) {
            nxt[i] = nxt[k];
            break;
        }
    }
    for(int i=0; i!=-1; i=nxt[i]) {
        if(i != 0) cout << i << " ";
    }
    return 0;
}

困难题：走方格的方案数

【dp】【组合数学】

这道题一看数据范围只有8，有点离谱。

那应该瞎搞都能暴力做出来。不过这其实是比较典的题，也算是dp经典过河卒模型的基础版。

先来dp写一下吧，复杂度是O(N^2)。

状态转移为：一个点的方案始终等于到上一个点的可能方案之和。由于只能向下或者向右，所以一个点(i, j)的上一个点要么是(i-1, j)，(i, j-1)，所以dp[i][j] = dp[i][j-1] + dp[i-1][j];。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dp(n+5, vector<int>(m+5));
    for(int i=0; i<=n; i++) {
        dp[i][0] = 1;
    }
    for(int j=0; j<=m; j++) {
        dp[0][j] = 1;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            dp[i][j] = dp[i][j-1] + dp[i-1][j];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

不过这道题最优解是O(N)的做法，也是一个比较典的思想。

不难想到，从起点走到终点一定是n次向下+m次向右。

不妨将其转化为一个模型：n个0和m个1组成01序列有多少种组合方法。每种01序列其实就对应着唯一一条路径。

而对于“n个0和m个1组成01序列有多少种组合方法”的解其实就是C(n+m, n)或者C(n+m, m)。所以组合数公式套一下就行了。

fac[i]表示i的阶乘，因为i最大可能到16，所以要开long long。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> fac(n+m+1);
    fac[0] = 1;
    for(int i=1; i<=n+m; i++)
        fac[i] = fac[i-1] * i;
    // C(n+m, n)
    cout << fac[n+m]/(fac[n]*fac[m]) << endl;
    return 0;
}