美团第一场秋招

美团0810秋招笔试真题解析（秋招第一批笔试）

小美的密码

小美准备登录美团，需要输入密码，小美忘记了密码，只记得密码可能是 n个字符串中的一个。小美会按照密码的长度从小到大依次尝试每个字符串，对于相同长度的字符串，小美随机尝试，并且相同的密码只会尝试一次。小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次才能登录成功。

小美不会重新尝试已经尝试过的字符串。成功登录后会立即停止尝试。

输入描述

第一行输入一个整数 n(1<=n<=1000)代表密码字符串的个数。

第二行输入一个只由小写字母组成的字符串 s(1<=|s|<=1000)代表正确的密码。

接下来 n 行，每行输入一个长度不超过 1000的字符串，代表小美记得的密码。

输出描述

在一行上输出两个整数，表示最少和最多尝试次数。

示例 1

输入

1
2
3
4
5
6
4
ab
abc
ab
ac
ac

输出

1
1 2

说明

小美可能按照 [“ab”, “ac”, “abc”] 的顺序尝试，第一次尝试成功，也可能按照 [“ac”, “ab”, “abc”] 的顺序尝试，第二次尝试成功。

小美在尝试 “ac” 发现不正确后不会继续尝试 “ac”。

思路与代码

HashMap+HashSet

由于是从长度小的开始，所以记录每个长度的密码都有多少个就好。

最优选择就是直接一次猜中对应长度的密码

反之最差就是最后一次猜中对应长度的密码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static void T1() {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        String password = in.next();
//        String[] nums=new String[len];
    //记录并存储次数
        HashSet<String> set = new HashSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            String str = in.next();
            if (!set.contains(str)) {
                map.merge(str.length(), 1, Integer::sum);
                set.add(str);
            }
        }
        int rightLen = password.length();
        int start=0;
        for (int i = 1; i < rightLen; i++) {
            start+=map.getOrDefault(i,0);
        }
        System.out.println((start + 1)+" "+(start+map.get(rightLen)));
    }

小美的数组删除

小美有一个长度为 n 的数组 a1,a2,….,an ，他可以对数组进行如下操作：

● 删除第一个元素 a1，同时数组的长度减一，花费为 x。

● 删除整个数组，花费为 k*MEX(a) （其中 MEX(a) 表示 a 中未出现过的最小非负整数。例如 [0,1,2,4] 的 MEX 为 3 ）。

小美想知道将 a 数组全部清空的最小代价是多少，请你帮帮他吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=1000) 代表数据组数，每组测试数据描述如下：

第一行输入三个正整数 n,k,x(1<=n<=2*10^5, 1<=k,x<=10^9) 代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。

第二行输入 n 个整数 a1,a2,….,an(0<=ai<=n)，表示数组元素。

除此之外，保证所有的 n 之和不超过 2*10^5。

输出描述

对于每一组测试数据，在一行上输出一个整数表示将数组中所有元素全部删除的最小花费。

示例 1

输入

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

输出

1
15

说明

1
2
3
4
5
6
7
若不执行操作一就全部删除，MEX{4,5,2,3,1,0} = 6，花费 18 ；
若执行一次操作一后全部删除，MEX{5,2,3,1,0} = 4，花费 3+12；
若执行两次操作一后全部删除，MEX{2,3,1,0} = 4，花费 6+12 ；
若执行三次操作一后全部删除，MEX{3,1,0} = 2，花费 9+6 ；
若执行四次操作一后全部删除，MEX{1,0} = 2，花费 12+6 ；
若执行五次操作一后全部删除，MEX{0} = 1，花费 15+3；
若执行六次操作一，MEX{} = 0，花费 18；

思路和代码

枚举删除的次数。同时需要排序数组，找出整个数组的非负整数

但是需要注意当前删除的数字是不是小于上一次的最小非负整数

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
public static void main(String[] args) {
//        T1();
        Scanner in = new Scanner(System.in);
        int times = in.nextInt();
        for (int i = 0; i < times; i++) {
            int len = in.nextInt();
            int allNums = in.nextInt();
//            删除一个
            int one = in.nextInt();
            int[] nums = new int[len];
            for (int j = 0; j < len; j++) {
                nums[j] = in.nextInt();
            }
            int[] tempNums = Arrays.copyOf(nums, len);
            Arrays.sort(tempNums);
//            最小非负整数
            int mex = len;
            for (int j = 0; j < len; j++) {
                if (tempNums[j] != j) {
                    mex = j;
                    break;
                }
            }
//            枚举次数
            int ans = mex * allNums;
            for (int j = 0; j < len; j++) {
                if (nums[j] < mex) {
                    mex = nums[j];
                }
                ans=Math.min(ans,((j+1)*one)+(allNums*mex));
            }
            System.out.println(ans);

        }
    }

小美的彩带

小美的彩带是由一条长度为 n 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用 ai 表示。因此当 i>n 时，ai = ai-n 。

小美每次会从左往后或从右往左剪一段长度为 x 的彩带，她想知道她每次剪下来的彩带有多少种颜色。

输入描述

第一行输入两个整数 n,q(1<=n,q<=2*10^5) 代表彩带长度、剪彩带次数。

第二行输入 n 个整数 a1,a2,…,an(1<=ai<=10^9) 代表彩带每一个位置的颜色。

此后 q 行，每行输入一个字符 c 和一个整数 x(1<=x<=10^9; c∈L,R) 代表裁剪方向和裁剪长度，其中 ‘L’ 说明从左往右剪， ‘R’ 说明从右往左剪 。

输出描述

对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。

示例 1

输入

