3.16深信服笔试

C++开发，14 道填空题，填空题有逻辑题，智力题，4 道编程题，编程题均满分。

填空题有一个是给一个数组，让你数一下有几个逆序对，还有一个是和哈希表相关的题。

C卷。回忆版，只回忆了大致，无题面和样例。

第一题，字符串的题，满分代码

这个题感觉有点奇怪

class Solution {
public:
    string get_subst(string st) {
        string ans;
        for (int i = 0; i < (int) st.size(); i++) {
            if (ans.size() > 1 && st[i] == ans.back() && st[i] == ans[(int) ans.size() - 2]) {
                ans.pop_back();
                ans.pop_back();
            } else {
                ans += st[i];
            }
        }
        return ans;
    }
};

第二题，选相差小于 x 的，满分代码

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    i64 x;
    cin >> n >> x;
    vector<pair<i64, i64>> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());

    i64 res = v[0].second, ans = res;
    for (int i = 1; i < n; i++) {
        if (v[i].first - v[i - 1].first > x) {
            res = v[i].second;
        } else {
            res += v[i].second;
        }
        ans = max(ans, res);
    }
    cout << ans << '\n';

    return 0;
}

第三题，LRU 的题，满分代码

#include "bits/stdc++.h"

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, l;
    cin >> n >> l;
    unordered_map<int, list<pair<int, int>>::iterator> mp;
    list<pair<int, int>> lst;

    while (l--) {
        char o;
        cin >> o;
        if (o == 's') {
            int x, v;
            cin >> x >> v;
            
            if (mp.count(x)) {
                auto it = mp[x];
                lst.splice(lst.begin(), lst, it);
                it->second = v;
            } else {
                if (lst.size() == n) {
                    mp.erase(lst.back().first);
                    lst.pop_back();
                }
                lst.push_front({x, v});
                mp[x] = lst.begin();
            }
        } else {
            int x;
            cin >> x;

            if (mp.count(x)) {
                auto it = mp[x];
                lst.splice(lst.begin(), lst, it);
                cout << it->second << '\n';
            } else {
                cout << "-1\n";
            }
        }
    }

    return 0;
}

第四题，一些数被打乱要求还原的题，满分代码

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), c(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        c[b[i]] = i;
    }
    int j = 0;
    for (int i = 1; i <= n; i++) {
        if (c[i] == -1) {
            j = i;
            break;
        }
    }
    vector<int> ans;
    while (j) {
        ans.push_back(a[j]);
        j = b[j];
    }
    for (int i = (int) ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}