美团春招0309笔试复盘以及逆向思维的应用

文章介绍了美团春招笔试中的几道算法题及其解题思路。包括字符串修改、数组求和、矩阵平衡、区间删除和朋友关系查询等题目。每道题都提供了详细的输入输出描述、示例和解题思路，部分题目还附带了Java代码实现。文章强调了逆向思维在解题中的重要性，并通过具体题目展示了如何应用这种思维方式。

2024年3月9日算法 #逆向思维

文章目录

最近是春招金3银4的时间节点，各大厂相继放出一批岗位（当然还是卷得不行），所以还得在学习中不断提高自身。实习了近半年，已经很久没有刷过算法题，所以这次也是参加了美团的笔试找找手感。

这次笔试题目的质量很高，尤其最后一题涉及到了对逆向思维的考察，博主之前一篇文章中也提到了逆向思维题的魅力：记力扣周赛348中一道有趣的思维题，但对于这方面还是比较薄弱，能不能想出来有时得碰点运气（

小美的MT

题目

MT 是美团的缩写，因此小美很喜欢这两个字母。

现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作 $k$ 次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个’M’和’T’字符？

输入描述

第一行输入两个正整数，代表字符串长度 $n$ 和操作次数 $k$ 。第二行输入一个长度为 $n$ 的、仅由大写字母组成的字符串。

$1\leq k\leq n\leq 10^5$

输出描述

输出操作结束后最多共有多少个’M’和’T’字符。

示例

输入：

5 2
MTUAN

输出：

思路

签到题，遍历字符串，计算非’M’和’T’的字符数 $a$ ，答案就是 $n - a + min(a, k)$ ，代码略

小美的数组询问

题目

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。

现在小美想知道，如果那些未知的元素在区间 $[l,r]$ 范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？

共有 $q$ 次询问。

输入描述

第一行输入两个正整数 $n$ , $q$ ，代表数组大小和询问次数。

第二行输入 $n$ 个整数 $a_i$ ，其中如果输入 $a_i$ 的为 0，那么说明 $a_i$ 是未知的。

接下来的 $q$ 行，每行输入两个正整数 $l$ , $r$ ，代表一次询问。

$1\leq n,q\leq 10^5$

$0\leq a_i\leq 10^9$

$1\leq l\leq r\leq 10^9$

输出描述

输出 $q$ 行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例

输入：

输出：

5 6
8 8

说明：

只有第二个元素是未知的。第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。第二次询问，显然数组的元素和必然为 8。

思路

这题也是签到题，把数组里的值相加得到 $sum$ （注意数据范围），并统计0的个数 $z$ ，对于每个查询，最小和就是 $sum+(z*l)$ ，最大和就是 $sum+(z*r)$

这么一算下来，时间复杂度 $O(n+q)$ ，妥妥能过！结果一提交，超时…

这道题最坑的一点就是输出卡常（仅测试了Java，其他语言未知）。

这里我们用BufferedWriter优化输出，最后也是成功AC了

代码

import java.util.Scanner;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] a = new int[n];
        long sum = 0;
        long zeroCount = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            sum += a[i];
            if (a[i] == 0) {
                zeroCount++;
            }
        }

        // query
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < q; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            out.append(String.valueOf(sum + zeroCount * l))
                    .append(" ")
                    .append(String.valueOf(sum + zeroCount * r))
                    .append("\n");
        }
        out.flush();
    }
}

小美的平衡矩阵

题目

小美拿到了一个 $n*n$ 的矩阵，其中每个元素是 0 或者 1。

小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。

现在，小美希望你回答有多少个 $i*i$ 的完美矩形区域。你需要回答 $1<=i<=n$ 的所有答案。

输入描述

第一行输入一个正整数 $n$ ，代表矩阵大小。

接下来的 $n$ 行，每行输入一个长度为 $n$ 的01串，用来表示矩阵。

$1\leq n\leq 200$

输出描述

输出n行，第 $i$ 行输出的 $i*i$ 完美矩形区域的数量。

示例

输入：

输出：

思路

这道题的数据量不大，我们可以枚举所有符合条件的正方形，然后用二维前缀和快速求出正方形内1的数量，判断是否等于 $i*i/2$ 即可。

同时我们注意到只有正方形元素个数为偶数时，0和1的数量才有可能相等，所以我们只需要计算边长为偶数的正方形即可。

代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine()) + 1; // 加1避免边界判断
        int[] sum = new int[n * n]; // 二维前缀和优化为一维数组

        // 创建前缀和
        for (int i = 1; i < n; i++) {
            char[] s = in.nextLine().toCharArray();
            for (int j = 1; j < n; j++) {
                sum[i * n + j] = s[j - 1] - '0'
                        + sum[(i - 1) * n + j]
                        + sum[i * n + j - 1]
                        - sum[(i - 1) * n + j - 1];
            }
        }
        System.out.println(Arrays.toString(sum));

        // query
        int[] ans = new int[n - 1]; // 边长为i的正方形个数
        for (int x = 1; x < n; x++) {
            for (int y = 1; y < n; y++) {
                for (int i = 1; x + i < n && y + i < n; i += 2) {
                    int blockSum = sum[(x + i) * n + y + i]
                            - sum[(x - 1) * n + y + i]
                            - sum[(x + i) * n + y - 1]
                            + sum[(x - 1) * n + y - 1];
                    if (blockSum == (i + 1) * (i + 1) / 2) {
                        ans[i]++;
                    }
                }
            }
        }
        for (int i = 0; i < n - 1; i++) {
            System.out.println(ans[i]);
        }
    }
}

