【刷题节】美团2024年春招第一场笔试【技术】_小美的平衡矩阵

1.小美的平衡矩阵

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] nums = new int[n][n], sum = new int[n][n];
        char[] chars;
        for (int i = 0; i < n; i++) {
            chars = scanner.next().toCharArray();
            for (int j = 0; j < n; j++) {
                nums[i][j] = chars[j] - '0';
                if ( i != 0 &&
                        j != 0)sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] +
                        nums[i][j];
                else if (i != 0)sum[i][j] = sum[i - 1][j] + nums[i][j];
                else if (j != 0)sum[i][j] = sum[i][j - 1] + nums[i][j];
                else sum[i][j] = nums[i][j];
            }
        }
        int res = 0;
        int tar = 0;
        for(int i = 0;i<n;i++){
            if(i%2==0) System.out.println(0);
            else{
                for (int j = i; j < n; j++) {
                    for (int w = i; w < n; w++) {
                        if (j == i && w == i)tar = sum[j][w];
                        else if (j == i)tar = sum[j][w] - sum[j][w - i - 1];
                        else if (w == i)tar = sum[j][w] - sum[j - i - 1][w];
                        else tar = sum[j][w] - sum[j][w - i - 1] - sum[j - i - 1][w] + sum[j - i - 1][w
                                    - i - 1];
                        if (tar == (i + 1) * (i + 1) / 2)res++;
                    }
                }
                System.out.println(res);
                res = 0;
                }

            }



    }
}
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

2. 小美的数组询问

import java.util.Scanner;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();int n=(int)in.nval;
        in.nextToken();int q=(int)in.nval;
        int[] arr = new int [n];
        long sum = 0l;
        long a = 0;
        for (int i = 0; i < n; i++) {
            in.nextToken();
            arr[i] = (int)in.nval;
            if(arr[i]==0) a++;
            sum += (long)arr[i];
            
        }
        for (int i = 0; i < q; i++) {
            in.nextToken();
            int  left = (int)in.nval;
            in.nextToken();
            int right = (int)in.nval;
            System.out.print(sum+a*left);
            System.out.print(" ");
            System.out.println(sum+a*right);
            
        }

    }
}
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

3.小美的 MT

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

public class Main {
    public static void main(String[] args) throws IOException {
//        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//        in.nextToken();int n=(int)in.nval;
//        in.nextToken();int q=(int)in.nval;
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();int n = (int) in.nval;
        in.nextToken();int k = (int) in.nval;
        in.nextToken();String string = in.sval;
        int sum = 0;
        for(int i = 0;i<string.length();i++){
            if(string.charAt(i)=='M'||string.charAt(i)=='T'){
                sum++;
            }
        }
        System.out.println(sum+k>=n?n:sum+k);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.Scanner;

public class Main {
    static final int maxn = 100010;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] a = new int[maxn];
        long cnt = 0;
        long sum = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = scanner.nextInt();
            if (a[i] == 0) {
                cnt++;
            } else {
                sum += a[i];
            }
        }
        while (q-- > 0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            System.out.println((sum + l * cnt) + " " + (sum + r * cnt));
        }
    }
}

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

4.小美的朋友关系

关键词：并查集、逆序、栈、类、方法重写、集合

这道题的题解是来自另一个大佬： 原链接：https://zhuanlan.zhihu.com/p/686093235

但是我放进去 是超时，希望有大佬批评指正！！

这题考到我的智商盲点的，我们需要维护一个并查集来记录朋友关系，这题难点就在于后期会存在遗忘的情况，但是并查集只有合并操作，没有删除操作，由于进行了路径压缩，因此删除的时候难以确定应该修改哪些节点。但是我们可以逆向操作，我们可以逆向遍历查询，遇到删除操作如果是逆序的话则是合并操作，这样就能用并查集进行处理了。确定了大方向后，我们首先读入初始化的边存入数组和集合中，然后存储后期的查询，然后对应后期遗忘的边存入集合方便后续判断。然后才开始初始化关系，注意后期要删除的边不要初始化。然后在存储查询的时候要注意，遗忘中可能包括不是初始化时的操作，是间接关系，是不需要执行并操作的，然后也会出现重复的遗忘，我们要执行加边的是第一次出现的遗忘，因此需要将重复的遗忘从查询中删除。然后要注意重写类的equals方法，传入的参数需要与父类一致，都是Object类，然后hashcode也需要重写，否则集合会判断两者不一样。

