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

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

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

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

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

🍥 本次难度不小，最后一题是倍增+预处理，写起来比较麻烦细节容易错，建议非竞赛选手尝试暴力骗分

1️⃣ 小学数学题，每次用最大的桶装

2️⃣ 枚举题，对于每个玩家分别暴力向左和向右拓展

3️⃣ 二分答案，这题最无脑也最容易写的做法就是二分啦，直接贪心容易出错

4️⃣ 贪心，当然也可以用DP(比较麻烦)

5️⃣ 倍增+预处理，一看就是打竞赛的人出的题，笔试中并不常见，建议非竞赛选手直接尝试暴力骗分

💧 01.K小姐的装水问题 评测链接🔗

问题描述

在一个美丽的小镇上，K小姐经营着一家水上运输公司。她有三个不同容量的桶，分别为 单位。最近，小镇的居民请求她帮助运输 单位的水到镇外的湖泊。每次运输时，K小姐可以选择使用任意一个桶装水，装满后将水送到目的地，然后返回继续装水。为了提高效率，K小姐希望知道她至少需要多少趟才能完成这个运输任务。

输入格式

第一行包含四个正整数 ，分别表示待运输的水量和三个桶的容量。

输出格式

输出一个整数，表示将 单位的水装完至少需要跑多少趟。

样例输入

4 2 2 1

样例输出

2

数据范围

题解

结论题

可以发现每次都用最大的桶装即可，最终答案为

参考代码

• Python

def min_trips(n, a, b, c):
    # 找出最大的桶容量
    max_capacity = max(a, b, c)
    # 计算所需趟数并向上取整
    trips = (n + max_capacity - 1) // max_capacity
    return trips

# 输入处理
n, a, b, c = map(int, input().split())
# 输出结果
print(min_trips(n, a, b, c))

• Java

import java.util.Scanner;

public class MinTrips {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入待运输水量和三个桶的容量
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        
        // 找出最大的桶容量
        int maxCapacity = Math.max(a, Math.max(b, c));
        // 计算所需趟数并向上取整
        int trips = (n + maxCapacity - 1) / maxCapacity;
        
        // 输出结果
        System.out.println(trips);
    }
}

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, a, b, c;
    // 输入待运输水量和三个桶的容量
    cin >> n >> a >> b >> c;
    
    // 找出最大的桶容量
    int maxCapacity = max(a, max(b, c));
    // 计算所需趟数并向上取整
    int trips = (n + maxCapacity - 1) / maxCapacity;
    
    // 输出结果
    cout << trips << endl;
    return 0;
}

✨ 02.捉迷藏游戏的胜利时间 评测链接🔗

问题描述

在一个神秘的森林中，K小姐、小蓝和小绿正在进行一场捉迷藏的游戏。他们的当前位置分别用字母表示，其他位置可能是空地（用 '*' 表示）或障碍物（用 '#' 表示）。寻找方可以每秒移动到相邻的空地，而躲藏方则无法移动。当寻找方移动到躲藏方的位置时，躲藏方就被找到，游戏结束。

在这场游戏中，K小姐、小蓝和小绿都希望能尽快找到对方。现在，我们需要计算出当他们分别作为寻找方时，能够获胜所需的最少时间。如果某个寻找方无法找到任何躲藏方，则输出 -1。

输入格式

输入包含一个仅由字符 '*'、'#'、'R'、'B'、'G' 组成的字符串 ，其中 表示 K小姐 的位置， 表示小蓝的位置， 表示小绿的位置。字符串的长度 满足 。

输出格式

输出一行，包含三个整数，分别表示 K小姐、小蓝和小绿作为寻找方时能够获胜的最少时间。如果无法获胜，则直接输出 -1。

样例输入

R***B**G

样例输出

4 3 3

数据范围

• 字符串长度 的范围为 。
• 字符 '', '', '' 各自只出现一次。

题解

模拟

对于每种字符，分别尝试向左向右拓展, 遇到障碍物即可停止，计算出各自的最小距离。

参考代码

• Python

def find_min_time(s):
    # 定义角色
    characters = 'RBG'
    n = len(s)
    results = []
    for ch in characters:
        # 找到当前角色的位置
        idx = s.find(ch)
        i, j = idx - 1, idx + 1
        count = 1
        found = False
        while i >= 0 or j < n:
            # 检查左边是否找到其他角色
            if i >= 0 and s[i] in characters:
                found = True
                break
            # 如果左边是空地，继续向左移动
            if i >= 0 and s[i] == '*':
                i -= 1
            # 检查右边是否找到其他角色
            if j < n and s[j] in characters:
                found = True
                break
            # 如果右边是空地，继续向右移动
            if j < n and s[j] == '*':
                j += 1
            count += 1

        # 如果没有找到其他角色，返回 -1
        if not found:
            count = -1
        results.append(count)

    return results

