美团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 relationfor(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 opint[][] 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 unionfor(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");elseSystem.out.println("No");}}}