2024美团春季笔试真题

本文为原创内容，转载请注明出处并附带原文链接。感谢您的尊重与支持！

你必须非常努力，才能看起来毫不费劲。

1.小美的01矩阵

题目描述

小美拿到了一个n行m列的矩阵，她想知道该矩阵有多少个 2 * 2 的子矩形满足 1 和 0 的数量相等？

输入描述

第一行输入两个正整数n, m用空格隔开。

接下来的n行，每行输入一个长度为m的 01 串，用来表示矩阵。

2 <= n, m <= 100

输出描述

一个整数，代表 1 和 0 的数量相等的 2 * 2 的子矩形数量。

输入示例

2 3
110
010

输出示例

1

提示信息

一共有两个2 * 2的子矩形，只有一个是合法的。
时间限制：c/c++/go：1s；其他语言：3s。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int m = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        // 读取矩阵并转换为 int[][]
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < n; j++) {
                matrix[i][j] = line.charAt(j) - '0';
            }
        }
        
        int count = 0;
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                int sum = matrix[i][j] + matrix[i][j + 1] +
                        matrix[i + 1][j] + matrix[i + 1][j + 1];

                if (sum == 2) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

2.小美的回文子串

题目描述

小美有一个长为 n的字符串s，她希望删除尽可能少的字符，使得字符串不含长度为偶数的回文子串。

她想知道她最少要删除几个字符，请你帮帮她吧。

输入描述

输入包含两行。

第一行一个正整数n(1 <= n <= 10^5)，表示字符串s 的长度。

第二行一个长为n字符串s。

输出描述

输出包含一行一个整数，表示最少删除数量。

输入示例

5
aaabc

输出示例

2

提示信息

删除变为 abc即可，删除了2个字符。

时间限制：c/c++/go：1s；其他语言:3s。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 签到题，子串里元素唯一就行
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        sc.nextLine(); 
        String str = sc.nextLine(); 

        long ans = 0;
        for (int i = 1; i < n; i++) {
            if (str.charAt(i) == str.charAt(i - 1)) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

3.小美的元素交换

题目描述

小美拿到了一个排列，其中初始所有元素都是红色，但有一些元素被染成了白色。

小美每次操作可以选择交换任意两个红色元素的位置。她希望操作尽可能少的次数使得数组变成非降序，你能帮帮她吗？

排列是指：一个长度为n的数组，其中 1 到n每个元素恰好出现了一次。

输入描述

第一行输入一个正整数n，代表数组的长度。
第二行输入n个正整数ai，代表数组的元素。
第三行输入一个长度为n的字符串，代表数组元素的染色情况。第i个字符为’R’代表第i个元素被染成红色，为’W’代表初始的白色。

1 <= n <= 105
1 <= ai <= n

输出描述

如果无法完成排序，请输出 -1。否则输出一个整数，代表操作的最小次数。

输入示例

4
1 3 2 4
WRRW

输出示例

1

提示信息

第一次操作，交换 2 和 3，数组变成[1,2,3,4]。

时间限制：c/c++/go：1s；其他语言：3s。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 哈希表，记录原数组中每个数字的位置
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[] nums = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            nums[i] = num;
        }
        sc.nextLine();
        String color = sc.nextLine();
        for (int i = 0; i < n; i++) {
            map.put(nums[i], i);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            // 将数字x放到下标为x-1的位置
            if (nums[i] == i + 1) {
                continue;
            }

            int pos = map.get(i + 1);  // 目标位置
            if (color.charAt(i) == 'R' && color.charAt(pos) == 'R') {
                res++;
                int temp = nums[i];
                nums[i] = nums[pos];
                nums[pos] = temp;

                // 交换后更新 map
                map.put(nums[pos], pos);
                map.put(nums[i], i);
            } else {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(res);
    }
}

4.小美的字符串切割

题目描述

小美定义一个字符串的权值为：字符串长度乘以字符的种类数。例如，”arcaea”的权值为 6 * 4=24

现在小美拿到了一个字符串，她希望你将该字符串切割成若干个连续子串，使得每个子串的权值不小于k。请你求出最终最多可以切割出的子串数量。

请注意，由于字符串过长，给出的字符串将是以连续段长度形式给出，例如：aabbaaa 将描述为 a(2)b(2)a(3)，aaaaaaaaaaaab 将描述为 a(12)b(1)。

