美团暑期实习 3.18笔试 后端5道题 题解（Java版）

• 测评 oj 平台，塔子哥学算法：http://101.43.147.120/

• 参考：今夕kpole_「技术笔试」美团暑期实习 2023-03-18

1. 捕获敌人

题目描述

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。

敌人的位置将被一个二维坐标 $(x,y)(x,y)$ 所描述。

小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。捕获的敌人之间的横坐标的最大差值不能大于 $AA$，纵坐标的最大差值不能大于 $BB$ 。

现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

输入描述

第一行三个整数 $N,A,BN,A,B$，表示共有 $NN$ 个敌人，小美的全屏技能的参数 $AA$ 和参数 $BB$。

接下来 $NN$ 行，每行两个数字 $x,yx,y$，描述一个敌人所在的坐标。

$1⩽N\le 5001\; \backslash leqslant\; N\; \le \; 500$，$1⩽A,B⩽10001\backslash leqslant\; A\; ,\; B\backslash leqslant\; 1000$，$1⩽x,y⩽10001\backslash leqslant\; x,y\backslash leqslant\; 1000$

输出描述

一行，一个整数表示小美使用技能单次所可以捕获的最多数量。

样例1

输入

3 1 1
1 1
1 2
1 3

输出

2

说明：最多可以同时捕获两名敌人，可以是 $(1,1)(1,1)$ 和 $(1,2)(1,2)$ 处的敌人，也可以是 $(1,2)(1,2)$ 和 $(1,3)(1,3)$ 处的敌人，但不可以同时捕获三名敌人，因为三名敌人时，纵坐标的最大差值是 $22$，超过了参数 $BB$ 的值 $11$。

样例2

输入

5 1 2
1 1
2 2
3 3
1 3
1 4

输出

3

说明：最多同时捕获三名敌人。其中一种方案如下: 捕获 $(1,1)(1,1)$，$(1,3)(1,3)$，$(2,2)(2,2)$ 处的三个敌人。

题解

二维前缀和，关于二维前缀和的学习可参考：蓝桥杯AcWing学习笔记 2-2前缀和的学习（附相关蓝桥真题：K倍区间）(Java)

跟 AcWing 的这道题几乎一样：99. 激光炸弹

就是在一个大矩形中有若干个点，给我们一个小矩阵，看它最多能框住多少个点。

所以我们先读入敌人坐标，将有敌人的坐标初始化为 $11$。

然后用二维前缀和预处理，再枚举每一个范围内 $(A,B)(A,B)$ 的子矩阵，取一个 $maxmax$ 即可。

时间复杂度 $O(N^2)O(N^2)$

import java.util.Scanner;

public class Main {
    static final int N = 1000;
    static int[][] g = new int[N + 10][N + 10];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
        a++; b++; // 最大间隔++，前缀和下标从1开始处理，防止边界问题
        // 与N取min
        a = Math.min(a, N);
        b = Math.min(b, N);
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            g[x][y]++; // 读入敌人坐标
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1]; // 二维前缀和预处理 公式一
            }
        }
        int res = 0;
        // 枚举一下所有长宽是ab的矩形，(i,j)为右下角，取max
        for (int i = a; i <= N; i++) {
            for (int j = b; j <= N; j++) {
                res = Math.max(res, g[i][j] - g[i - a][j] - g[i][j - b] + g[i - a][j - b]); // 求某一个子矩阵的值 公式二
            }
        }
        System.out.println(res);
    }
}

2. 截彩带

题目描述

小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。

因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过 $KK$ 种。

显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过 $KK$ 种。

输入描述

第一行两个整数 $N,KN,K$，以空格分开，分别表示彩带有 $NN$ 厘米长，你截取的一段连续的彩带不能超过 $KK$ 种颜色。接下来一行 $NN$ 个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。

$1\le N,K\le 50001\le N,K\le 5000$，彩带上的颜色数字介于 $[1,2000][1,2000]$ 之间。