1
2
3
4
5
6 3
1 1 4 5 1 4
L 2
L 3
R 12

输出

1
2
3
1
3
3

说明

1
2
3
第一次剪彩带，剪下来的是 [1,1] ，有 {1} 这 1 种颜色；
第二次剪彩带，剪下来的是 [4,5,1] ，有 {1,4,5} 这 3 种颜色；
第三次剪彩带，剪下来的是 [1,1,4,5,1,4,1,1,4,5,1,4] ，有 {1,4,5} 这 3 种颜色。

思路与代码

离散化+离线处理（莫队）+树状数组。

观察数据范围：n<=200000, q<=200000，那么此题大概率是一个O(q*logn)的复杂度的要求。

由于是循环数组，那么假设我们区间的长度x是大于n的，那么必然是所有的元素数量的个数。我们不妨可以进行以下处理：将所有的区间先读取进内存，然后将区间排序，做一个预处理，这样对于不同的区间运算可以加速，避免重复运算。（思想就是莫队算法）

由于a[i]的范围是10^9，因此需要对数据进行离散化处理，最后我们使用树状数组来快速计算区间内的不同颜色数量，这个复杂度可以做到O(nlogn)。

类似题目思路可以参考洛谷：https://www.luogu.com.cn/problem/P1972

Java

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
import java.util.*;

public class Main {
    private static final int MAXN = 2000007;
    
    private static long[] a = new long[MAXN];
    private static long[] ans = new long[MAXN];
    private static long[] hsh = new long[MAXN];
    private static long[] vis = new long[MAXN];
    private static long[] c = new long[MAXN];

    private static class Query {
        int l, r, id;
        Query(int l, int r, int id) {
            this.l = l;
            this.r = r;
            this.id = id;
        }
    }

    private static int lowbit(int x) {
        return x & -x;
    }

    private static void update(int x, int k) {
        for (int i = x; i < MAXN; i += lowbit(i)) {
            c[i] += k;
        }
    }

    private static long getsum(int x) {
        long sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            sum += c[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        
        List<Query> queries = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextLong();
            hsh[i] = a[i];
        }
        

        Arrays.sort(hsh, 1, n + 1);
        int len = 1;
        for (int i = 2; i <= n; i++) {
            if (hsh[i] != hsh[len]) {
                hsh[++len] = hsh[i];
            }
        }
        

        for (int i = 1; i <= n; i++) {
            a[i] = Arrays.binarySearch(hsh, 1, len + 1, a[i]) + 1;
            a[n + i] = a[i];
        }
        
        int nl = 1, nr = n * 2;
        for (int i = 1; i <= q; i++) {
            char c = scanner.next().charAt(0);
            int x = scanner.nextInt();
            x = Math.min(x, n);
            if (c == 'L') {
                if (nl > n) {
                    nl -= n;
                }
                queries.add(new Query(nl, nl + x - 1, i));
                nl += x;
            } else {
                if (nr <= n) {
                    nr += n;
                }
                queries.add(new Query(nr - x + 1, nr, i));
                nr -= x;
            }
        }
        

        queries.sort(Comparator.comparingInt(a -> a.r));
        
        int cur = 1;

        for (Query query : queries) {
            for (int i = cur; i <= query.r; i++) {
                if (vis[(int) a[i]] > 0) {
                    update((int) vis[(int) a[i]], -1);
                }
                update(i, 1);
                vis[(int) a[i]] = i;
            }
            cur = query.r + 1;
            ans[query.id] = getsum(query.r) - getsum(query.l - 1);
        }
        

        for (int i = 1; i <= q; i++) {
            System.out.println(ans[i]);
        }
        
        scanner.close();
    }
}

答案版本2 ：主席树

该问题本质为求数组内颜色个数， 如果L大于整个数组，就是数组本身的答案。

如果L < 整个数组，考虑分为一个前缀一个后缀进行求解。我们可以将两段数组拼在一起。然后问题变为多次求一个区间内的数的种类。由于n = 1e5 ,无法使用朴素暴力获得满分。rmq询问颜色个数，经典主席树，也就是对颜色做可持久化值域线段树，然后差分询问两个历史版本即可。由于太过复杂，这里不放代码。

考虑n = 1e3的情况拿部分分，我们可以使用一个set，每次截取数组子段，装入set进行查询他的size。

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
def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    unique_elements = set(a)
    
    curl = 0
    curr = n - 1
    
    for _ in range(q):
        op, x = input().split()
        x = int(x)
        
        if x > n:
            print(len(unique_elements))
        elif op == "L":
            tmp = set()
            for _ in range(x):
                tmp.add(a[curl])
                curl = (curl + 1) % n
            print(len(tmp))
        else:  # operation is "R"
            tmp = set()
            for _ in range(x):
                tmp.add(a[curr])
                curr = (curr - 1 + n) % n
            print(len(tmp))

if __name__ == "__main__":
    main()

总结

第一道题想出来了，比较简单。

第二道题也有了思路，但是卡在了如何找出没出现的最小非负整数+遍历时动态更新。

原本思路是原地哈希，因为在leetcode上做过类似的题，这样的时间复杂度比较小。

但还是答案直接，直接排序，找出没出现的。

第三题不会，放弃，不是给我做的

收货：

  • 每道题的题解都得看看有没有别的题解，也许解法不是最优，但是思路是值得学习的。
  • 这次学会了看数据范围，有些是暴力不了的，如第三题，那就直接放弃吧，也许暴力能偷一点点？
笔试题解
#美团
美团第一场秋招
https://hexo-blog-five-swart.vercel.app/2024/08/11/美团第一场秋招/
作者
方立
发布于
2024年8月11日
许可协议