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

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

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

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

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

1️⃣ 考虑贡献法，对于每个出现一次的考虑向左或者向右扩展

2️⃣ 非常经典的DP问题

3️⃣ 前缀和+模拟，比美团那道压轴简单许多

4️⃣ DFS+贪心，比较容易想

🍉 01.特殊调酒师

问题描述

LYA 是一位著名的调酒师，她最近发明了一种特殊的鸡尾酒。这种鸡尾酒有以下特点：

1. 至少由 3 种酒水组成。
2. 只使用两种不同品牌的酒。
3. 其中一种品牌的酒恰好只使用一次。

例如，[威士忌, 威士忌, 伏特加] 和 [威士忌, 伏特加, 威士忌] 都是符合要求的特殊鸡尾酒（长度为 3，只使用威士忌和伏特加两种酒，且伏特加恰好使用一次）。而 [威士忌, 伏特加]、[威士忌, 伏特加, 朗姆酒] 和 [威士忌, 威士忌, 威士忌] 都不符合要求。

LYA 有一个长度为 的酒水序列 ，她想知道这个序列中有多少个连续子序列可以调制成特殊鸡尾酒。

输入格式

第一行输入一个正整数 ，表示酒水序列的长度，。

第二行输入 个正整数 ，，表示每种酒水的编号。

输出格式

输出一个整数，表示可以调制成特殊鸡尾酒的连续子序列的数量。

样例输入1

6
1 1 4 5 1 4

样例输出1

1

样例解释1

只有 [1, 1, 4] 这个子序列可以调制成特殊鸡尾酒。

样例输入2

4 
2 2 4 2

样例输出2

3

数据范围

题解

本题的核心思路是将连续相同的酒水压缩成一组，然后遍历压缩后的数组来计算特殊鸡尾酒的数量。

我们需要考虑以下几种情况：

1. 当前组的长度为1，且前后两组的酒水相同。
2. 其他情况下，可以将当前组作为特殊酒水，与前后组组合。

算法步骤如下：

1. 压缩输入数组，将连续相同的酒水记为一组。
2. 遍历压缩后的数组，根据不同情况计算特殊鸡尾酒的数量。
3. 特别处理边界情况，如只有一种酒水的情况。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

def solve():
    # 读取输入
    n = int(input())
    a = list(map(int, input().split()))
    
    # 压缩数组
    v = []
    cnt = 1
    for i in range(1, n):
        if a[i] != a[i - 1]:
            v.append([cnt, a[i - 1]])
            cnt = 1
        else:
            cnt += 1
    v.append([cnt, a[-1]])
    
    m = len(v)
    res = 0
    
    # 处理只有一种酒水的情况
    if m == 1:
        print(0)
        return
    
    # 计算特殊鸡尾酒的数量 即 第一组选一个，最后一组选一个的情况
    res += v[m - 2][0] - 1  # 倒数第二组
    res += v[1][0] - 1  # 第二组
    
    for i in range(1, m - 1):
        l, r = v[i - 1][1], v[i + 1][1]
        lcnt, rcnt = v[i - 1][0], v[i + 1][0]
        cur_cnt = v[i][0]
        
        if cur_cnt == 1 and l == r:
            # 当前组长度为1，且前后两组酒水相同
            res += rcnt - 1 + rcnt
            if lcnt >= 2:
                res += (lcnt - 2 + 1) * (rcnt + 1)
        else:
            # 其他情况
            res += lcnt - 1 + rcnt - 1
    
    print(res)

# 运行解决方案
solve()

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取输入
        int n = Integer.parseInt(br.readLine());
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        
        solve(n, a);
    }
    
    static void solve(int n, int[] a) {
        // 压缩数组，将连续相同的酒水记为一组
        List<int[]> v = new ArrayList<>();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (a[i] != a[i - 1]) {
                v.add(new int[]{cnt, a[i - 1]});
                cnt = 1;
            } else {
                cnt++;
            }
        }
        v.add(new int[]{cnt, a[n - 1]});
        
        int m = v.size();
        long res = 0;
        
        // 处理只有一种酒水的情况
        if (m == 1) {
            System.out.println(0);
            return;
        }
        
        // 计算特殊鸡尾酒的数量 即 第一组选一个，最后一组选一个的情况
        res += v.get(m - 2)[0] - 1;  // 倒数第二组
        res += v.get(1)[0] - 1;  // 第二组
        
        for (int i = 1; i < m - 1; i++) {
            int l = v.get(i - 1)[1], r = v.get(i + 1)[1];
            int lcnt = v.get(i - 1)[0], rcnt = v.get(i + 1)[0];
            int cur_cnt = v.get(i)[0];
            
            if (cur_cnt == 1 && l == r) {
                // 当前组长度为1，且前后两组酒水相同
                res += rcnt - 1 + rcnt;
                if (lcnt >= 2) {
                    res += (long)(lcnt - 2 + 1) * (rcnt + 1);
                }
            } else {
                // 其他情况
                res += lcnt - 1 + rcnt - 1;
            }
        }
        
        // 输出结果
        System.out.println(res);
    }
}

• Cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& i : a) cin >> i;
    
    // 压缩数组
    vector<array<int, 2>> v;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            v.push_back({cnt, a[i - 1]});
            cnt = 1;
        } else {
            cnt++;
        }
    }
    v.push_back({cnt, a.back()});
    
    int m = v.size();
    LL res = 0;
    
    // 处理只有一种酒水的情况
    if (m == 1) {
        cout << 0 << "\n";
        return;
    }
    
    // 计算特殊鸡尾酒的数量 即 第一组选一个，最后一组选一个的情况
    res += v[m - 2][0] - 1;  // 倒数第二组
    res += v[1][0] - 1;  // 第二组
    
    for (int i = 1; i < m - 1; i++) {
        int l = v[i - 1][1], r = v[i + 1][1];
        int lcnt = v[i - 1][0], rcnt = v[i + 1][0];
        int cur_cnt = v[i][0];
        
        if (cur_cnt == 1 && l == r) {
            // 当前组长度为1，且前后两组酒水相同
            res += rcnt - 1 + rcnt;
            if (lcnt >= 2) {
                res += (lcnt - 2 + 1LL) * (rcnt + 1);
            }
        } else {
            // 其他情况
            res += lcnt - 1 + rcnt - 1;
        }
    }
    
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

🥮 02.LYA的咖啡店经营

问题描述

LYA 开了一家咖啡店，她每天面临 个经营决策。每个决策都有两个选项：

1. 使用 包咖啡豆，制作特色咖啡获得 元利润。
2. 从供应商那里购入 包咖啡豆。

然而，咖啡店的储藏室容量有限，最多只能存放 包咖啡豆。如果购入的咖啡豆超过储藏室容量，多余的部分将会变质无法使用。

在所有决策结束后，剩余的每包咖啡豆可以以 1 元的价格出售给其他咖啡店。

LYA 想知道在最优决策下，她最多能获得多少利润。

输入格式

第一行输入两个整数 和 ，，分别表示决策次数和储藏室容量。

接下来 行，每行输入三个整数 、 和 ，，表示每个决策的相关数据。

输出格式

输出一个整数，表示最大可能获得的利润。

样例输入

3 3
1 2 1
1 3 1
1 2 4

样例输出

6

样例解释

最优决策如下：

1. 选择选项 2，购入 1 包咖啡豆。
2. 选择选项 1，使用 1 包咖啡豆制作特色咖啡，获得 3 元利润。
3. 选择选项 2，购入 4 包咖啡豆，但由于储藏室容量限制，实际只能存放 3 包。

最后，将剩余的 3 包咖啡豆以每包 1 元的价格出售。

总利润为：3（第二次决策）+ 3（出售剩余咖啡豆）= 6 元。

数据范围

• 
• 

题解

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

定义 为前 个决策后，拥有 包咖啡豆时的最大利润。

状态转移考虑两种情况：选择制作特色咖啡或购入咖啡豆。

注意处理咖啡豆数量超过储藏室容量的情况。

最终答案为 ，其中 。

时间复杂度 ，空间复杂度 。

参考代码

• Python

def solve():
    # 读取输入
    n, m = map(int, input().split())
    decisions = [list(map(int, input().split())) for _ in range(n)]
    
    # 初始化dp数组
    dp = [[-1] * (m + 1) for _ in range(n + 1)]
    
    def dfs(day, beans):
        # 基本情况：所有决策都已做出
        if day == n:
            return beans
        
        # 如果已经计算过，直接返回结果
        if dp[day][beans] != -1:
            return dp[day][beans]
        
        x, y, z = decisions[day]
        
        # 选择1：购入咖啡豆
        result = dfs(day + 1, min(m, beans + z))
        
        # 选择2：制作特色咖啡（如果有足够的咖啡豆）
        if beans >= x:
            result = max(result, dfs(day + 1, beans - x) + y)
        
        # 保存并返回结果
        dp[day][beans] = result
        return result
    
    # 输出最优结果
    print(dfs(0, 0))

# 运行解决方案
solve()

• Java

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

public class Main {
    static int n, m;
    static int[][] decisions;
    static long[][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 读取输入
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        decisions = new int[n][3];
        dp = new long[n + 1][m + 1];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                decisions[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 初始化dp数组
        for (long[] row : dp) {
            Arrays.fill(row, -1);
        }
        
        // 输出最优结果
        System.out.println(dfs(0, 0));
    }
    
    static long dfs(int day, int beans) {
        // 基本情况：所有决策都已做出
        if (day == n) return beans;
        
        // 如果已经计算过，直接返回结果
        if (dp[day][beans] != -1) return dp[day][beans];
        
        int x = decisions[day][0], y = decisions[day][1], z = decisions[day][2];
        
        // 选择1：购入咖啡豆
        long result = dfs(day + 1, Math.min(m, beans + z));
        
        // 选择2：制作特色咖啡（如果有足够的咖啡豆）
        if (beans >= x) {
            result = Math.max(result, dfs(day + 1, beans - x) + y);
        }
        
        // 保存并返回结果
        return dp[day][beans] = result;
    }
}

• Cpp

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

#define int long long

signed