输出描述

一行，一个整数，表示选取的彩带的最大长度。

样例

输入

8 3
1 2 3 2 1 4 5 1

输出

5

说明：最长的一段彩带是 $[1,2,3,2,1][1,2,3,2,1]$ 共 $55$ 厘米。

题解

求连续子数组最大和，但此题还要求区间的种类数不能超过 $KK$ 种，所以在双指针的基础上我们还需要用 哈希 来维护区间的种类数。

暴力解法

直接两重循环，用 set 维护区间种类数。

时间复杂度 $O(N^2)O(N^2)$

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int res = 0;
        for (int i = 0; i < n; i++) {
            Set<Integer> set = new HashSet<>();
            for (int j = i; j < n; j++) {
                set.add(a[j]);
                if (set.size() > k) break;
                res = Math.max(res, j - i + 1);
            }
        }
        System.out.println(res);
    }
}

双指针 + map

时间复杂度 $O(N)O(N)$

import java.util.Scanner;

public class Main {

    static final int N = 5010;
    static int[] cnt = new int[N];
    static int num;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        int res = 0;
        for (int i = 0, j = 0; i < n; i++) {
            a[i] = sc.nextInt();
            add(a[i]);
            while (num > k) {
                sub(a[j]);
                j++;
            }
            res = Math.max(res, i - j + 1);
        }
        System.out.println(res);
    }

    private static void add(int x) {
        if (++cnt[x] == 1) num++;
    }

    private static void sub(int x) {
        if (--cnt[x] == 0) num--;
    }
}

3. 字符串变回文串

题目描述

现在小美获得了一个字符串。小美想要使得这个字符串是回文串。

小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符 '$aa$' - '$zz$'。

你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串，数据保证能在题目限制下形成回文字符串。

注：回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。例如字符串 $abcba,aaaa,accaabcba,aaaa,acca$ 都是回文字符串。字符串 $abcd,aceaabcd,acea$ 都不是回文字符串。

输入描述

一行，一个字符串。字符串中仅由小写英文字符构成。

保证字符串不会是空字符串。

字符串长度介于 $[1,100000][1,100000]$ 之间。

输出描述

一行，一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例1

输入

acca

输出

aaaa

说明：原来的字符串已经是回文字符串了。但它不是题目条件下可以取得的字典序最小的回文字符串。将第二个字符和第三个字符都改为 $aa$ 可以获得字典序最小的回文字符串。

样例2

输入

abcde

输出

abcba

说明：将 $dede$ 改为 $baba$ 可以获得字典序最小的回文字符串。

题解

模拟题，挺复杂的，需要考虑很多情况。

因为这道题有一句话：数据保证能在题目限制下形成回文字符串。

所以它保证让我们至少更改两次后 它一定是一个回文串，所以我们可以得到以下步骤：

1. 首先将串变成回文串，即前 $n\mathrm{/}2n/2$ 个字符与后 $n\mathrm{/}2n/2$ 个字符完全相同。
2. 然后如果有剩余的次数，优先使最前面的字符变为 $aa$。注意这一步操作可能会修改第一步已经修改过的位置（如果有，则这一步只消耗一次）。
3. 如果串长度是奇数，并且还有剩余次数，则修改中间的字符。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] c = s.toCharArray();
        int n = c.length;
        int[] v = new int[n];
        int cnt = 2;
        // step1 先变为字典序最小的回文串
        for (int i = 0; i < n / 2; i++) {
            if (c[i] != c[n - i - 1]) {
                cnt--;
                char t = (char) Math.min(c[i], c[n - i - 1]);
                c[i] = t;
                c[n - i - 1] = t;
                v[i] = 1;
            }
        }
        // step2
        for (int i = 0; i < n / 2; i++) {
            if (c[i] != 'a') {
                int cost = v[i] == 1 ? 1 : 2;
                if (cnt >= cost) {
                    cnt -= cost;
                    c[i] = c[n - i - 1] = 'a';
                }
            }
        }
        // step3
        if (cnt >= 1 && n % 2 == 1) {
            if (c[n / 2] != 'a') {
                c[n / 2] = 'a';
            }
        }
        System.out.println(c);
    }
}

