T1 T2 T3水题不说了T4题目描述: 小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？输入: 第一行输入两个正整数n，k。第二行输入n个正整数ai，代表小美拿到的数组。1<=n,k<=10^51<=ai<=10^9输出: 一个整数，代表删除的方案数。示例 1输入5 22 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^91 <= m,q  <= 10^51 <= u,v  <= n1 <= op  <= 2保证至少存在一次查询操作。输出描述: 对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。示例 1输入5 3 51 22 34 51 1 52 1 32 1 41 1 22 1 3输出 YesNoNo说明:第一次事件，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;    }}