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

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

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

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

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

🍰 本次题目难度中等偏上，但对米哈游自身来说还算是简单的一场。 🧩 第一题是一个分类讨论，第二题分析后发现数据范围很小可以 暴力，第三题是一个基环树上的博弈问题，结论比较容易猜

🎤 01.LYA的花园改造计划

问题描述

LYA是一位园艺爱好者，她有一个长方形的花园，花园里种植了 种不同的花卉。每种花卉都有一个独特的芳香值，第 种花卉的芳香值为 。LYA发现，当两种花卉相邻种植时，它们会产生一种特殊的香气融合效果，这种效果的强度等于两种花卉芳香值的乘积。

为了让花园的香气更加迷人，LYA决定对花园进行一次小规模改造。她可以选择交换任意两种相邻的花卉的位置（必须进行一次交换）。LYA想知道，通过这次改造，她最多能将花园的香气融合效果提升到多少？

花园的香气融合效果定义为所有相邻花卉香气融合强度的最大值。例如，如果花园中有四种花卉，它们的芳香值分别是 ，那么相邻花卉的香气融合强度分别是 、 和 ，因此花园的香气融合效果为 。

输入格式

第一行输入一个整数 ，表示花卉的种类数。

第二行输入 个整数 ，表示每种花卉的芳香值。

输出格式

输出一个整数，表示经过一次相邻花卉交换后，花园可能达到的最大香气融合效果。

样例输入

3
3 1 10

样例输出

30

数据范围

题解

首先计算原始花园布局的最大香气融合效果。

然后，考虑所有可能的相邻花卉交换：

• 对于每一对相邻的花卉，尝试交换它们。
• 交换后，需要重新计算受影响的香气融合强度。
• 更新最大香气融合效果。

在所有可能的交换中，找出能产生最大香气融合效果的交换。

关键点在于，交换两个相邻的花卉只会影响三个位置的香气融合强度：被交换的两个花卉之间的强度，以及它们与各自相邻的另一个花卉之间的强度。

时间复杂度分析：我们只需要遍历一次数组，对每对相邻的花卉进行一次交换尝试，因此总的时间复杂度为 。

参考代码

• Python

def solve(n, flowers):
    # 计算初始的最大香气融合效果
    max_effect = max(flowers[i] * flowers[i+1] for i in range(n-1))
    
    # 尝试交换每一对相邻的花卉
    for i in range(n-1):
        new_effect = max_effect
        
        # 计算交换后的新效果
        if i > 0:
            new_effect = max(new_effect, flowers[i-1] * flowers[i+1])
        if i < n-2:
            new_effect = max(new_effect, flowers[i] * flowers[i+2])
        
        new_effect = max(new_effect, flowers[i+1] * flowers[i])
        
        # 更新最大效果
        max_effect = max(max_effect, new_effect)
    
    return max_effect

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

# 计算并输出结果
result = solve(n, flowers)
print(result)

• 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[] flowers = new int[n];
        
        for (int i = 0; i < n; i++) {
            flowers[i] = scanner.nextInt();
        }
        
        System.out.println(solve(n, flowers));
    }
    
    public static int solve(int n, int[] flowers) {
        // 计算初始的最大香气融合效果
        int maxEffect = 0;
        for (int i = 0; i < n - 1; i++) {
            maxEffect = Math.max(maxEffect, flowers[i] * flowers[i+1]);
        }
        
        // 尝试交换每一对相邻的花卉
        for (int i = 0; i < n - 1; i++) {
            int newEffect = maxEffect;
            
            // 计算交换后的新效果
            if (i > 0) {
                newEffect = Math.max(newEffect, flowers[i-1] * flowers[i+1]);
            }
            if (i < n - 2) {
                newEffect = Math.max(newEffect, flowers[i] * flowers[i+2]);
            }
            
            newEffect = Math.max(newEffect, flowers[i+1] * flowers[i]);
            
            // 更新最大效果
            maxEffect = Math.max(maxEffect, newEffect);
        }
        
        return maxEffect;
    }
}

• Cpp

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

using namespace std;