# 示例输入
s = "R***B**G"
print(find_min_time(s))  # 输出: [4, 3, 3]

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] characters = {'R', 'B', 'G'};
        int n = s.length();
        
        for (char ch : characters) {
            // 找到当前角色的位置
            int idx = s.indexOf(ch);
            int i = idx - 1, j = idx + 1;
            int count = 1;
            boolean found = false;

            while (i >= 0 || j < n) {
                // 检查左边是否找到其他角色
                if (i >= 0 && charactersContains(s.charAt(i), characters)) {
                    found = true;
                    break;
                }
                // 如果左边是空地，继续向左移动
                if (i >= 0 && s.charAt(i) == '*') i--;

                // 检查右边是否找到其他角色
                if (j < n && charactersContains(s.charAt(j), characters)) {
                    found = true;
                    break;
                }
                // 如果右边是空地，继续向右移动
                if (j < n && s.charAt(j) == '*') j++;

                count++;
            }

            // 如果没有找到其他角色，返回 -1
            if (!found) count = -1;

            System.out.print(count + " ");
        }
    }

    private static boolean charactersContains(char c, char[] characters) {
        for (char ch : characters) {
            if (ch == c) return true;
        }
        return false;
    }
}

• Cpp

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    string characters = "RBG";
    int n = s.size();

    for (char ch : characters) {
        // 找到当前角色的位置
        int idx = s.find(ch);
        int i = idx - 1, j = idx + 1;
        int count = 1;
        bool found = false;

        while (i >= 0 || j < n) {
            // 检查左边是否找到其他角色
            if (i >= 0 && characters.find(s[i]) != string::npos) {
                found = true;
                break;
            }
            // 如果左边是空地，继续向左移动
            if (i >= 0 && s[i] == '*') i--;

            // 检查右边是否找到其他角色
            if (j < n && characters.find(s[j]) != string::npos) {
                found = true;
                break;
            }
            // 如果右边是空地，继续向右移动
            if (j < n && s[j] == '*') j++;

            count++;
        }

        // 如果没有找到其他角色，返回 -1
        if (!found) count = -1;

        cout << count << " ";
    }

    return 0;
}

🧩 03.砖块合成与收集 评测链接🔗

问题描述

在一个小镇上，K小姐正在进行一项有趣的砖块收集活动。她手中有 个红砖、 个蓝砖和 个绿砖。根据镇上的规定，每 个红砖可以合成 个蓝砖，而每 个蓝砖可以合成 个绿砖。值得注意的是，砖块只能正向合成，不能反向分解。

K小姐希望收集到尽可能多的完整套砖块，每套包含 个红砖、 个蓝砖和 个绿砖。请计算 K小姐最多可以收集多少套完整的砖块。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 ，代表数据组数。每组测试数据描述如下：

在一行上输入五个整数 ，分别表示红砖、蓝砖和绿砖的数量及合成的比例。

输出格式

对于每一组测试数据，在一行上输出一个整数，代表 K小姐最多可以收集到的砖块套数。

样例输入

2
1 2 3 4 2
10 2 1 4 2

样例输出

1
2

数据范围

• 每组数据中的 的值均在 到 之间。
• 合成比例 的值均在 到 之间。

题解

二分答案

假定当前的答案是 ，对于红砖来说将 的部分全部合成蓝砖。 蓝砖同理，将多余的部分全部合成绿砖。 如果最后绿砖的数量 说明当前答案可以满足，尝试更大的答案，否则尝试更小的答案。 上述的过程可以用二分来实现，时间复杂度

参考代码

• Python

import sys

# 从标准输入读取数据
input = lambda: sys.stdin.readline().strip()

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

# 遍历每个测试用例
for _ in range(T):
    # 读取每组数据的参数
    a, b, c, x, y = map(int, input().split())
    
    # 初始化二分查找的范围
    lo, hi = 0, a
    
    # 检查是否可以收集到 mid 套完整砖块
    def check(mid, a, b, c):
        # 计算多余的红砖数量并合成蓝砖
        diff = a - mid
        b += diff // x
        
        # 检查蓝砖是否足够
        diff = b - mid
        if diff < 0:
            return False
        
        # 计算多余的蓝砖数量并合成绿砖
        c += diff // y
        
        # 检查绿砖是否足够
        diff = c - mid
        if diff < 0:
            return False
        
        return True
    
    # 二分查找最大可收集套数
    while lo < hi:
        mid = (lo + hi + 1) >> 1
        if check(mid, a, b, c):
            lo = mid
        else:
            hi = mid - 1
    
    # 输出结果
    print(lo)

• Java

import java.util.Scanner;

public class BrickCollection {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取测试用例数量
        int T = sc.nextInt();
        
        // 遍历每个测试用例
        for (int t = 0; t < T; t++) {
            // 读取每组数据的参数
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();
            long x = sc.nextLong();
            long y = sc.nextLong();
            
            // 初始化二分查找的范围
            long lo = 0;
            long hi = a;
            
            // 检查是否可以收集到 mid 套完整砖块
            while (lo < hi) {
                long mid = (lo + hi + 1) / 2;
                if (canCollect(mid, a, b, c, x, y)) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
            
            // 输出结果
            System.out.println(lo);
        }
        
        sc.close();
    }
    
    private static boolean can