✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

美团-2026.03.21-研发岗

这套 3.21 美团研发岗三题梯度很清楚。第一题是典型结论题，关键在于把“超长重复数组上的 LIS”看成“不同值最多能取几种”；第二题看起来像交换模拟，真正要抓的是每个 '(' 需要跨过多少个失衡右括号；第三题是整套分水岭，需要把树上路径方向和区间二进制值一起维护，树链剖分加双向信息线段树才是正解。

01. 小基的档案拼接升序册

问题描述

小基 手里有一份长度为 的档案编号序列 。

为了观察长序列下的变化，他把这份序列原封不动地复制到末尾，一共额外拼接了 次。拼接完成后的新序列记为 ，长度为 。并且对于任意满足 的位置，都有：

现在需要你计算：在新序列 中，最长严格递增子序列的长度是多少。

这里的严格递增子序列指：从原序列中按相对顺序选出若干个元素，且后一个元素一定严格大于前一个元素。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个整数 ，表示原数组长度。
• 第二行输入 个整数 ，表示原数组元素。

输出格式

对于每组测试数据，输出一行一个整数，表示新数组 的最长严格递增子序列长度。

样例输入

2
4
1 1 2 3
5
4 5 3 3 4

样例输出

3
3

样例说明

第一组数据中，可以取出的最长严格递增子序列为 ，因此答案为 。

数据范围

• 
• 
• 
• 单个测试文件内所有 的总和不超过

题解

这题表面上像要在一个超长序列上做 LIS，但真正关键点只有一个：拼接次数极大，远远大于数组里不同数值的个数。

设原数组中一共出现了 个不同的值。

由于子序列要求严格递增，所以同一个值最多只能选一次。因此答案一定不会超过不同值个数 。

接下来说明这个上界一定能取到。

把原数组里所有不同的值从小到大排序，设为：

因为新数组是把原数组重复了很多次，而 ，所以完全可以这样选：

• 在第 份数组中选一个值为 的位置；
• 在第 份数组中选一个值为 的位置；
• ...
• 在第 份数组中选一个值为 的位置。

这些位置一定严格递增，值也严格递增，所以长度为 的严格递增子序列一定存在。

因此答案就是：

做法就非常直接了：每组数据用集合去重，输出集合大小即可。

时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()


def solve() -> None:
    t = int(input())
    out = []
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))

        # 严格递增子序列中，同一个值最多只能出现一次。
        # 由于复制次数极多，可以把所有不同值按升序分别放到不同副本中去选。
        out.append(str(len(set(arr))))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        unordered_set<int> st;
        st.reserve(n * 2);

        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            // 记录原数组里出现过多少种不同的值。
            st.insert(x);
        }

        // 答案就是不同元素个数。
        cout << st.size() << '\n';
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int t = fs.nextInt();
        while (t-- > 0) {
            int n = fs.nextInt();
            HashSet<Integer> set = new HashSet<>(n * 2);

            for (int i = 0; i < n; ++i) {
                // 统计不同元素个数即可。
                set.add(fs.nextInt());
            }

            out.append(set.size()).append('\n');
        }

        System.out.print(out);
    }
}

02. 小兰的括号整理术

问题描述

小兰拿到了一段长度为偶数的括号串 ，其中只包含 '(' 和 ')'。

如果一个括号串满足下面的定义，就称它是一个平衡括号序列：

1. 空串是平衡的。
2. 若字符串 是平衡的，那么 "(A)" 也是平衡的。
3. 若字符串 和 都是平衡的，那么 "AB" 也是平衡的。

现在 小兰 只能执行下面这种操作：

• 选择一个位置 ，交换相邻的两个字符 与 。

请你计算，至少要做多少次这样的相邻交换，才能把整个括号串变成一个平衡括号序列。

保证每组数据都一定可以通过若干次相邻交换变成平衡括号序列。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个偶数 ，表示括号串长度。
• 第二行输入一个长度为 的字符串 ，其中只包含 '(' 与 ')'。

输出格式

对于每组测试数据，输出一行一个整数，表示最少相邻交换次数。

样例输入

