9646516T4是近期做过的最难的笔试压轴题。1.给球员得分记录找mvp，按照题意模拟即可，弄个map存下分数#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 0x3F3F3F3F;const int maxn = 2e5 + 555;const int MOD = 1e9 + 7;int32_t main() {    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cout.precision(10);    cout << fixed;    int n;    cin >> n;    string ta, tb;    cin >> ta >> tb;    map<string, int> tm;    map<string, map<string, int>> pm;    int mvp_val = -1e9;    string mvp;    for (int i = 0; i < n; i++) {        string player, team;        int val;        cin >> player >> team >> val;        tm[team] += val;        pm[team][player] += val;        if (pm[team][player] > mvp_val) {            mvp_val = pm[team][player];            mvp = player;        }    }    if (tm[ta] == tm[tb]) {        cout << "ended in a draw" << endl;    } else if (tm[ta] > tm[tb]) {        cout << ta << endl;    } else {        cout << tb << endl;    }    cout << mvp << endl;    return 0;}2.给出隐身逻辑，有草丛隐身和buff隐身两种，判断A是否能看到B。先处理下每个人物i是否在草丛j中，查询的时候先看b是否开了buff，然后看ab是否是一伙的，之后再看b是否在草丛中，如果在再看ab在不在一个草丛中。我用了bitset优化，暴力应该也可以。注意B不在草丛的情况，没注意的话会卡56%#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 0x3F3F3F3F;const int maxn = 2e5 + 555;const int MOD = 1e9 + 7;struct user {    double x, y;    int buff, cls;    bitset<200> st;};vector<user> V;bool inside_circle(double cx, double cy, double cr, double x, double y) {    double ox = x - cx;    double oy = y - cy;    double d = ox * ox + oy * oy;    return d <= cr * cr;}bool inside_rect(double A, double B, double C) { return A <= B && B <= C; }int32_t main() {    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cout.precision(10);    cout << fixed;    int n, m, q;    cin >> n >> m >> q;    for (int i = 0; i < n; i++) {        user s;        cin >> s.x >> s.y >> s.buff >> s.cls;        V.push_back(s);    }    for (int i = 0; i < m; i++) {        int t;        cin >> t;        if (t == 0) {            double cx, cy, cr;            cin >> cx >> cy >> cr;            for (auto &u : V) {                u.st[i] = inside_circle(cx, cy, cr, u.x, u.y);            }        } else {            set<double> sx, sy;            for (int j = 0; j < 4; j++) {                double x, y;                cin >> x >> y;                sx.insert(x);                sy.insert(y);            }            assert(sx.size() == 2);            assert(sy.size() == 2);            for (auto &u : V) {                u.st[i] = inside_rect(*sx.begin(), u.x, *next(sx.begin())) &&                          inside_rect(*sy.begin(), u.y, *next(sy.begin()));            }        }    }    while (q--) {        int a, b;        cin >> a >> b;        a--;        b--;        if (V[b].buff) {            cout << 0 << endl;        } else if (V[a].cls != V[b].cls) {            if (!V[b].st.count()) {                cout << 1 << endl;            } else {                if (((V[a].st & V[b].st).count())) {                    cout << 1 << endl;                } else {                    cout << 0 << endl;                }            }        } else {            cout << 1 << endl;        }    }    return 0;}3.给一堆物品，每个物品有两个值a和b，求最多取出k个物品的条件下，取出a总和为y的物品，最小的b总和是多少。a和y有正有负，k<=5。这题数据水了，暴力DP 100ms轻松过，正解可能需要折半搜索优化下。#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 0x3F3F3F3F;const int maxn = 2e5 + 555;const int MOD = 1e9 + 7;const char *FAIL_FLAG = "Cannot Make It!";int32_t main() {    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cout.precision(10);    cout << fixed;    int n, k, x, y;    cin >> n >> k >> x >> y;    if (x == 1)        y = -y;    vector<pair<int, int>> V;    for (int i = 0; i < n; i++) {        int v, a, b;        cin >> v >> a >> b;        if (a == 1)            b = -b;        V.push_back({b, v});    }    vector<unordered_map<int, int>> F(6);    F[0][0] = 0;    for (auto [a2, b2] : V) {        for (int i = k; i >= 0; i--) {            for (auto [a, b] : F[i - 1]) {                if (!F[i].count(a2 + a)) {                    F[i][a2 + a] = b + b2;                } else {                    F[i][a2 + a] = min(b + b2, F[i][a2 + a]);                }            }        }    }    ll ans = 1e18;    for (int i = 0; i <= k; i++) {        if (F[i].count(y)) {            ans = min(ans, 1LL * F[i][y]);        }    }    if (ans < 1e18) {        cout << ans << endl;    } else {        cout << FAIL_FLAG << endl;    }    return 0;}4.给一个字符串矩阵(n*m~1e5)，每次移动可以上下左右走，也可以瞬移到相同字符处，代价都是1,给出1e5个询问，求两点最短路。这题出的真心不错，一眼就能看到思路，但是需要处理很多细节。首先先加26个辅助点，代表a-z，每个辅助点连向对应字符位置，由于辅助点要一来一回，为了方便起见，将辅助点边权设为1，普通边边权为2，求出答案后除以2.从a到b要么不使用传送，那么答案是曼哈顿距离，要么至少使用一次瞬移。此时A到B的答案为A->中间点X->辅助点->B。此时可以枚举辅助点的类型，这样辅助点->B这段距离可以预处理出来。中间点X->辅助点代价是1。A->中间点X代价是A到最近的这个类型的点的距离，这可以bfs预处理出来。#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 0x3F3F3F3F;const int maxn = 2e5 + 555;const int MOD = 1e9 + 7;const int dx[] = {1, -1, 0, 0};const int dy[] = {0, 0, 1, -1};#define IDX(x, y) (((x) * (m)) + (y))void dijk(int s, vector<int> &D, const vector<vector<pair<int, int>>> &G) {    set<pair<int, int>> st;    st.insert({0, s});    D[s] = 0;    while (!st.empty()) {        auto [dis, pos] = *st.begin();        st.erase(st.begin());        if (D[pos] < dis) {            continue;        }        for (auto [to, cost] : G[pos]) {            if (D[to] > cost + dis) {                D[to] = cost + dis;                st.insert({D[to], to});            }        }    }}vector<int> chr[26];int n, m;void bfs(int ch, vector<int> &dis, const vector<vector<pair<int, int>>> &G) {    queue<pair<int, int>> q;    for (int i : chr[ch]) {        q.push({0, i});        dis[i] = 0;    }    while (!q.empty()) {        auto [d, idx] = q.front();        int x = idx / m;        int y = idx - x * m;        q.pop();        for (int k = 0; k < 4; k++) {            int x2 = x + dx[k];            int y2 = y + dy[k];            if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m) {                if (dis[IDX(x2, y2)] > d + 1) {                    dis[IDX(x2, y2)] = d + 1;                    q.push({d + 1, IDX(x2, y2)});                }            }        }    }}int32_t main() {    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cout.precision(10);    cout << fixed;    cin >> n >> m;    vector<string> V(n);    for (int i = 0; i < n; i++) {        cin >> V[i];    }    vector<vector<pair<int, int>>> G(n * m + 100);    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            chr[V[i][j] - 'a'].push_back(IDX(i, j));            for (int k = 0; k < 4; k++) {                int x = i + dx[k];                int y = j + dy[k];                if (x >= 0 && x < n && y >= 0 && y < m) {                    G[IDX(i, j)].push_back({IDX(x, y), 2});                }            }            G[IDX(i, j)].push_back({n * m + V[i][j] - 'a', 1});            G[n * m + V[i][j] - 'a'].push_back({IDX(i, j), 1});        }    }    vector<vector<int>> dis(26, vector<int>(n * m + 30, INF));    for (int i = 0; i < 26; i++) {        dijk(n * m + i, dis[i], G);    }    vector<vector<int>> dis2(26, vector<int>(n * m + 30, INF));    for (int i = 0; i < 26; i++) {        bfs(i, dis2[i], G);    }    int q;    cin >> q;    while (q--) {        int x0, x1, y0, y1;        cin >> x0 >> y0 >> x1 >> y1;        x0--;        x1--;        y0--;        y1--;        int ch = V[x1][y1] - 'a';        ll ans = abs(x0 - x1) + abs(y0 - y1);        for (int i = 0; i < 26; i++) {            ll step1 = dis2[i][IDX(x1, y1)] * 2;            ll step2 = 1;            ll step3 = dis[i][IDX(x0, y0)];            ll now = step1 + step2 + step3;            ans = min(ans, now / 2);        }        cout << ans << endl;    }    return 0;}