美团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个操作。  如果是查询操作，直接使用并查集即可，如果是删除操作，我们就进行加边的操作

还需要做离散化，因为n的范围为1e9，太麻烦，懒得处理了

import java.io.*;
import java.util.*;
public class T5 {
    static final int N = 100010;
    static int[] fa = new int[N];
    static List<String> res = new ArrayList<>();
    static int n, m, q;
    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]);
        m = Integer.parseInt(str[1]);
        q = Integer.parseInt(str[2]);

        for (int i = 0; i < N; i++)
            fa[i] = i;

        Set<int[]> edge = new HashSet<>();
        Set<int[]> del_edge = new HashSet<>();
        List<int[]> ops = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            str = br.readLine().split(" ");
            int u = Integer.parseInt(str[0]), v = Integer.parseInt(str[1]);
            edge.add(new int[]{u, v});
        }

        for (int i = 0; i < q; i++) {
            str = br.readLine().split(" ");
            int op = Integer.parseInt(str[0]), u = Integer.parseInt(str[1]), v = Integer.parseInt(str[2]);
            if (op == 1) {
                del_edge.add(new int[]{u, v});
                del_edge.add(new int[]{v, u});
            }
            ops.add(new int[]{op, u, v});
        }

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

        for (int i = q - 1; i >= 0; i--) {
            int[] t = ops.get(i);
            int u = t[1], v = t[2];
            if (t[0] == 1) {
                merge(u, v);
            } else {
                int a = find(u), b = find(v);
                if (a == 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 != fa[x])
            fa[x] = find(fa[x]);
        return fa[x];
    }

    public static void merge(int a, int b) {
        int ta = find(a), tb = find(b);
        fa[ta] = tb;
    }
}