注意：a(2)a(2)也是有效的数据。

输入描述

第一行输入一个两个正整数 n, k，代表原字符串长度和每个子串至少应取的权值。
第二行一个仅包含小写字母、数字和括号的字符串。长度不超过 10^6。
保证所有括号内的数字之和恰好等于n。给定的每个字母后面必然包含一个括号加数字。

1 <= k, n <= 10^18

输出描述

如果整个字符串的权值小于k，请直接输出 -1。

否则输出一个正整数，代表可以切割的最多子串数量。

输入示例

7 6
a(2)b(2)a(3)

输出示例

2

提示信息

该字符串表示为”aabbaaa”，切割成”aab”和”baaa”即可。

时间限制：c/c++/go：1s；其他语言：3s。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(); // 读取n
        long k = sc.nextLong(); // 读取k

        sc.nextLine(); // 清除缓冲区的换行符
        String s1 = sc.nextLine(); // 读取编码字符串

        int res = 0;
        Set<Character> set = new HashSet<>();
        int cntchar = 0;
        int cntlen = 0;
        int i = 0;

        while (i < s1.length()) {
            char c = s1.charAt(i); // 获取字符
            i += 2; // 跳过 '(' 和字符

            int sum = 0;
            // 解析数字
            while (s1.charAt(i) != ')') {
                sum = sum * 10 + s1.charAt(i) - '0';
                i++;
            }
            i++; // 跳过 ')'

            // 处理当前字符的重复部分
            for (int j = 0; j < sum; j++) {
                if (!set.contains(c)) {
                    set.add(c); // 新字符
                    cntchar++; // 字符种类增加
                }
                cntlen++; // 长度增加

                // 判断是否满足条件，重置计数
                if (cntlen * cntchar >= k) {
                    res++;
                    cntlen = 0;
                    cntchar = 0;
                    set.clear();
                }
            }
        }

        // 输出结果
        System.out.println(res != 0 ? res : -1);
    }
}

5.迷路的孩子

题目描述

有一棵有n个节点的树，小美在s节点，要去t节点。
但小美是经常迷路的孩子，她不知道该怎么走，因此她每次都会随机选择一条之前没有走过的边走，小美想知道她能到达 t 节点的概率是多少。
有多次询问，每次询问需要求出小美能到达t节点的概率对10^9+7取模后的结果。
如果最后答案为分数，则最简分式后的形式为 a/b ，其中a和b互质，那么输出整数 x 使得 b * x = a (mod 10^9+7) 且 0 <= x <= 10^9+7。可以证明这样的整数 x 是唯一的。

输入描述

第一行输入一个整数 n(1 <= n <= 210^5) 表示树节点个数。
接下来 n-1 行，每行输入两个整数 u, v(1 <= u, v <= n) 表示树上的边。
接下来一行，输入一个整数 q(1 <= q <= 210^5) 表示询问次数。
接下来 q 行，每行输入两个整数 s,t(1 <= s, t <= n) 表示询问。

输出描述

输出 q 行，每行输出一个整数表示概率。

输入示例

3
1 2
1 3
2
2 3
1 3

输出示例

1
500000004

提示信息

第1个询问：

小美有1的概率从节点2走到节点1，然后有1的概率从节点1走到节点3，因此有1的概率能到达节点3。1对1000000007取模后的结果为1。

第2个询问：

小美有1/2的概率从节点1走到节点2，有1/2的概率从节点1走到节点3，因此只有1/2的概率能到达节点3，1/2对1000000007取模后的结果为500000004。

时间限制：c/c++/go：2s；java：12s；其他语言：20s。

算法思路：LCA + 乘法逆元 + DFS。太难了，直接放弃…

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import java.io.*;
import java.util.*;
 
public class Main {
    static final int MOD = 1_000_000_007;
    static final int MAX_LOG = 20;
    static int[][] fa; // fa[i][j] 表示节点 i 的第 2^j 个祖先
    static int[] depth; // 记录节点深度
    static List<Integer>[] graph; // 邻接表存储树结构
    static long[] path; // 存储路径上的概率值
    static List<Pair>[] start, end; // 记录查询的起点和终点
    static long[] ans; // 存储每次查询的结果
 