小美的区间删除

题目

小美拿到了一个大小为 $n$ 的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有 $k$ 个0。小美想知道，一共有多少种不同的删除方案？

输入描述

第一行输入两个正整数 $n$ ， $k$ 。第二行输入 $n$ 个正整数 $a_i$ ，代表小美拿到的数组。

$1\leq n,k\leq 10^5$

$1\leq a_i\leq 10^9$

输出描述

一个整数，代表删除的方案数。

示例

输入：

5 2
2 5 3 4 20

输出：

说明：

第一个方案，删除[3]。

第二个方案，删除[4]。

第三个方案，删除[3,4]。

第四个方案，删除[2]。

思路

和之前蓝桥杯做过的一道题有点相似，乘积末尾0的个数取决于2和5的因子数量（记为 $f2$ , $f5$ )，所以可以理解为删除一个区间后，剩下的因子数满足 $min(f2,f5)\geq k$ 的情况总数。

我们把思路逆转一下，问题的本质就变成了有多少个区间的因子数满足 $z-k\geq min(f2,f5)$ ，其中 $z$ 为整个数组乘积的末尾0数量。

嗯，这很逆转

可以用前缀和数组记录2和5的因子数量，但是笔试时没想到如何求出满足条件的方案数，~~所以没做出来~~，听群里大佬说可以用二分查找。

小美的朋友关系

题目

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。

现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？

事件共有 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\leq n \leq 10^9$

$1\leq m,q \leq 10^5$

$1\leq u,v \leq n$

$1\leq op \leq 2$

保证至少存在一次查询操作。

输出描述

对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 $u$ 的人和编号 $v$ 的人能通过朋友介绍互相认识，则输出”Yes”。否则输出”No”。

示例

输入：

输出：

Yes
No
No

说明：

第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。

第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。

第三次事件是询问，显然 1 号和 4 号无法互相认识。

第四次事件，1 号和 2 号淡忘了。

第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

思路

这题乍一看像是典型的并查集模板题，但仔细一看涉及到人员关联的删除，传统的并查集只支持添加边，并不支持删除已有边，一时间无从下手。

这时又要请出逆向思维了

嗯，又是这张图

我们注意到事件中只会对边进行删除，所以反过来想，我们可以找出所有在事件中删除的边，在初始化朋友关系时不把这些边加入并查集，这样我们就得到了一个执行了所有事件后的并查集，之后我们对事件逆序执行，有以下两种情况：

查询事件，正常进行查询即可，但是因为事件是逆序执行的所以我们需要一个栈来储存查询结果；
删除事件，需要反过来把边添加到并查集中；

最终把查询结果出栈即可。

代码

import java.util.*;

public class Main {
    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[][] init = new int[m][2];
        for (int i = 0; i < m; i++) {
            init[i][0] = in.nextInt();
            init[i][1] = in.nextInt();
        }

        // 储存事件和删除边
        int[][] event = new int[q][3];
        Set<DelEdge> set = new HashSet<>();
        for (int i = 0; i < q; i++) {
            event[i][0] = in.nextInt();
            event[i][1] = in.nextInt();
            event[i][2] = in.nextInt();
            if (event[i][0] == 1) {
                set.add(new DelEdge(event[i][1], event[i][2]));
            }
        }

        // 初始化
        UnionFind friend = new UnionFind();
        for (int i = 0; i < m; i++) {
            if (!set.contains(new DelEdge(init[i][0], init[i][1]))) {
                friend.union(init[i][0], init[i][1]);
            }
        }

        // 逆序处理事件
        Deque<Boolean> ans = new ArrayDeque<>();
        for (int i = q - 1; i >= 0; i--) {
            if (event[i][0] == 1) {
                friend.union(event[i][1], event[i][2]);
            } else {
                ans.push(friend.isConnected(event[i][1], event[i][2]));
            }
        }

        // 输出
        while (!ans.isEmpty()) {
            System.out.println(ans.pop() ? "Yes" : "No");
        }
    }

    // 并查集模板
    private static class UnionFind {
        private Map<Integer, Integer> parent; // n太大，用map

        public UnionFind() {
            parent = new HashMap<>();
        }

        public int find(int x) {
            if (!parent.containsKey(x)) {
                return x;
            }
            int root = parent.get(x);
            if (x != root) {
                parent.put(x, find(root));
            }
            return parent.get(x);
        }

        public void union(int x, int y) {
            int rootX = find(Math.min(x, y));
            int rootY = find(Math.max(x, y));
            if (rootX != rootY) {
                parent.put(rootX, rootY);
            }
        }

        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }
    }

    private static class DelEdge {
        int x;
        int y;

        public DelEdge(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            DelEdge delEdge = (DelEdge) o;

            return x == delEdge.x && y == delEdge.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}