2022.3.2日网易互娱笔试题解

第一题

题一视频：https://www.bilibili.com/video/BV1Qu411D7UH?spm_id_from=333.999.0.0

#include <bits/stdc++.h>
using namespace std;

int xs[] = {0, 7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
string rs = "10X98765432";
char id[20];
vector<int> idx;
int ans;

int check() {
    int r = 0;
    for (int i = 1; i <= 17; i++)
        r = (r + (id[i] - '0') * xs[i]) % 11;
    return rs[r] == id[18];
}

void dfs(int x, int n) {
    if (x == n) {
        ans += check();
        return;
    }
    for (int i = 0; i <= 9; i++) {
        id[idx[x]] = i + '0';
        dfs(x + 1, n);
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> (id + 1); idx.clear();
        for (int i = 1; i <= 18; i++) // 找到 * 所在的位置集合 
            if (id[i] == '*')
                idx.push_back(i);
        ans = 0;
        dfs(0, idx.size());
        cout << ans << endl;
    }
}

第二题

题二视频：https://www.bilibili.com/video/BV1PL4y137Cx?spm_id_from=333.999.0.0

#include <bits/stdc++.h>
using namespace std; 
#define fi first
#define se second
const int N = 1e5 + 5;

typedef long long LL;

vector<pair<int, int>> edge[N];

int n; LL t[N];

void init() {
    for (int i = 1; i <= n; i++) {
        t[i] = 0;
        edge[i].clear();
    }
}

void solve() {
    scanf("%d", &n); init();
    queue<int> que;
    for (int i = 1; i <= n; i++) {
        int D, K;
        scanf("%d %d", &D, &K);
        if (!K) // 将入度为 0 的点加入到队列中，并更新任务的完成时间 
            que.push(i), t[i] = D;
        while (K--) {
            int x; scanf("%d", &x);
            edge[x].push_back({i, D});
        }
    }
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (auto nxt : edge[u]) {
            int v = nxt.fi, w = nxt.se;
            t[v] = max(t[v], t[u] + w); // 更新 v 的最晚完成时间 
            if (-- rd[v] == 0) {
                que.push(v);
            }
        }
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, t[i]);
    cout << ans << endl;
}

int main() {
    int T; cin >> T; while (T--) solve();
}

第三题

题三视频：https://www.bilibili.com/video/BV1nL4y1375F?spm_id_from=333.999.0.0

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 10005;

int n, m, p;
int dis[N][2];
vector<int> eb[N], el[N];

void init() {
    for (int i = 1 ; i <= n ; i ++) {
        eb[i].clear(), el[i].clear();
    }
}

int BFS() {
    queue<pair<int, int>> que; que.push({1, 0});
    memset(dis, 0x3f, sizeof(dis));
    dis[1][0] = 0;
    while (!que.empty()) {
        auto u = que.front(); que.pop();
        for (int v : eb[u.fi]) {
            if (dis[v][0] > dis[u.fi][u.se] + 1) que.push({v, 0});
            dis[v][0] = dis[u.fi][u.se] + 1;
        }
        for (int v : el[u.fi]) {
            if (dis[v][1] > dis[u.fi][u.se] + u.se) que.push({v, 1});
            dis[v][1] = dis[u.fi][u.se] + u.se;
        }
    }
    return min(dis[n][0], dis[n][1]);
}

void solve() {
    scanf("%d %d %d", &n, &m, &p); init();
    for (int i = 0, u, v ; i < m ; i ++) {
        scanf("%d %d", &u, &v);
        eb[u].push_back(v), eb[v].push_back(u);
    }
    for (int i = 0, u, v ; i < p ; i ++) {
        scanf("%d %d", &u, &v);
        el[u].push_back(v), el[v].push_back(u);
    }
    cout << BFS() << endl;
}

int main() {
    int T; cin >> T; while (T --) solve();
    return 0;
}

#春招上岸经验##笔试题目##笔经##校招##网易#