美团3.9 笔试

T1 T2 T3水题不说了

T4

题目描述: 小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？
输入: 第一行输入两个正整数n，k。第二行输入n个正整数ai，代表小美拿到的数组。
1<=n,k<=10^5
1<=ai<=10^9
输出: 一个整数，代表删除的方案数。
示例 1
输入
5 2
2 5 3 4 20
输出
4
说明
第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。

思路:

计算构成0的个数，其实就是计算2和5的个数最小值。假设数组中2的个数为x，5的个数为y，构成0的个数就是min(x, y)。假设某区间2和5的个数分别为x1和y1，那么如果删除该区间，剩余2的个数为x-x1，剩余5的个数为y-y1，如果min(x-x1, y-y1) >= k，那么该区间可以删除。先计算2和5的前缀和，然后枚举可以删除的区间

import java.io.*;
public class T4 {
    static final int N = 100010;
    static int[] a = new int[N], pre2 = new int[N], pre5 = new int[N];
    static int n, k, total2, total5;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);

        str = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str[i]);
            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;
        }

        int res = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n) {
                int cnt2 = pre2[j + 1] - pre2[i];
                int cnt5 = pre5[j + 1] - pre5[i];
                int remain2 = total2 - cnt2, remain5 = total5 - cnt5;
                if (Math.min(remain2, remain5) >= k)
                    j++;
                else
                    break;
            }
            res += Math.max((j - i), 0);
        }
        System.out.println(res);
    }

    public static int cal(int num, int mod) {
        int cnt = 0;
        while (num != 0) {
            if (num % mod == 0)
                cnt++;
            else
                break;
            num /= mod;
        }
        return cnt;
    }
}

T5

题目描述: 小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。
注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。
输入描述: 第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。
1 <= n <= 10^9
1 <= m,q <= 10^5
1 <= u,v <= n
1 <= op <= 2
保证至少存在一次查询操作。
输出描述: 对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。
示例 1
输入
5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3
输出
Yes
No
No
说明:
第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。
第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问，显然 1 号和 4 号无法互相认识。
第四次事件，1 号和 2 号淡忘了。
第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

思路: 逆向并查集. 正向使用并查集因为涉及到删除操作，所以无法使用。但是我们可以逆向使用，先构建所有的边，然后将所有需要删除的边全部删除，从后往前遍历q个操作。如果是查询操作，直接使用并查集即可，如果是删除操作，我们就进行加边的操作

美团3.9 笔试

T4

T5

全站热榜