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

简单题：简单密码

简单模拟题，就不多讲了。

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

int main() {
    string s;
    cin >> s;
    map<char, int> mp;
    mp['a'] = mp['b'] = mp['c'] = 2;
    mp['d'] = mp['e'] = mp['f'] = 3;
    mp['g'] = mp['h'] = mp['i'] = 4;
    mp['j'] = mp['k'] = mp['l'] = 5;
    mp['m'] = mp['n'] = mp['o'] = 6;
    mp['p'] = mp['q'] = mp['r'] = mp['s'] = 7;
    mp['t'] = mp['u'] = mp['v'] = 8;
    mp['w'] = mp['x'] = mp['y'] = mp['z'] = 9;
    for(auto c: s) {
        if(c >= 'a' && c <= 'z') cout << mp[c];
        else if(c >= 'A' && c <= 'Y') cout << (char)(c + 33);
        else if(c == 'Z') cout <<'a';
        else cout << c;
    }
    return 0;
}

中等题：蛇形矩阵

对于每一条斜线上的每个点，有一个特性就是横纵坐标之和为定值。

考虑这个特性去安排遍历的顺序，问题就迎刃而解了。

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> mp(n+1, vector<int>(n+1));
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=i; j++) {
            mp[i+1-j][j] = ++cnt;
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n-i+1; j++)
            cout << mp[i][j] << " ";
        cout << endl;
    }
    return 0;
}

困难题：火车进站

首先对于一个长度为n的序列，它可能得出栈情况其实就是固定的，和每个位置上的值是没有关系的。

也就是说，我们只需要去找出1, 2, 3, ..., n-1, n的入栈顺序对应哪些出栈顺序，再把123456...映射到这些位置上的值就好了。

最后在对这些序列按照字典序排个序问题就解决了。

然后，观察到n的最大范围是10。10！并不会超出时限，那么枚举一下全排列，对每个排列判断一下合法性就好了。

那么如何判断一个出站顺序是否合法呢？最简单的做法就是实际真的拿一个栈（入栈顺序为123456......）来模拟一遍就好了。以下check函数就是这个作用。

    auto check = [&](vector<int> &v) {
        vector<int> stk;
        int cnt = 0;
        stk.push_back(++cnt);
        for(int i=1; i<=n; i++) {
            while(stk.back() < v[i]) stk.push_back(++cnt);
            if(stk.back() == v[i]) stk.pop_back();
            else return false;
        }
        return true;
    };

有了上面这个check函数，接下来就只剩枚举全排列了。

比较方便的是可以直接用C++的库函数next_permutation来实现。

下面是完整的AC代码。

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1), v(n+1);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        v[i] = i;
    }
    vector<vector<int>> res;
    auto check = [&](vector<int> &v) {
        vector<int> stk;
        int cnt = 0;
        stk.push_back(++cnt);
        for(int i=1; i<=n; i++) {
            while(stk.back() < v[i]) stk.push_back(++cnt);
            if(stk.back() == v[i]) stk.pop_back();
            else return false;
        }
        return true;
    };
    do {
        if(check(v)) res.push_back(v);
    } while(next_permutation(v.begin()+1, v.end()));
    for(auto &d: res) {
        for(int i=1; i<=n; i++)
            d[i] = a[d[i]];
    }
    sort(res.begin(), res.end());
    for(auto &d: res) {
        for(int i=1; i<=n; i++)
            cout << d[i] << " ";
        cout << endl;
    }
    return 0;
}