3
2
)(
4
()()
4
))((

样例输出

1
0
3

数据范围

• 
• 
• 一定为偶数
• 所有测试数据中 的总和不超过

题解

要让一个括号串变成平衡序列，最重要的条件是：任意前缀中，左括号数量都不能少于右括号数量。

从左到右扫描，用 bal 表示当前前缀里：

扫描时分两种情况：

• 遇到 ')'，说明前缀里右括号多了一个，直接令 bal -= 1。
• 遇到 '('，先看当前 bal 是否已经小于 。

如果此时 bal < 0，表示在这个 '(' 前面已经有 -bal 个“多出来的右括号”。为了让最终前缀合法，这个 '(' 一定要越过这 -bal 个右括号，交换次数也就恰好增加 -bal。

随后再把这个 '(' 放进前缀里，也就是令 bal += 1。

为什么这样算一定最优？

• 当前这个 '(' 必须跨过前面所有多出来的右括号，否则这些失衡前缀永远修不好。
• 它跨过的数量正好就是 -bal，这是无论如何都省不掉的交换次数。
• 每个 '(' 只在自己真正需要补前缀失衡时贡献交换，不会重复计算。

例如 "))(("：

• 前两个 ')' 扫完后，bal = -2。
• 遇到第三个字符 '(' 时，它必须跨过前面两个多余的 ')'，贡献 次交换。
• 再遇到第四个 '(' 时，还需要跨过 个多余的 ')'，再贡献 次。

总答案就是 。

时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()


def solve() -> None:
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        s = input()

        ans = 0
        bal = 0

        for ch in s:
            if ch == ')':
                bal -= 1
            else:
                # 这个左括号必须跨过前面所有多出来的右括号。
                if bal < 0:
                    ans += -bal
                bal += 1

        out.append(str(ans))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        long long ans = 0;
        int bal = 0;

        for (char ch : s) {
            if (ch == ')') {
                --bal;
            } else {
                // 当前左括号必须跨过前面所有多出来的右括号。
                if (bal < 0) {
                    ans += -bal;
                }
                ++bal;
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }

        String next() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            StringBuilder sb = new StringBuilder();
            while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int t = fs.nextInt();
        while (t-- > 0) {
            int n = fs.nextInt();
            String s = fs.next();

            long ans = 0;
            int bal = 0;

            for (int i = 0; i < n; ++i) {
                if (s.charAt(i) == ')') {
                    bal--;
                } else {
                    // 这个左括号必须跨过前面所有多出来的右括号。
                    if (bal < 0) {
                        ans += -bal;
                    }
                    bal++;
                }
            }

            out.append(ans).append('\n');
        }

        System.out.print(out);
    }
}

03. 小毛的树径翻转密码

问题描述

小毛 有一棵节点编号为 的树，每个节点上只会写着 或 。

对于任意一条从节点 到节点 的简单路径 ，把这条路径上经过的所有节点值按顺序拼成一个二进制串。记这个二进制串对应的十进制数对 取模后的结果为 。

例如，如果路径上的节点值依次是 01101，那么它对应的十进制数就是 ，因此：

现在 小毛 会进行 次操作：

• 操作 1 u v：把简单路径 上所有节点的值全部反置。
• 操作 2 u v：询问当前的 。

其中反置的含义是：

• 0 变成 1
• 1 变成 0

请你回答所有操作 2。

输入格式

第一行输入两个整数 ，表示树的节点数和操作数。

第二行输入 个整数 ，表示每个节点的初始值，其中 。

接下来 行，每行输入两个整数 ，表示树中的一条无向边。

接下来 行，每行输入三个整数 ：

• 若 ，表示把路径 上所有节点值反置。
• 若 ，表示询问 。

输出格式

对于每个操作 2，输出一行一个整数，表示对应路径的二进制值对 取模的结果。

样例输入

5 5
0 0 0 0 0
1 2
1 3
2 4
2 5
2 1 4
1 1 3
2 4 1
1 2 5
2 5 1

样例输出

0
1
7

样例说明

• 第一次询问时，路径字符串是 000。
• 第二次询问时，路径字符串是 001。
• 第三次询问时，路径字符串是 111。

数据范围

• 
• 
• 
• 

题解

这题同时有两种操作：

1. 树上路径整体翻转。
2. 树上路径按方向读成一个二进制数。

如果只做“路径翻转”，树链剖分加线段树就够了。难点在于询问时，路径是有方向的：u -> v 和 v -> u 读出来的二进制值一般不同。

所以在线段树里，不能只维护一个方向的答案，而是要把一段链同时维护两种读法：

• fwd：按区间从左到右读取时，对应的二进制值。
• rev：按区间从右到左读取时，对应的二进制值。

1. 区间信息如何合并

假设有两段二进制串：

• 左段为
• 右段为

把它们拼成 后，对应的数值就是：

因此在线段树里合并左右儿子时：

• fwd = left.fwd * 2^{right.len} + right.fwd
• rev = right.rev * 2^{left.len} + left.rev

2. 反置如何维护

如果一段长度为 的二进制串当前值为 val，把每一位都反置后，相当于把它变成：

因为长度为 的全 1 二进制值正好是 。

所以对一整个区间反置时：

• fwd = (2^L - 1) - fwd
• rev = (2^L - 1) - rev

这样就能在线段树上打懒标记。

3. 树链剖分如何处理方向

树链剖分会把一条路径拆成若干段重链区间。

但是这些区间在 dfs 序上默认是“链顶到链底”的方向，而路径查询要求的是“从 到 ” 的方向。

因此查询时要分成两部分维护：

• left：从原始起点 往上走时的答案。
• right：从路径另一端往回收集的答案。

处理规则：

• 若取到的是 这一侧的链段，那么真实方向是“从下往上”，要使用这段区间的 rev。
• 若取到的是 这一侧的链段，那么真实方向是“从上往下”，要使用这段区间的 fwd。

最后把 left 与 right 拼起来，就是整条路径 的答案。

4. 复杂度

每次路径修改或路径查询，都会被树链剖分拆成 段。

每段在线段树上的操作复杂度是 ，所以总复杂度为：

能够通过题目的数据范围。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

MOD = 10 ** 9 + 7


def solve() -> None:
    n, m = map(int, input().split())
    val = [0] + list(map(int, input().split()))

    g = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)

    fa = [0] * (n + 1)
    dep = [0] * (n + 1)
    siz = [0] * (n + 1)
    son = [0] * (n + 1)
    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    rnk = [0] * (n + 1)

    # 用显式栈建树，避免链式树下递归爆栈。
    dep[1] = 1
    order = []
    st = [1]
    while st:
        u = st.pop()
        order.append(u)
        for v in g[u]:
            if v == fa[u]:
                continue
            fa[v] = u
            dep[v] = dep[u] + 1
            st.append(v)

    for u in reversed(order):
        siz[u] = 1
        mx = 0
        for v in g[u]:
            if v == fa[u]:
                continue
            siz[u] += siz[v]
            if siz[v] > mx:
                mx = siz[v]
                son[u] = v

    tim = 0

    # 非递归剖分：沿重儿子一路走，轻儿子压栈等待新链开始。
    st = [(1, 1)]
    while st:
        u, tp = st.pop()
        x = u
        while x:
            tim += 1
            dfn[x] = tim
            rnk[tim] = x
            top[x] = tp
            for v in g[x]:
                if v != fa[x] and v != son[x]:
                    st.append((v, v))
            x = son[x]

    pw = [1] * (n + 1)
    one = [0] * (n + 1)
    for i in range(1, n + 1):
        pw[i] = pw[i - 1] * 2 % MOD
        one[i] = (pw[i] - 1 + MOD) % MOD

    arr = [0] * (n + 1)
    for i in range(1, n + 1):
        arr[dfn[i]] = val[i]

    seg_f = [0] * (n * 4)
    seg_r = [0] * (n * 4)
    tag = [0] * (n * 4)

    def pull(idx: int, l: int, r: int) -> None:
        mid = (l + r) >> 1
        ls = idx << 1
        rs = ls | 1
        len_l = mid - l + 1
        len_r = r - mid

        # 正向：左段在前，右段在后。
        seg_f[idx] = (seg_f[ls] * pw[len_r] + seg_f[rs]) % MOD

        # 反向：相当于先读右段反向，再读左段反向。
        seg_r[idx] = (seg_r[rs] * pw[len_l] + seg_r[ls]) % MOD

    def apply(idx: int, length: int) -> None:
        # 全 1 的值减去当前值，就得到逐位反置后的结果。
        seg_f[idx] = (one[length] - seg_f[idx]) % MOD
        seg_r[idx] = (one[length] - seg_r[idx]) % MOD
        tag[idx] ^= 1

    def push(idx: int, l: int, r: int) -> None:
        if not tag[idx] or l == r:
            return
        mid = (l + r) >> 1
        ls = idx << 1
        rs = ls | 1
        apply(ls, mid - l + 1)
        apply(rs, r - mid)
        tag[idx] = 0

    def build(idx: int, l: int, r: int) -> None:
        if l == r:
            seg_f[idx] = arr[l]
            seg_r[idx] = arr[l]
            return
        mid = (l + r) >> 1
        build(idx << 1, l, mid)
        build(idx << 1 | 1, mid + 1, r)
        pull(i