美团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);

    }
}

第五题

题目描述

输入描述

输出描述

思路

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");
        }

    }
    }