4. 购买物品

题目描述

网在商店里有 $NN$ 个物品，每个物品有原价和折扣价小美相要购买商品。小美拥有 $XX$ 元，一共 $YY$ 张折扣券。

小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽置减少花费。

你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入描述

第一行三个整数，以空格分开，分别表示 $N,X,YN,X,Y$ 。接下来 $NN$ 行，每行两个整数，以空格分开，表示一个的原价和折扣价。 $1\le N\le 100\mathrm{，}1\le X\le 5000\mathrm{，}1\le Y\le 501\le N\le 100，1\le X\le 5000，1\le Y\le 50$，每个商品原价和折扣价均介于 $[1,50][1,50]$ 之间。

输出描述

一行，两个整数，以空格分开。第一个数字表示最多买几个商品，第二个数字表示在满足商品尽量多的前提下所花费的最少的钱数。

样例1

输入

3 5 1
4 3
3 1
6 5

输出

2 5

说明：第一个商品原价购入，第二个商品折扣价购入，可以获得最多的商品数量 $22$ 个。此时消耗 $55$ 元。因此输出 $2525$。

样例2

输入

3 5 1
4 3
3 1
6 1

输出

2 4

说明：可以发现有很多种买两个商品的方法最省钱的方案是第二个商品原价购入，第三个商品折扣价购入。此时花费 $44$ 元。

样例3

输入

10 30 3
2 1
3 2
2 1
10 8
6 5
4 3
2 1
10 9
5 4
4 2

输出

8 24

题解

三维 $0101$ 背包问题，设 f[i][j][k] 表示前 $ii$ 个物品，买了 $jj$ 个，用了 $kk$ 个优惠券的最少价格。

三个转移情况：

• 不买：  f[i][j][k] = f[i - 1][j][k]
• 直接买：f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + p[i])
• 用劵买：f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - 1] + p2[i])

注意边界处理和初始化。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt(); // n个物品 x元 y个优惠券
        int[] p = new int[n + 1], p2 = new int[n + 1]; // 原价 折扣价
        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
            p2[i] = sc.nextInt();
        }

        int[][][] f = new int[n + 1][n + 1][y + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= y; k++) {
                    f[i][j][k] = Integer.MAX_VALUE / 2;
                }
            }
        }

        f[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= i && k <= y; k++) {
                    // 不买
                    f[i][j][k] = f[i - 1][j][k];
                    if (j >= 1) {
                        // 原价购买
                        if (f[i - 1][j - 1][k] + p[i] <= x) {
                            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k] + p[i]);
                        }
                        // 折扣购买
                        if (k >= 1 && f[i - 1][j - 1][k - 1] + p2[i] <= x) {
                            f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][k - 1] + p2[i]);
                        }
                    }
                }
            }
        }

        int cnt = 0, cost = x + 1;
        for (int j = 0; j <= n; j++) {
            for (int t = 0; t <= y; t++) {
                if (f[n][j][t] <= x) {
                    if (cnt < j) {
                        cnt = j;
                        cost = f[n][j][t];
                    } else if (cnt == j) {
                        cost = Math.min(cost, f[n][j][t]);
                    }
                }
            }
        }
        if (cost > x) cost = 0;
        System.out.println(cnt + " " + cost);
    }
}

