美团2025春招第一次笔试题

第四题

题目描述

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

输入描述

第一行输入两个正整数 n,k

第二行输入n个正整数 a_i，代表塔子哥拿到的数组

1<=n , k<= 10e5
1<= a_i<=10e9

输出描述

一个整数，代表删除的方案数

思路

数论+双指针

package meituan.chun2025_1;

import java.util.Scanner;



public class Main4 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n];
        long time_2 = 0,time_5 = 0;
        int now;
        for(int i=0;i<n;i++){
            nums[i] = in.nextInt();
             now = nums[i];
            while(now>=5&&now%5==0){
                now/=5;
                time_5++;
            }
            while(now>=2&&now%2==0){
                now/=2;
                time_2++;
            }
        }
        int left = 0;
        long result = 0;
        long now_time_2 = 0,now_time_5 =0;

        for(int i=0;i<n;i++){
             now = nums[i];
            while(now>=5&&now%5==0){
                now/=5;
                now_time_5++;
            }
            while(now>=2&&now%2==0){
                now/=2;
                now_time_2++;
            }
            long zero_now = Math.min(time_5-now_time_5,time_2-now_time_2);
            while(left<=i&&left<n&&zero_now<k){
                now = nums[left++];
                while(now>=5&&now%5==0){
                    now/=5;
                    now_time_5--;
                }
                while(now>=2&&now%2==0){
                    now/=2;
                    now_time_2--;
                }
                zero_now = Math.min(time_5-now_time_5,time_2-now_time_2);
            }
            result+=i-left+1;
        }
        System.out.println(result);

    }
}

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

第五题

题目描述

输入描述

输出描述

思路

package meituan.chun2025_1;

import java.util.*;

class UnionFind {
    private int[] parent;
    private int[] size;
    private int count;

    public UnionFind(int n) {
        this.parent = new int[n];
        this.size = new int[n];
        this.count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            return;
        }
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public int getCount() {
        return count;
    }
}
class Function{
    public void Add(HashMap<Integer,HashSet<Integer>>  is_exist,int x, int y){
        int source = Math.max(x,y);
        int target = Math.min(x,y);
        HashSet<Integer> now_set = is_exist.getOrDefault(source,new HashSet<Integer>());
        now_set.add(target);
        is_exist.put(source,now_set);
    }

    public boolean isExist(HashMap<Integer,HashSet<Integer>>  is_exist,int x, int y){
        int source = Math.max(x,y);
        int target = Math.min(x,y);
        HashSet<Integer> now_set = is_exist.getOrDefault(source,new HashSet<Integer>());
        if (now_set.isEmpty())
            return false;
        if (!now_set.contains(target))
            return false;
        return true;
    }

    public void Remove(HashMap<Integer,HashSet<Integer>>  is_exist,int x, int y){
        int source = Math.max(x,y);
        int target = Math.min(x,y);
        HashSet<Integer> now_set = is_exist.get(source);
        now_set.remove(target);
    }
}
public class Main5 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int[][] relation = new int[m][2];
        UnionFind solution = new UnionFind(n+1);
        Function function = new Function();
        HashMap<Integer,HashSet<Integer>>  is_exist = new HashMap<>();
        HashMap<Integer,HashSet<Integer>>  is_forget = new HashMap<>();

        //input relation
        for(int i=0;i<m;i++){
            int x = in.nextInt();
            int y = in.nextInt();
            relation[i][0] = x;
            relation[i][1] = y;
            function.Add(is_exist,x,y);
        }

        //input op
        int[][] op = new int[n][3];
        for(int i=0;i<q;i++){
            op[i][0] = in.nextInt();
            op[i][1] = in.nextInt();
            op[i][2] = in.nextInt();
            if(op[i][0]==1)
                function.Add(is_forget,op[i][1],op[i][2]);
        }

                // add union
        for(int i=0;i<m;i++){
            if (!function.isExist(is_forget,relation[i][0],relation[i][1]))
                solution.union(relation[i][0],relation[i][1]);
        }

        Deque<Boolean> result = new LinkedList<>();
        for(int i=q-1;i>=0;i--){
            int[] now = op[i];
            if (now[0]==1){
                if (!function.isExist(is_exist,now[1],now[2]))
                    continue;
                function.Remove(is_exist,now[1],now[2]);
                solution.union(now[1],now[2]);
            }
            else
            {
                result.offerFirst(solution.find(now[1])==solution.find(now[2]));
        }
        }
        while(!result.isEmpty())
        {
            boolean now = result.pollFirst();
            if (now)
                System.out.println("Yes");
            else
                System.out.println("No");
        }

    }
    }


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