import java.util.*;

public class Main {
    static Map<Integer, Integer> fa = new HashMap<>();
    static Set<Pair> fr = new HashSet<>();
    static List<Pair> qs = new ArrayList<>();
    static List<String> ans = new ArrayList<>();

    static class Pair {
        int first;
        int second;
        int third;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        Pair(int first, int second, int third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return first == pair.first && second == pair.second && third == pair.third;
        }

        @Override
        public int hashCode() {
            return Objects.hash(first, second, third);
        }
    }

    static int find(int x) {
        if (!fa.containsKey(x)) return x;
        fa.put(x, find(fa.get(x)));
        return fa.get(x);
    }

    static void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            fa.put(x, y);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int q = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            fr.add(new Pair(u, v));
        }
        for (int i = 0; i < q; i++) {
            int op = scanner.nextInt();
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            if (op == 1) {
                fr.remove(new Pair(u, v));
            }
            qs.add(new Pair(op, u, v));
        }
        Collections.reverse(qs);
        for (Pair pair : fr) {
            merge(pair.first, pair.second);
        }
        for (Pair pair : qs) {
            if (pair.first == 1) {
                merge(pair.second, pair.third);
            } else {
                ans.add(find(pair.second) == find(pair.third) ? "Yes" : "No");
            }
        }
        Collections.reverse(ans);
        for (String s : ans) {
            System.out.println(s);
        }
    }
}
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

5.小美的区间删除

小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？

关键词：数学、前缀和、滑动窗口

这题我只想到了使用前缀和来解决，因此会遇到乘法太大导致溢出的问题，当时还打算使用BigDecimal来解决，原来是自己想的简单了。这题除了前缀和，还考了数学问题，实际上能够得到10的倍数只与2和5的个数相关，其他因子对这个不产生影响。因此我们只需对数组中每个数进行分解，看里面包含多少个2和5，然后用前缀和的方式记录。然后就使用滑动窗口来寻找可以删除的区间。判断条件是这个剩下的区间的2和5的最小值与k进行比较，因为一个2和一个5相乘就是10，那么2和5的最小值就是末尾为零的个数。

import java.util.*;

public class MaxCase {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        long[] pre2 = new long[n+1];
        long[] pre5 = new long[n+1];
        int cnt2,cnt5,temp;

        for(int i=0;i<n;i++){
            temp = in.nextInt();
            cnt2=0;
            cnt5=0;
            for(int x=temp;x%2==0;x/=2) cnt2++;
            for(int x=temp;x%5==0;x/=5) cnt5++;
            pre2[i+1] = pre2[i] + cnt2;
            pre5[i+1] = pre5[i] + cnt5;
        }

        long res = 0;
        for(int i=0,j=0;i<n;i++){
            while(j<n){
                long remain2 = pre2[n] - pre2[j+1] + pre2[i];
                long remain5 = pre5[n] - pre5[j+1] + pre5[i];
                if(Math.min(remain2,remain5)<k) break;
                j++;
            }
            res += Math.max(j-i, 0);
        }

        System.out.println(res);
    }
}
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

垃圾的我写的，我实在不知道哪错了！希望大佬指正！！！备受感谢！！

import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {

        StreamTokenizer tokenizer = new StreamTokenizer(new InputStreamReader(System.in));
        tokenizer.nextToken();        int n = (int) tokenizer.nval;
        tokenizer.nextToken();        int k = (int) tokenizer.nval;
        int [] arr = new int[n];
        long sum = 1l;
        for (int i = 0; i < arr.length; i++) {
            tokenizer.nextToken();    arr[i] = (int) tokenizer.nval;
            sum *=arr[i];
        }
        long temp = sum;
        long result = 0;
        for(int left = 0; left < arr.length;left++) {
            for(int right = left;right<arr.length;right++){
                temp /= arr[right];
                if(moweizero(temp,k))result++;
                else {
                    break;
                }
            }
            temp = sum;
        }
        System.out.println(result);


    }
    public static boolean  moweizero (long sum ,int k){
        while(k>0){
            if(sum==0)return false;
            if(sum%10!=0)return false;
            sum = sum/10;
            k--;
        }
        return true;
    }
}
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