另一种dp思维：设 dp[i][j][k] 表示前 $ii$ 个物品，花费了 $jj$ 元，用了 $kk$ 个优惠券能买到的最多的商品。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
        int[] a = new int[n + 1], b = new int[n + 1];
        int[][][] dp = new int[n + 1][x + 1][y + 1], cost = new int[n + 1][x + 1][y + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= x; j++) {
                for (int k = 0; k <= y; k++) {
                    // 不买
                    dp[i][j][k] = dp[i - 1][j][k];
                    cost[i][j][k] = cost[i - 1][j][k];
                    // 直接买
                    if (j - a[i] >= 0) {
                        if (dp[i - 1][j - a[i]][k] + 1 > dp[i][j][k]) {
                            dp[i][j][k] = dp[i - 1][j - a[i]][k] + 1;
                            cost[i][j][k] = cost[i - 1][j - a[i]][k] + a[i];
                        }
                        else if (dp[i - 1][j - a[i]][k] + 1 == dp[i][j][k]) {
                            cost[i][j][k] = Math.min(cost[i][j][k], cost[i - 1][j - a[i]][k] + a[i]);
                        }
                    }
                    // 拿优惠券买
                    if (j - b[i] >= 0 && k >= 1) {
                        if (dp[i - 1][j - b[i]][k - 1] + 1 > dp[i][j][k]) {
                            dp[i][j][k] = dp[i - 1][j - b[i]][k - 1] + 1;
                            cost[i][j][k] = cost[i - 1][j - b[i]][k - 1] + b[i];
                        }
                        else if (dp[i - 1][j - b[i]][k - 1] + 1 == dp[i][j][k])
                            cost[i][j][k] = Math.min(cost[i][j][k], cost[i - 1][j - b[i]][k - 1] + b[i]);
                    }
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= x; j++) {
                for(int k = 0; k <= y; k++) {
                    if (dp[i][j][k] == dp[n][x][y]) {
                        res = Math.min(res, cost[i][j][k]);
                    }
                }
            }
        }
        System.out.println(dp[n][x][y] + " " + res);
    }
}

5. 能量塔

题目描述

给定一颗 $nn$ 个节点的树，每个节点有一个能量塔，可以为距离当前点不超过给定值的点提供一点能量。问最终每个点可以获得多少能量。距离的定义是两点之间边的个数，自己也可以给自己提供能量。

输入描述

第一行一个整数 $NN$，表示节点的数量。

接下来一行 $NN$ 个以空格分开的整数，依次表示节点 $11$，节点 $22$，…，节点 $NN$ 的能量塔所能提供能量的最远距离。

接下来 $N-1N-1$ 行，每行两个整数，表示两个点之间有一条边。$1\le N\le 5001\le N\le 500$，节点上能量塔所能到达的最远距离距离不会大于 $500500$。

输出描述

一行，三个整数，以空格分开。表示 $NN$ 个点，每个点最终获得的能量。

样例

输入

3
1 1 1
1 2
2 3

输出

2 3 2

题解

对于树上的某个点，dfs 一次即可。

这里要用到邻接表存储，我们用 List 构建邻接表。

时间复杂度 $O(N^2)O(N^2)$

import java.util.*;

public class Test {

    static final int N = 510;
    static List[] g = new ArrayList[N];
    static int[] dis = new int[N], sum = new int[N]; // 距离 总和

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            dis[i] = sc.nextInt();
        }

        for(int i = 0; i < N; i++) g[i] = new ArrayList<Edge>(); // 初始化邻接表

        for (int i = 1; i < n; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            // 存边
            g[u].add(new Edge(u, v));
            g[v].add(new Edge(v, u));
        }

        for (int i = 1; i <= n; i++) {
            dfs(i, 0, dis[i]);
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(sum[i] + " ");
        }
    }

    static void dfs(int u, int fa, int d) {
        if (d < 0) return;
        sum[u]++; // 自己也算1点能量
        for (Object e : g[u]) {
            Edge ed = (Edge) e;
            if (ed.v != fa) {
                dfs(ed.v, u, d - 1); // 遍历所有能走到的地方
            }
        }
    }

    static class Edge {
        int u, v; // 两点
        public Edge(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }
}