💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

1️⃣ 枚举+贪心，比较简单

2️⃣ 非常经典的DP问题，需要维护一个前缀最大值

3️⃣ DFS，难点主要是读入需要处理 + (原题未给数据范围)

4️⃣ 大模拟，有点像华子出的阅读理解+模拟题 (原题未给数据范围)

🍡 01.魔法糖果工厂

题目描述

LYA 是一家魔法糖果工厂的新任管理员。工厂生产的魔法糖果有七种颜色，分别用字母 a、b、c、d、e、f、g 表示。这些糖果被排列在一条传送带上，准备进行包装。

为了提高效率，工厂引进了一台智能包装机器人。这个机器人可以按照预设的指令序列来包装糖果。指令序列由字符 a、b、c、d、e、f、g 和 * 组成。其中，a 到 g 表示机器人可以包装对应颜色的糖果，而 * 则表示机器人可以重复前一个动作任意次（包括 0 次）。

如果指令序列执行完毕，或者遇到当前无法匹配的糖果，机器人就会停止工作。LYA 想知道，按照给定的指令序列，机器人最多能包装多少个糖果。

输入格式

第一行输入一个字符串，表示传送带上 个糖果的颜色序列，长度 不超过 1000。

第二行输入一个字符串，表示机器人的指令序列 ， 的长度不超过 1000。

输出格式

输出一个整数，表示机器人最多可以包装的糖果数量。

样例输入

abbbbcdefg
ab*c*d

样例输出

7

数据范围

题解

贪心+模拟

每次遇到 '*' 或者 相同的字母就往后进行匹配，否则直接break

参考代码

• Python

def pack_candies(candy_seq, cmd_seq):
    """
    计算机器人能包装的最大糖果数量
    
    :param candy_seq: 糖果序列
    :param cmd_seq: 命令序列
    :return: 包装的糖果数量
    """
    n, m = len(candy_seq), len(cmd_seq)
    candy_idx, cmd_idx, packed = 0, 0, 0

    # 遍历糖果序列和命令序列
    while candy_idx < n and cmd_idx < m:
        if cmd_seq[cmd_idx] == '*':
            # 如果 '*' 是第一个命令，直接返回
            if cmd_idx == 0:
                return packed
            
            # 获取前一个命令
            prev_cmd = cmd_seq[cmd_idx - 1]
            
            # 重复执行前一个命令，直到遇到不匹配的糖果
            while candy_idx < n and candy_seq[candy_idx] == prev_cmd:
                packed += 1
                candy_idx += 1
            cmd_idx += 1
        elif candy_seq[candy_idx] == cmd_seq[cmd_idx]:
            # 如果当前糖果匹配当前命令
            packed += 1
            candy_idx += 1
            cmd_idx += 1
        else:
            # 如果不匹配，移动到下一个命令
            cmd_idx += 1
            # 如果下一个命令不是 '*'，跳过这个命令
            if cmd_idx < m and cmd_seq[cmd_idx] != '*':
                continue

    return packed

# 读取输入
candy_seq = input()
cmd_seq = input()

# 计算并输出结果
print(pack_candies(candy_seq, cmd_seq))

• Java

import java.util.Scanner;

public class CandyPacking {
    // 计算机器人能包装的最大糖果数量
    public static int packCandies(String candySeq, String cmdSeq) {
        int n = candySeq.length(), m = cmdSeq.length();
        int candyIdx = 0, cmdIdx = 0, packed = 0;

        // 遍历糖果序列和命令序列
        while (candyIdx < n && cmdIdx < m) {
            if (cmdSeq.charAt(cmdIdx) == '*') {
                // 如果 '*' 是第一个命令，直接返回
                if (cmdIdx == 0) return packed;
                
                // 获取前一个命令
                char prevCmd = cmdSeq.charAt(cmdIdx - 1);
                
                // 重复执行前一个命令，直到遇到不匹配的糖果
                while (candyIdx < n && candySeq.charAt(candyIdx) == prevCmd) {
                    packed++;
                    candyIdx++;
                }
                cmdIdx++;
            } else if (candySeq.charAt(candyIdx) == cmdSeq.charAt(cmdIdx)) {
                // 如果当前糖果匹配当前命令
                packed++;
                candyIdx++;
                cmdIdx++;
            } else {
                // 如果不匹配，移动到下一个命令
                cmdIdx++;
                // 如果下一个命令不是 '*'，跳过这个命令
                if (cmdIdx < m && cmdSeq.charAt(cmdIdx) != '*') continue;
            }
        }

        return packed;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        String candySeq = scanner.nextLine();
        String cmdSeq = scanner.nextLine();
        
        // 计算并输出结果
        System.out.println(packCandies(candySeq, cmdSeq));
        
        // 关闭 Scanner
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <string>
using namespace std;

// 计算机器人能包装的最大糖果数量
int pack_candies(const string& candy_seq, const string& cmd_seq) {
    int n = candy_seq.length(), m = cmd_seq.length();
    int candy_idx = 0, cmd_idx = 0, packed = 0;

    // 遍历糖果序列和命令序列
    while (candy_idx < n && cmd_idx < m) {
        if (cmd_seq[cmd_idx] == '*') {
            // 如果 '*' 是第一个命令，直接返回
            if (cmd_idx == 0) return packed;
            
            // 获取前一个命令
            char prev_cmd = cmd_seq[cmd_idx - 1];
            
            // 重复执行前一个命令，直到遇到不匹配的糖果
            while (candy_idx < n && candy_seq[candy_idx] == prev_cmd) {
                packed++;
                candy_idx++;
            }
            cmd_idx++;
        } else if (candy_seq[candy_idx] == cmd_seq[cmd_idx]) {
            // 如果当前糖果匹配当前命令
            packed++;
            candy_idx++;
            cmd_idx++;
        } else {
            // 如果不匹配，移动到下一个命令
            cmd_idx++;
            // 如果下一个命令不是 '*'，跳过这个命令
            if (cmd_idx < m && cmd_seq[cmd_idx] != '*') continue;
        }
    }

    return packed;
}

int main() {
    string candy_seq, cmd_seq;
    
    // 读取输入
    cin >> candy_seq >> cmd_seq;
    
    // 计算并输出结果
    cout << pack_candies(candy_seq, cmd_seq) << endl;
    return 0;
}

⚡️ 02.魔法珠宝展览会

问题描述

LYA 是一位著名的魔法珠宝设计师，她正在筹备一场盛大的魔法珠宝展览会。展览会上有 件珠宝作品，每件作品都有一个独特的魔法能量值。为了让展览更有趣，LYA 决定从这些作品中挑选一些进行特别展示。

然而，魔法珠宝之间会相互影响，所以 LYA 必须遵守一个特殊规则：相邻展示的两件珠宝在原始排列中的位置间隔不能小于 。LYA 希望挑选出的珠宝的魔法能量值之和最大，同时保持它们在原始排列中的相对顺序不变。

输入格式

第一行包含两个整数 和 ，分别表示珠宝的总数和最小位置间隔。

第二行包含 个整数，表示每件珠宝的魔法能量值。

输出格式

输出一个整数，表示满足条件的最大魔法能量值之和。

样例输入

5 2
3 2 5 10 7

样例输出

15

样例解释

在这个例子中，共有 5 件魔法珠宝，它们的魔法能量值分别为 3、2、5、10 和 7。最小位置间隔 为 2。最优的选择方案是：

1. 选择第 1 件珠宝（能量值为 3）
2. 选择第 3 件珠宝（能量值为 5）
3. 选择第 5 件珠宝（能量值为 7）

这个选择满足了位置间隔不小于 2 的要求，并且保持了原始顺序。选中珠宝的魔法能量值之和为 3 + 5 + 7 = 15，这是所有可能选择中的最大值。

注意，虽然第 4 件珠宝的能量值（10）是最大的，但由于间隔限制，我们不能同时选择它和第 5 件珠宝。选择 3、5、7 的组合能够得到更大的总和。

数据范围

• 
• 
• 魔法能量值

题解

本题可以使用动态规划解决。

定义 为考虑选第 件珠宝时的最大魔法能量值和。

状态转移方程为 。

维护前 个状态的最大值，

可以将时间复杂度优化到 。空间复杂度为 。

参考代码

• Python

# 读取输入
n, k = map(int, input().split())
values = list(map(int, input().split()))

# 初始化动态规划数组
dp = [0] * (n + 1)
max_sum = 0
max_prev = 0

# 动态规划过程
for i in range(n):
    # 更新当前状态
    if i >= k:
        max_prev = max(max_prev, dp[i - k])
    dp[i] = max(dp[i], max_prev + values[i])
    
    # 更新全局最大值
    max_sum = max(max_sum, dp[i])

# 输出结果
print(max_sum)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = scanner.nextInt();
        }
        
        // 初始化动态规划数组
        int[] dp = new int[n + 1];
        int maxSum = 0;
        int maxPrev = 0;
        
        // 动态规划过程
        for (int i = 0; i < n; i++) {
            // 更新当前状态
            if (i >= k) {
                maxPrev = Math.max(maxPrev, dp[i - k]);
            }
            dp[i] = Math.max(dp[i], maxPrev + values[i]);
            
            // 更新全局最大值
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        // 输出结果
        System.out.println(maxSum);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    // 读取魔法能量值
    vector<int> values(n);
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }
    
    // 初始化动态规划数组
    vector<int> dp(n + 1, 0);
    int max_sum = 0;
    int max_prev = 0;
    
    // 动态规划过程
    for (int i = 0; i < n; i++) {
        // 更新当前状态
        if (i >= k) {
            max_prev = max(max_prev, dp[i - k]);
        }
        dp[i] = max(dp[i], max_prev + values[i]);
        
        // 更新全局最大值
        max_sum = max(max_sum, dp[i]);
    }
    
    // 输出结果
    cout << max_sum << endl;
    
    return 0;
}

🍇 03.旅行规划师

问题描述

K小姐是一位热爱旅行的摄影师。她计划进行一次精彩的摄影之旅，并希望从众多景点中选择最佳组合。为了做出明智的选择，她对每个景点进行了详细评估，考虑了以下因素：

• 体力消耗（）：拍摄和探索景点所需的体力。
• 灵感值（）：景点能激发的创作灵感。
• 位置（）：景点的地理坐标，以K小姐的家（）为原点。

从一个景点到另一个景点的体力消耗计算方式为：。

K小姐想从个景点中选择个进行拍摄。她的旅程将从家出发，依次游览这个景点，最后返回家。旅程的舒适度定义为：总灵感值（）除以总体力消耗（）。

• ：所有景点的体力消耗之和，加上旅途中的体力消耗。
• ：所有景点的灵感值之和。

请帮助K小姐规划出舒适度最高的旅行路线。

输入格式

第一行输入两个整数 和 ，用空格分隔，分别表示景点总数和计划游览的景点数量。保证 。

接下来的 行，每行包含四个数值 、、 和 ，用空格分隔。其中 和 为整数， 为景点坐标。

输出格式

输出一个小数，表示最优旅行路线的舒适度，保留6位小数。

样例输入

3 2
6 20 10 15
-5 10 30 27
-15 10 20 25

样例输出

0.370370

样例解释

最优旅行路线为：(0, 0) -> (10, 15) -> (20, 25) -> (0, 0) 或 (0, 0) -> (20, 25) -> (10, 15) -> (0, 0) 计算得出 , ，最终舒适度为 。

数据范围

题解

本题可以使用深度优先搜索（DFS）来解决。

本质就是从 个数中有顺序的选出 个

时间复杂度为O(t!/(t-k)!)，空间复杂度为O(t)。

参考代码

• Python

# 导入所需的模块
import sys
from itertools import permutations

# 读取输入
t, k = map(int, input().split())
spots = []
for _ in range(t):
    m, n, x, y = map(int, input().replace('(', '').replace(')', '').split())
    spots.append((m, n, x, y))

# 计算两点之间的距离
def distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

# 计算路径的舒适度
def comfort(path):
    cm = sum(spots[i][0] for i in path)  # 体力消耗
    cn = sum(spots[i][1] for i in path)  # 灵感值
    cm += distance(0, 0, spots[path[0]][2], spots[path[0]][3])  # 从家到第一个景点
    cm += distance(0, 0, spots[path[-1]][2], spots[path[-1]][3])  # 从最后一个景点回家
    for i in range(len(path) - 1):
        cm += distance(spots[path[i]][2], spots[path[i]][3], spots[path[i+1]][2], spots[path[i+1]][3])
    return cn / cm if cm != 0 else 0

# 主函数
def solve():
    max_comfort = 0
    for path in permutations(range(t), k):
        max_comfort = max(max_comfort, comfort(path))
    return max_comfort

# 输出结果
print(f"{solve():.6f}")

• Java

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

public class Main {
    static int t, k;
    static int[][] spots;
    static double maxComfort = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));