    // 用于存储 (节点, 查询编号) 对
    static class Pair {
        int node, idx;
        Pair(int node, int idx) {
            this.node = node;
            this.idx = idx;
        }
    }
 
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 进行快速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st;
 
        // 读取节点数 n
        int n = Integer.parseInt(br.readLine());
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
 
        // 读取树的边
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            // 构建无向图
            graph[u].add(v);
            graph[v].add(u);
        }
 
        // 预处理 LCA（倍增法）
        fa = new int[n][MAX_LOG]; // 存储每个节点的第 2^i 个祖先
        depth = new int[n]; // 记录节点深度
        dfs1(0, 0); // 从 0 号节点开始 DFS 计算 LCA
 
        // 读取查询数 m
        int m = Integer.parseInt(br.readLine());
        start = new ArrayList[n];
        end = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            start[i] = new ArrayList<>();
            end[i] = new ArrayList<>();
        }
 
        ans = new long[m];
        Arrays.fill(ans, 1); // 初始时所有查询的概率值都是 1
 
        // 处理每个查询
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            // 计算 u 和 v 的最近公共祖先 (LCA)
            int z = lca(u, v);
 
            if (u != z) {
                start[u].add(new Pair(z, i)); // 记录 u 到 LCA 的计算
                if (v != z) {
                    end[v].add(new Pair(z, i)); // 记录 v 到 LCA 的计算
                    // 计算概率贡献值
                    ans[i] = modMul(qpow(graph[z].size() - 1), qpow(qpow(graph[z].size())));
                }
            } else {
                end[v].add(new Pair(u, i)); // 直接从 u 到 v
            }
        }
 
        // 预处理路径概率值
        path = new long[n];
        dfs2(0, 0); // 计算路径概率值
 
        // 输出所有查询结果
        for (long x : ans) {
            out.println(x);
        }
        out.flush();
    }
 
    /**
     * 预处理 LCA，使用 DFS 计算每个节点的深度和 2^i 级祖先
     */
    static void dfs1(int node, int parent) {
        depth[node] = depth[parent] + 1;
        fa[node][0] = parent; // 直接父节点
        // 计算 2^i 级祖先
        for (int i = 1; i < MAX_LOG; i++) {
            fa[node][i] = fa[fa[node][i - 1]][i - 1];
        }
        // 递归访问子节点
        for (int neighbor : graph[node]) {
            if (neighbor != parent) dfs1(neighbor, node);
        }
    }
 
    /**
     * 计算最近公共祖先 (LCA)
     */
    static int lca(int x, int y) {
        if (depth[x] < depth[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        // 使 x 和 y 处于同一深度
        for (int i = MAX_LOG - 1; i >= 0; i--) {
            if (depth[fa[x][i]] >= depth[y]) x = fa[x][i];
        }
        if (x == y) return x;
        // 同时向上跳，直到找到 LCA
        for (int i = MAX_LOG - 1; i >= 0; i--) {
            if (fa[x][i] != fa[y][i]) {
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }
 
    /**
     * 计算路径上的概率值
     */
    static void dfs2(int u, int parent) {
        // 计算 LCA -> v 的路径概率
        for (Pair p : end[u]) {
            int x = p.node, y = p.idx;
            long temp = modMul(modMul(path[parent], qpow(path[x])), qpow(graph[x].size()));
            ans[y] = modMul(ans[y], temp);
        }
 
        // 计算当前节点的路径概率值
        if (u != 0) path[u] = modMul(path[parent], qpow(graph[u].size() - 1));
        else path[u] = qpow(graph[u].size());
 
        // 计算 u -> LCA 的路径概率
        long qu = qpow(graph[u].size());
        for (Pair p : start[u]) {
            int x = p.node, y = p.idx;
            long temp = modMul(modMul(path[parent], qpow(path[x])), qu);
            ans[y] = modMul(ans[y], temp);
        }
 
        // 递归访问子节点
        for (int neighbor : graph[u]) {
            if (neighbor != parent) dfs2(neighbor, u);
        }
    }
 
    /**
     * 计算 a 的逆元（快速幂求逆）
     */
    static long qpow(long a) {
        return qpow(a, MOD - 2);
    }
 
    /**
     * 快速幂计算 (a^b) % MOD
     */
    static long qpow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
 
    /**
     * 计算 (a * b) % MOD
     */
    static long modMul(long a, long b) {
        return (a * b) % MOD;
    }
}