8.7 网易互娱-后台开发工程师-笔试参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    int n = 18;
    vector<int> W{7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
    string M = "10X98765432";
    auto check = [&](string s) -> bool {
        int sum = 0;
        for (int i = 0; i < n - 1; ++i) {
            sum += W[i] * (s[i] - '0');
        }
        return M[sum % 11] == s[n - 1];
    };

    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int ans = 0;
        function<void(int)> Dfs = [&](int k) {
            if (k == n - 1) {
                if (check(s)) {
                    ans += 1;
                }
                return ;
            }
            if (s[k] != '*') {
                Dfs(k + 1);
            } else {
                for (int i = 0; i < 10; ++i) {
                    s[k] = i + '0';
                    Dfs(k + 1);
                }
                s[k] = '*';
            }
        };
        Dfs(0);
        cout << ans << '\n';
    }
    return 0;
}

/*
2
34088119480815*663
520123200501169**4

1
9
*/

第二题《比赛排名》：拓扑排序

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int N, M, C;
    cin >> N >> M;
    vector<unordered_set<int>> children(N + 1), parent(N + 1);
    while (M--) {
        cin >> C;
        int pre = -1, x;
        while (C--) {
            cin >> x;
            if (pre != -1) {
                children[pre].emplace(x);
                parent[x].emplace(pre);
            }
            pre = x;
        }
    }
    vector<int> indeg(N + 1);
    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        indeg[i] = parent[i].size();
        if (indeg[i] == 0) {
            q.emplace(i);
        }
    }
    vector<int> ans;
    while (!q.empty()) {
        if (q.size() != 1) {
            break;
        }
        int u = q.front();
        ans.emplace_back(u);
        q.pop();
        while (!children[u].empty()) {
            int v = *children[u].begin();
            if (--indeg[v] == 0) {
                q.emplace(v);
            }
            children[u].erase(v);
        }
    }
    if (ans.size() != N) {
        cout << "NO\n";
    } else {
        for (int i = 0; i < N; ++i) {
            cout << ans[i] << " \n"[i == N - 1];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

/*
4
3 2
2 1 3
2 1 2
4 3
3 1 2 3
2 1 3
2 1 4
4 1
4 1 2 3 4
4 3
3 1 2 4
3 1 3 4
2 3 2

NO
NO
1 2 3 4
1 3 2 4
*/

第三题《永远的七日之都》：优先队列（本题只是作为参考，因为笔试时忘了优先队列自定义函数怎么写了）

#include <bits/stdc++.h>
using namespace std;
#define MOD 1'000'000'007
void solve() {
    int N, K, p, w;
    cin >> N >> K;
    auto lt_cmp = [&](auto &lhs, auto &rhs) {
        auto [l_base, l_inc, l_p] = lhs;
        auto [r_base, r_inc, r_p] = rhs;
        return 1.0 * (l_base + l_inc) / l_base < 1.0 * (r_base + r_inc) / r_base;
    };
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(lt_cmp)> q(lt_cmp);
    long long ans = 1;
    while (N--) {
        cin >> p >> w;
        int base = p * w + 100 - p;
        if (p != 100) {
            q.emplace(base, w - 1, p);
        } else {
            ans = (ans * base) % MOD;
        }
    }
    while (K--) {
        if (q.empty()) {
            break;
        }
        auto [base, inc, p] = q.top();
        q.pop();
        if (p + 1 == 100) {
            ans = (ans * (base + inc)) % MOD;
        } else {
            q.emplace(base + inc, inc, p + 1);
        }
    }
    while (!q.empty()) {
        auto [base, inc, p] = q.top();
        q.pop();
        ans = (ans * base) % MOD;
    }
    cout << ans << '\n';
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

/*
3
3 2
0 2
0 3
0 4
3 2
0 4
0 4
1 4
5 6
0 4
0 4
0 4
0 4
0 4

1060000
1092727
930393309
*/