美团算法笔试 2026.03.21

选择题8题 一共20分

编程题4题 一共80分

第一题给定一个数组，将这个数组复制1e9次得到一个超大的数组，问这个新数组的最长严格上升子序列的长度，很明显可以每次复制都只选一个元素，所以答案就是数组中有多少不同的数，直接sort后unique即可

第二题要用numpy、pandas、scikit-learn实现单层GRU前向传播，没时间做了

第三题给定一个数组，要求将数组切割成任意个子数组，使得每一个子数组中的众数*数组长度之和最小，这题直接dp即可，用unordered_map存cnt，dp[i]表示[1,i]的数组划分的最优解，枚举最后一个数组划分到哪，复杂度n方

第四题给了一棵树，树上每个节点有0或1两种值，每次做两种操作，要么将路径u->v上每个节点的值翻转，要么求从u->v按顺序记录下的01串转换成二进制 mod 1e9+7意义下的值，这题纯数据结构，树链剖分求LCA维护路径+线段树维护dfn序上的数值，注意u->v是先从u->lca向上走，然后是lca->v向下走，在dfn序上是从大到小和从小到大两种方向，需要小心维护两种方向的值。具体来说，dfn序上的线段树维护区间内从低到高和从高到低的二进制表示的数字，取反可以用num_inv=2^k-1--num这样来实现，懒标记只需要一个翻转标记即可，然后树剖后对于同一条链上dfn序连续的节点就能统一维护，最后计算答案比较麻烦，需要计算从u向上（与dfn序相反的方向），然后计算从lca向下到v（与dfn序相同方向），链内用线段树查值，拼接多条链的结果，复杂度mlog^2n

第一题代码

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end());
    cout << unique(a.begin(), a.end()) - a.begin() << "\n";
}

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

}

第三题代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) {
        cin >> x;
    }
    vector<ll> dp(n, INF);
    for (int i = 0; i < n; i++) {
        unordered_map<int, int> cnt;
        for (int j = i, maxv = 0; j >= 0; j--) {
            cnt[a[j]]++;
            if (cnt[a[j]] > cnt[maxv] || (cnt[a[j]] == cnt[maxv] && a[j] > maxv)) {
                maxv = a[j];
            }
            dp[i] = min(dp[i], (ll)(i - j + 1) * maxv + (j > 0 ? dp[j - 1] : 0));
        }
    }
    cout << dp.back() << "\n";
}

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

第四题代码

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

struct Node {
    int l, r;
    int rev;
    ll sum_lr, sum_rl;
    Node() = default;
    Node(int l, int r, int rev, ll val): l(l), r(r), rev(rev) {}
};
vector<Node> tree;
vector<int> a, sz, dep, top, dfn, id, fa, child;
vector<vector<int>> to;
vector<ll> pow2;
int tot;
void dfs1(int x) {
    sz[x] = 1;
    for (auto y : to[x]) {
        if (y == fa[x]) {
            continue;
        }
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y);
        if (sz[y] > sz[child[x]]) {
            child[x] = y;
        }
        sz[x] += sz[y];
    }
}

void dfs2(int x, int belong) {
    tot++;
    dfn[x] = tot;
    id[tot] = x;
    top[x] = belong;
    if (child[x] != 0) {
        dfs2(child[x], belong);
    }
    for (auto y : to[x]) {
        if (y == fa[x] || y == child[x]) {
            continue;
        }
        dfs2(y, y);
    }
}

void pushup(int x) {
    tree[x].sum_lr = (tree[x << 1].sum_lr * pow2[tree[x << 1 | 1].r - tree[x << 1 | 1].l + 1] % mod + tree[x << 1 | 1].sum_lr) % mod;
    tree[x].sum_rl = (tree[x << 1 | 1].sum_rl * pow2[tree[x << 1].r - tree[x << 1].l + 1] % mod + tree[x << 1].sum_rl) % mod;
}

void upd(int x, int rev) {
    if (rev == 1) {
        tree[x].sum_lr = (pow2[tree[x].r - tree[x].l + 1] - 1 - tree[x].sum_lr + mod) % mod;
        tree[x].sum_rl = (pow2[tree[x].r - tree[x].l + 1] - 1 - tree[x].sum_rl + mod) % mod;
        tree[x].rev ^= 1;
    }
}

void pushdown(int x) {
    if (tree[x].rev == 1) {
        upd(x << 1, tree[x].rev);
        upd(x << 1 | 1, tree[x].rev);
        tree[x].rev = 0;
    }
}

