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

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

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

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

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

🍖 本次题目难度中等偏上，最后一题又是笔试常驻嘉宾树形DP

1️⃣ 第一题其实是个诈骗题，发现图其实都不需要读入，本质是一个 置换环

2️⃣ 第二题比较签到是个简单的 字符串处理

3️⃣ 第三题是笔试常驻嘉宾 树形DP，建议大家好好练练，树形DP属于会者不难，难者不会的这一类。

📃 01.图书馆整理

问题描述

K小姐是一位图书馆管理员。最近，她发现图书馆的书架上的书籍编号出现了混乱。每本书都有一个独特的编号，理想情况下，这个编号应该与书在书架上的位置相对应。为了恢复秩序，K小姐决定通过交换书籍的位置来使每本书的编号与其位置相匹配。

她想知道最少需要多少次交换才能完成这项任务。由于图书馆的布局比较特殊，书架之间的连接形成了一棵树的结构。K小姐可以在任意两个位置之间交换书籍，不受书架连接的限制。

请帮助K小姐计算出完成整理任务所需的最少交换次数。

输入格式

第一行输入一个正整数 ，表示图书馆中的书籍总数。

第二行输入 个正整数 ，第 个数字表示位置 上书籍的编号，这 个数互不相同。

接下来的 行，每行输入两个正整数 和 ，表示书架 和书架 之间有一条通道相连。

输出格式

输出一个整数，表示最少需要的交换次数。

样例输入

4
2 1 4 3
1 2
2 3
2 4

样例输出

2

数据范围

题解

这个问题可以通过计算置换环的方法来解决。虽然题目描述了一个树形结构的图书馆布局，但实际上我们只需要关注书籍的编号和它们当前的位置。

关键思路如下：

1. 对于每个位置，我们检查该位置上的书籍编号是否与位置匹配。
2. 如果不匹配，我们跟踪这个"错误放置"的链条，直到找到一个循环。
3. 每个这样的循环就是一个置换环。
4. 对于长度为 的置换环，需要 次交换才能使其中的所有书籍回到正确位置。
5. 总的交换次数是所有置换环所需交换次数的总和。

这种方法之所以有效，是因为：

• 每次交换都能至少让一本书回到正确位置。
• 置换环方法保证了我们使用最少的交换次数。

时间复杂度：，其中 是书籍的数量。 空间复杂度：，用于存储访问标记。

参考代码

• Python

def min_swaps(n, books):
    swaps = 0
    visited = [False] * (n + 1)
    
    for i in range(1, n + 1):
        if not visited[i]:
            cycle_size = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = books[j]
                cycle_size += 1
            swaps += cycle_size - 1
    
    return swaps

# 读取输入
n = int(input())
books = [0] + list(map(int, input().split()))

# 读取书架连接信息（本题解法中不需要使用）
for _ in range(n - 1):
    u, v = map(int, input().split())

# 计算并输出结果
result = min_swaps(n, books)
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[] books = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            books[i] = scanner.nextInt();
        }
        
        // 读取书架连接信息（本题解法中不需要使用）
        for (int i = 0; i < n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
        }
        
        System.out.println(minSwaps(n, books));
    }
    
    public static int minSwaps(int n, int[] books) {
        int swaps = 0;
        boolean[] visited = new boolean[n + 1];
        
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                int cycleSize = 0;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = books[j];
                    cycleSize++;
                }
                swaps += cycleSize - 1;
            }
        }
        
        return swaps;
    }
}

• Cpp

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

int minSwaps(int n, vector<int>& books) {
    int swaps = 0;
    vector<bool> visited(n + 1, false);
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int cycleSize = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = books[j];
                cycleSize++;
            }
            swaps += cycleSize - 1;
        }
    }
    
    return swaps;
}

int main() {
    int n;
    cin >> n;
    vector<int> books(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> books[i];
    }
    
    // 读取书架连接信息（本题解法中不需要使用）
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
    }
    
    cout << minSwaps(n, books) << endl;
    return 0;
}

🕐 02.LYA的时区转换

问题描述

LYA 是一家时尚杂志的编辑，她每天都需要处理大量的时区转换问题，因为她要与全球各地的摄影师和模特沟通。她所在的城市位于东八区(UTC/GMT+08:00)，而她经常需要与位于世界协调时间(UTC)时区的合作伙伴联系。为了提高工作效率，LYA 决定开发一个简单的程序来帮助她快速进行时间转换。

输入格式

第一行输入一个整数 （），表示需要转换的时间数量。 接下来的 行，每行输入一个格式为"小时:分钟"的东八区时间（24小时制）。

输出格式

对于每一组输入的东八区时间，输出一行对应的世界协调时间（UTC）。 注意：输出的小时和分钟都应当补0至两位数。

样例输入

2
8:30
00:00

样例输出

00:30
16:00

数据范围

• 
• 输入的时间格式保证合法，小时在 0 到 23 之间，分钟在 0 到 59 之间。

题解

这道题目要求我们将东八区（北京时间）转换为世界协调时间（UTC）。由于东八区比UTC快8小时，我们需要将输入的时间减去8小时。主要需要注意以下几点：

1. 如果减去8小时后时间变为负数，需要加上24小时来调整。
2. 输出时需要保证小时和分钟都是两位数，不足两位需要在前面补0。

具体解题步骤

1. 读取输入的时间，将其转换为分钟数。
2. 减去8小时（480分钟），如果结果为负，加上24小时（1440分钟）。
3. 将结果转换回小时和分钟，并格式化输出。

时间复杂度：O(T)，其中T是需要转换的时间数量。 空间复杂度：O(1)，只使用了常数级的额外空间。

参考代码

• Python

def convert_to_utc(beijing_time):
    # 将北京时间转换为UTC时间
    hours, minutes = map(int, beijing_time.split(':'))
    total_minutes = hours * 60 + minutes
    utc_minutes = (total_minutes - 480) % 1440  # 减去8小时（480分钟），取模处理跨日情况
    utc_hours, utc_minutes = divmod(utc_minutes, 60)
    return f"{utc_hours:02d}:{utc_minutes:02d}"

# 读取测试用例数量
T = int(input())

# 处理每个测试用例
for _ in range(T):
    beijing_time = input().strip()
    utc_time = convert_to_utc(beijing_time)
    print(utc_time)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner