✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

滴滴2

题目一：工具切换优化

1️⃣：使用动态规划记录两种工具组合状态下的最小时间

2️⃣：对每个任务考虑直接完成或切换组合后完成的成本

3️⃣：状态转移方程计算最优解

难度：中等

这道题目的核心在于理解工具组合的状态切换问题。通过将问题建模为两个状态间的动态规划，我们可以高效地计算出完成所有任务的最小时间。关键是要识别出每种状态下完成不同类型任务的成本，并正确处理状态间的转换。

题目二：资源收集计划

1️⃣：识别层次容量约束，半径≤R的设备总数不能超过4R(R+1)

2️⃣：使用Fenwick树维护每个半径的设备使用情况

3️⃣：贪心选择最低成本设备，同时满足容量约束

难度：中等

这道题目将网格布局问题抽象为带层次容量约束的贪心问题。关键在于理解切比雪夫距离的容量限制：所有半径≤R的设备必须放在距离目标≤R的区域内，该区域最多容纳4R(R+1)个设备。通过Fenwick树高效维护容量使用情况，结合贪心策略选择最优方案。

01. 工具切换优化

问题描述

小兰是一名高效的工程师，她需要完成 项连续的工程任务。每项任务都需要使用特定类型的工具：要么需要精密工具（用 'P' 表示），要么需要通用工具（用 'G' 表示）。

小兰有两套工具组合可以选择：

• 组合A：左手持精密工具，右手持通用工具
• 组合B：左手持通用工具，右手持精密工具

初始时，小兰使用组合A。她需要按照从第 项到第 项的顺序依次完成所有任务。

对于每项任务，小兰有以下选择：

• 使用左手工具完成任务，耗时 秒
• 使用右手工具完成任务，耗时 秒
• 花费 秒切换到另一套工具组合，然后使用相应的手完成任务

请计算小兰完成所有任务所需的最少时间。

输入格式

第一行包含一个正整数 ，表示任务的总数。

第二行包含一个长度为 的字符串 （仅包含字符 'P' 和 'G'），其中第 个字符 为 'P' 表示第 项任务需要精密工具，'G' 表示需要通用工具。

第三行包含三个用空格分隔的正整数 , , ，分别表示使用左手工具的时间、使用右手工具的时间，以及切换工具组合的时间。

输出格式

输出一行，包含一个整数，表示小兰完成所有任务所需的最少时间。

样例输入

3
PPG
3 4 1

7
GGPPGGG
4 3 1

样例输出

10

23

数据范围

• 
• 

样例	解释说明
样例1	初始状态为组合A（左精密，右通用）。可以用左手完成前两个P任务（耗时 ），然后用右手完成G任务（耗时4），总时间10秒。也可以用左手完成前两个P任务后切换组合再用左手（现在是通用工具）完成G任务，总时间 秒。
样例2	初始用右手完成两个G任务（），切换组合用右手（现在是精密）完成两个P任务（），再切换回来用右手完成剩余G任务（），总时间 秒。

题解

这道题的核心在于理解工具组合的状态转换。我们可以用动态规划来解决这个问题。

设定两个状态：

• 状态0：组合A（左手精密工具，右手通用工具）
• 状态1：组合B（左手通用工具，右手精密工具）

用 dp[0] 和 dp[1] 分别表示处于状态0和状态1时完成当前任务的最小时间。

对于每个任务，我们需要考虑：

1. 在当前状态下直接完成任务
2. 先切换状态再完成任务

状态转移方程：

• next0 = min(dp[0], dp[1] + c) + cost0
• next1 = min(dp[1], dp[0] + c) + cost1

其中：

• cost0 是在状态0下完成当前任务的时间
• cost1 是在状态1下完成当前任务的时间

具体来说：

• 在状态0下，'P'任务用左手（时间a），'G'任务用右手（时间b）
• 在状态1下，'G'任务用左手（时间a），'P'任务用右手（时间b）

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    s = input()
    a, b, c = map(int, input().split())
    
    # dp[0]: 状态A的最小时间，dp[1]: 状态B的最小时间
    dp = [0, c]  # 初始状态A，或切换到状态B
    
    for ch in s:
        # 状态A下的成本：P用左手(a)，G用右手(b)
        cost_a = a if ch == 'P' else b
        # 状态B下的成本：G用左手(a)，P用右手(b)  
        cost_b = a if ch == 'G' else b
        
        # 计算转移到状态A和B的最小时间
        new_a = min(dp[0], dp[1] + c) + cost_a
        new_b = min(dp[1], dp[0] + c) + cost_b
        
        dp[0], dp[1] = new_a, new_b
    
    print(min(dp))

solve()

Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    long long a, b, c;
    cin >> a >> b >> c;
    
    // dp[0]: 组合A的最小时间, dp[1]: 组合B的最小时间
    vector<long long> dp = {0, c}; // 初始或切换到B
    
    for (char ch : s) {
        // 组合A: P用左手(a), G用右手(b)
        long long cost_a = (ch == 'P') ? a : b;
        // 组合B: G用左手(a), P用右手(b)
        long long cost_b = (ch == 'G') ? a : b;
        
        // 状态转移
        long long new_a = min(dp[0], dp[1] + c) + cost_a;
        long long new_b = min(dp[1], dp[0] + c) + cost_b;
        
        dp[0] = new_a;
        dp[1] = new_b;
    }
    
    cout << min(dp[0], dp[1]) << "\n";
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        String s = sc.next();
        long a = sc.nextLong();
        long b = sc.nextLong(); 
        long c = sc.nextLong();
        
        // dpA: 组合A的最小时间, dpB: 组合B的最小时间
        long dpA = 0, dpB = c; // 初始状态A，或切换到B
        
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            
            // 组合A下的成本：P任务用左手(a)，G任务用右手(b)
            long costA = (ch == 'P') ? a : b;
            // 组合B下的成本：G任务用左手(a)，P任务用右手(b)
            long costB = (ch == 'G') ? a : b;
            
            // 状态转移
            long newA = Math.min(dpA, dpB + c) + costA;
            long newB = Math.min(dpB, dpA + c) + costB;
            
            dpA = newA;
            dpB = newB;
        }
        
        System.out.println(Math.min(dpA, dpB));
        sc.close();
    }
}

02. 资源收集计划

问题描述

小毛正在管理一个大型资源收集项