美团3月9日笔试题_美团笔试 acm

第一题：小美的平衡矩阵

注意in.nextLine()和in.next()

import java.util.Scanner;

public class Main {
    static final int maxn = 210;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[][] a = new char[maxn][maxn];
        // int[][] b = new int[maxn][maxn];
        int[][] dp = new int[maxn][maxn];
        in.nextLine(); // 不加就报错！！！
        // 这是因为前面读取的是整数，后面是nextline取字符串，会先取后面的换行符。

        // for (int i = 0; i < n; ++i) {
        for (int i = 1; i <= n; ++i) {
            String line = in.nextLine();
            //String line = in.next(); 
            // 如果这么写就不需要in.nextLine();了
            // 因为如果读取到的标记之间有空格或换行符，则 .next() 方法会将其忽略。返回的是标记（token）字符串。
            for (int j = 1; j <= n; ++j) {
                // a[i][j] = line.charAt(j);
                a[i][j] = line.charAt(j - 1);
            }
        }
        // for (int i = 0; i < n; ++i) {
        // for (int j = 0; j < n; ++j) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                // b[i][j] = a[i][j] == '1' ? 1 : 0;
                int value = a[i][j] == '1' ? 1 : 0;
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + value;
            }
        }
        for (int len = 1; len <= n; ++len) {
            if (len % 2 == 1) System.out.println(0);
            else {
                int sum = 0;
                for (int i = len; i <= n; ++i) {
                    for (int j = len; j <= n; ++j) {
                        int num = dp[i][j] - dp[i - len][j] - dp[i][j - len] + dp[i - len][j - len];
                        // if (num == len)
                        if (num * 2 == len * len) sum++;
                    }
                }
                System.out.println(sum);
            }
        }
    }
}
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

第二题：小美的数组询问

注意注释的所有内容！！！都可能让代码超时！！！

• 数组大小预设
• 不用多余读取空行
• System.out.println 通常会比 System.out.printf 更快，后者常用于同时输出不同类型的数据

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int maxn = 100010;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        // in.nextLine();

        // int[] a = new int[n];
        int[] a = new int[maxn];
        long sum = 0, num_0 = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
            sum += a[i];
            if (a[i] == 0) num_0++;
        }
        // in.nextLine();

        while (q-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            // System.out.printf("%d %d\n", sum + l * num_0, sum + r * num_0);
            System.out.println((sum + l * num_0) + " " + (sum + r * num_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

第三题：小美的MT

注意ACM模式答案要打印输出，不要return

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine();
        String str = scanner.nextLine();

        int ans = 0, len = str.length();
        for (int i = 0; i < len; ++i) {
            if (str.charAt(i) == 'M' || str.charAt(i) == 'T') ans++;
        }
        // return ans + k > len ? len : ans + k;
        ans = Math.min(ans + k, len);
        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第四题：小美的朋友关系 3/30

并查集

// import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int N = 100010;
    static List<String> res = new ArrayList<>();
    static int[] f = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();

        // boolean[][] relations = new boolean[n][n];
        for (int i = 0; i < N; ++i) {
            f[i] = i;
        }

        Set<int[]> edge = new HashSet<>();
        while (m-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            edge.add(new int[] {a, b});
        }

        Set<int[]> del_edge = new HashSet<>();
        List<int[]> ops = new ArrayList<>();
        int temp = q;
        while (temp-- > 0) {
            int op = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            if (op == 1) {
                del_edge.add(new int[] {a, b});
                del_edge.add(new int[] {b, a});
            }
            ops.add(new int[] {op, a, b});

            // test
            // for (int i = 0; i < n; ++i) {
            //     for (int j = 0; j < n; ++j) {
            //         System.out.print(relations[i][j] + " ");
            //     }
            //     System.out.println();
            // }
        }

        // 建立并查集
        for (int[] e : edge) {
            boolean flag = true;
            for (int[] de : del_edge) {
                if (e[0] == de[0] && e[1] == de[1]) {
                    flag = false;
                    break;
                }
            }
            if (flag) merge(e[0], e[1]);
        }

        for (int i = q - 1; i >= 0; --i) {
            int op = ops.get(i)[0], a = ops.get(i)[1], b = ops.get(i)[2];
            if (op == 1) {
                merge(a, b);
            } else {
                if (find(a) == find(b)) res.add("Yes");
                else res.add("No");
            }
        }

        for (int i = res.size() - 1; i >= 0; --i) {
            System.out.println(res.get(i));
        }
    }
    public static int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    public static void merge(int x, int y) {
        int fx = find(f[x]), fy = find(f[y]);
        f[fx] = fy;
    }
}
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

第五题：小美的区间删除

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int maxn = 100010;
    static int[] a = new int[maxn], pre2 = new int[maxn], pre5 = new int[maxn];
    // pre[i]表示以i结尾之前所有字符含2或5的个数，不包括第i个
    static int n, k;
    static int total2 = 0, total5 = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        k = in.nextInt();
        // System.out.println(n+" "+k);
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
            int cnt2 = cal(a[i], 2), cnt5 = cal(a[i], 5);
            total2 += cnt2;
            total5 += cnt5;
            pre2[i + 1] = pre2[i] + cnt2;
            pre5[i + 1] = pre5[i] + cnt5;
            // System.out.println(cnt2+" "+cnt5);
            // System.out.println(pre2[i + 1]+" "+pre2[i]);
        }
        int res = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n) {
                // int cnt2 = pre2[j + 1] - pre2[i + 1];
                // int cnt5 = pre5[j + 1] - pre5[i + 1];
                int cnt2 = pre2[j + 1] - pre2[i];
                int cnt5 = pre5[j + 1] - pre5[i];
                int remain2 = total2 - cnt2, remain5 = total5 - cnt5;
                if (remain2 >= k && remain5 >= k) j++;
                else break;
            }
            // res += Math.max(j - i + 1, 0);
            res += Math.max(j - i, 0);
        }
        System.out.println(res);
    }

    public static int cal(int x, int mod) {
        int cnt = 0;
        while (x != 0) {
            if (x % mod == 0) cnt++;
            else break;
            x /= mod;
        }
        return 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51