int solve(int n, vector<int>& flowers) {
    // 计算初始的最大香气融合效果
    int max_effect = 0;
    for (int i = 0; i < n - 1; ++i) {
        max_effect = max(max_effect, flowers[i] * flowers[i+1]);
    }
    
    // 尝试交换每一对相邻的花卉
    for (int i = 0; i < n - 1; ++i) {
        int new_effect = max_effect;
        
        // 计算交换后的新效果
        if (i > 0) {
            new_effect = max(new_effect, flowers[i-1] * flowers[i+1]);
        }
        if (i < n - 2) {
            new_effect = max(new_effect, flowers[i] * flowers[i+2]);
        }
        
        new_effect = max(new_effect, flowers[i+1] * flowers[i]);
        
        // 更新最大效果
        max_effect = max(max_effect, new_effect);
    }
    
    return max_effect;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> flowers(n);
    for (int i = 0; i < n; ++i) {
        cin >> flowers[i];
    }
    
    cout << solve(n, flowers) << endl;
    
    return 0;
}

🌵 02.艺术品收藏家的难题

问题描述

LYA是一位热爱收藏的艺术品爱好者。她最近获得了一次参加拍卖会的机会，拍卖会上有 件艺术品供人竞拍。每件艺术品都有其独特的价值 和体积 。LYA带来了一个容量为 的特制收藏箱，她希望能够将尽可能多的艺术品装入其中，但总体积不能超过箱子的容量。

然而，LYA发现某些艺术品之间存在冲突，不能同时收藏。比如，一幅描绘和平的油画与一件展示战争场景的雕塑放在一起可能会产生不和谐的感觉。因此，她列出了 组互斥关系，每组关系用两个数字 和 表示，意味着编号为 的艺术品和编号为 的艺术品不能同时收藏。

现在，LYA希望你能帮她计算出在满足所有条件的情况下，她能够收藏的艺术品的最大总价值。

输入格式

第一行输入三个整数 、 和 （；；），分别表示艺术品的数量、收藏箱的容量和互斥关系的数量。

接下来的 行，每行输入两个整数 和 （），表示每件艺术品的体积和价值。

最后 行，每行输入两个整数 和 （，），描述一组互斥关系。

输出格式

输出一个整数，表示LYA能够收藏的艺术品的最大总价值。

样例输入

3 100 2
15 19
20 30
15 19
1 2
2 3

样例输出

38

数据范围

题解

本题是一个带有互斥约束的0-1背包问题的变种。由于艺术品数量较少（），我们可以直接二进制枚举。

1. 使用一个整数的二进制表示来表示选择的艺术品组合。例如，对于3件艺术品，101表示选择了第1件和第3件。

2. 遍历所有可能的组合（ 种），对于每种组合：

   • 检查是否满足容量限制
   • 检查是否满足互斥关系
   • 如果满足所有条件，计算当前组合的总价值

3. 在所有有效组合中找出最大总价值

时间复杂度：，其中 是艺术品数量， 是互斥关系数量。

虽然这个复杂度看起来很高，但由于 ，实际运行时间是可以接受的。

参考代码

• Python

def max_value(n, m, k, items, conflicts):
    """
    计算能够收藏的艺术品的最大总价值
    
    参数:
    n: 艺术品数量
    m: 收藏箱容量
    k: 互斥关系数量
    items: 艺术品列表，每个元素是(体积, 价值)的元组
    conflicts: 互斥关系列表，每个元素是(a, b)表示a和b互斥
    
    返回:
    最大总价值
    """
    def is_valid(comb):
        """检查组合是否满足互斥关系"""
        for a, b in conflicts:
            if (comb & (1 << (a - 1))) and (comb & (1 << (b - 1))):
                return False
        return True

    max_val = 0
    # 遍历所有可能的组合
    for i in range(1, 1 << n):
        weight = sum(items[j][0] for j in range(n) if i & (1 << j))
        if weight <= m and is_valid(i):
            value = sum(items[j][1] for j in range(n) if i & (1 << j))
            max_val = max(max_val, value)

    return max_val

# 读取输入
n, m, k = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
conflicts = [tuple(map(int, input().split())) for _ in range(k)]

# 计算并输出结果
print(max_value(n, m, k, items, conflicts))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        int k = sc.nextInt();

        // 读取艺术品信息
        long[][] items = new long[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = sc.nextLong(); // 体积
            items[i][1] = sc.nextLong(); // 价值
        }

        // 读取互斥关系