void build(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    tree[x].rev = 0;
    if (l == r) {
        tree[x].sum_lr = tree[x].sum_rl = a[id[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(x);
}

void update(int x, int l, int r) {
    if (tree[x].l == l && tree[x].r == r) {
        upd(x, 1);
        return;
    }
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) >> 1;
    if (r <= mid)update(x << 1, l, r);
    else if (l > mid)update(x << 1 | 1, l, r);
    else {
        update(x << 1, l, mid);
        update(x << 1 | 1, mid + 1, r);
    }
    pushup(x);
}

ll query(int x, int l, int r, int dir) {
    if (tree[x].l == l && tree[x].r == r) {
        return dir == 0 ? tree[x].sum_lr : tree[x].sum_rl;
    }
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) >> 1;
    if (r <= mid)return query(x << 1, l, r, dir);
    if (l > mid)return query(x << 1 | 1, l, r, dir);
    ll sumL = query(x << 1, l, mid, dir), sumR = query(x << 1 | 1, mid + 1, r, dir);
    if (dir == 0) {
        return (sumL * pow2[r - mid] % mod + sumR) % mod;
    }
    return (sumR * pow2[mid - l + 1] % mod + sumL) % mod;
}

int getLCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) {
        return x;
    }
    return y;
}

void update_path(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        update(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    update(1, dfn[x], dfn[y]);
}

ll calc_node(int x, int lca, int contain_lca, int dir) {
    ll ans = 0;
    int origin_x = x;
    // cerr << "calc " << x << " to " << lca << " with contain=" << contain_lca << " dir=" << dir << "\n";
    while (top[x] != top[lca]) {
        if (dir == 0) {
            assert(dep[origin_x] >= dep[x] && dep[origin_x] - dep[x] < pow2.size());
            ans = (query(1, dfn[top[x]], dfn[x], dir) * pow2[dep[origin_x] - dep[x]] % mod + ans) % mod;
        } else {
            assert(dep[x] + 1 >= dep[top[x]] && dep[x] - dep[top[x]] + 1 < pow2.size());
            ans = (ans * pow2[dep[x] - dep[top[x]] + 1] % mod + query(1, dfn[top[x]], dfn[x], dir)) % mod;
        }
        // cerr << "current=" << query(1, dfn[top[x]], dfn[x], dir) << "\n";
        // cerr << "ans=" << ans << "\n";
        x = fa[top[x]];
    }
    if (contain_lca) {
        // cerr << "current=" << query(1, dfn[lca], dfn[x], dir) << "\n";
        if (dir == 0) {
            assert(dep[origin_x] >= dep[x] && dep[origin_x] - dep[x] < pow2.size());
            ans = (query(1, dfn[lca], dfn[x], dir) * pow2[dep[origin_x] - dep[x]] % mod + ans) % mod;
        } else {
            assert(dep[x] + 1 >= dep[lca] && dep[x] - dep[lca] + 1 < pow2.size());
            ans = (ans * pow2[dep[x] - dep[lca] + 1] % mod + query(1, dfn[lca], dfn[x], dir)) % mod;
        }
    } else if (x != lca) {
        // cerr << "current=" << query(1, dfn[lca] + 1, dfn[x], dir) << "\n";
        if (dir == 0) {
            assert(dep[origin_x] >= dep[x] && dep[origin_x] - dep[x] < pow2.size());
            ans = (query(1, dfn[lca] + 1, dfn[x], dir) * pow2[dep[origin_x] - dep[x]] % mod + ans) % mod;
        } else {
            assert(dep[x] >= dep[lca] && dep[x] - dep[lca] < pow2.size());
            ans = (ans * pow2[dep[x] - dep[lca]] % mod + query(1, dfn[lca] + 1, dfn[x], dir)) % mod;
        }
    }
    // cerr << "ans=" << ans << "\n";
    return ans;
}

ll get_ans(int u, int v) {
    int lca = getLCA(u, v);
    ll sum_u = calc_node(u, lca, 1, 1);
    ll sum_v = calc_node(v, lca, 0, 0);
    // cerr << "for (u,v)=(" << u << "," << v << ") sum_u = " << sum_u << ", sum_v = " << sum_v << "\n";
    assert(dep[v] >= dep[lca] && dep[v] - dep[lca] < pow2.size());
    return (sum_u * pow2[dep[v] - dep[lca]] % mod + sum_v) % mod;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    tree.resize((n + 1) << 3);
    to.resize(n + 1);
    dfn.resize(n + 1, 0);
    sz.resize(n + 1, 0);
    id.resize(n + 1, 0);
    top.resize(n + 1, 0);
    dep.resize(n + 1, 0);
    fa.resize(n + 1, 0);
    child.resize(n + 1, 0);
    a.resize(n + 1, 0);
    pow2.resize(n + 2, 0);
    pow2[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n + 1; i++) {
        pow2[i] = pow2[i - 1] * 2 % mod;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        to[u].emplace_back(v);
        to[v].emplace_back(u);
    }
    dfs1(1);
    dfs2(1, 1);
    build(1, 1, n);
    while (m--) {
        int opt, u, v;
        cin >> opt >> u >> v;
        if (opt == 1) {
            update_path(u, v);
        } else {
            cout << get_ans(u, v) << '\n';
        }
    }
}