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

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

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

🍄 题面描述等均已改编，如果试题题面描述不一样请理解，做法和题目本质基本不变。

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

1️⃣ 经典老题了，统计 2 和 5 的数量，取最小的那个

2️⃣ 字符串模拟题，难度不大

3️⃣ 贪心，由于每个值不相等，排序后对于能分的分，计算最小分割次数，最后和k做比较

4️⃣ 树形DP，观察到题目描述，其实本质上是颗树，求树上直径的问题

🍬 01.神秘的糖果盒 评测链接🔗

题目描述

K小姐是一位热爱收集糖果的甜点爱好者。她有一个神奇的糖果盒，里面装满了各种各样的糖果。每颗糖果都有一个特殊的数值，代表着它的甜度。K小姐想知道，如果她把所有糖果的甜度乘起来，最终结果的末尾会有多少个0。这个数字恰好就是她今天可以吃到的糖果数量。你能帮助K小姐计算出这个数字吗？

输入格式

第一行输入一个正整数 （），表示糖果盒中糖果的数量。

第二行输入 个正整数 （），两两之间用空格隔开，表示每颗糖果的甜度值。

输出格式

输出一个整数 ，表示所有糖果甜度值之和的末尾0的个数。

样例输入1

1
10

样例输出1

1

样例输入2

3
25 8 10

样例输出2

3

数据范围

题解

数学

需要理解末尾0的形成原理。在十进制系统中，末尾的0是由10的因子产生的，而10可以分解为2和5的乘积。因此，我们的任务就转化为计算所有数字中2和5的因子的数量。

末尾0的个数取决于2和5因子中数量较少的那个，为什么呢？

• 因为每一对2和5才能产生一个10，从而在结果末尾产生一个0。

解题步骤：

1. 遍历所有输入的数字。
2. 对每个数字，统计它包含的2和5的因子数量。
3. 累加所有数字的2和5的因子数量。
4. 取2和5因子数量的较小值，这就是最终结果末尾0的个数。

参考代码

• Python

def count_factors(n, factor):
    """计算n中factor因子的数量"""
    count = 0
    while n % factor == 0:
        n //= factor
        count += 1
    return count

def solve():
    n = int(input())  # 读取糖果数量
    candies = list(map(int, input().split()))  # 读取每颗糖果的甜度值
    
    count_2 = 0  # 2因子的总数
    count_5 = 0  # 5因子的总数
    
    for candy in candies:
        count_2 += count_factors(candy, 2)
        count_5 += count_factors(candy, 5)
    
    # 末尾0的个数等于2和5因子中较少的那个
    print(min(count_2, count_5))

solve()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取糖果数量
        long count2 = 0, count5 = 0;  // 使用long类型防止溢出
        
        for (int i = 0; i < n; i++) {
            int candy = scanner.nextInt();
            count2 += countFactors(candy, 2);
            count5 += countFactors(candy, 5);
        }
        
        System.out.println(Math.min(count2, count5));
    }
    
    // 计算num中factor因子的数量
    private static int countFactors(int num, int factor) {
        int count = 0;
        while (num % factor == 0) {
            num /= factor;
            count++;
        }
        return count;
    }
}

• Cpp

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

// 计算num中factor因子的数量
int countFactors(int num, int factor) {
    int count = 0;
    while (num % factor == 0) {
        num /= factor;
        count++;
    }
    return count;
}

int main() {
    int n;
    cin >> n;  // 读取糖果数量
    
    long long count2 = 0, count5 = 0;  // 使用long long防止溢出
    
    for (int i = 0; i < n; i++) {
        int candy;
        cin >> candy;
        count2 += countFactors(candy, 2);
        count5 += countFactors(candy, 5);
    }
    
    cout << min(count2, count5) << endl;
    
    return 0;
}

🪙 02.密码学家的挑战 评测链接🔗

问题描述

LYA 是一位年轻有为的密码学家。她最近接到了一个特殊的任务:破解一种新型的加密信息。经过长期研究,LYA 发现了这种加密方式的规律:

1. 原始信息是一个由小写英文字母组成的多元字符串,即不包含重复字符的字符串。例如 "abc", "xyz", "apex", "blackmyth" 都是多元字符串,而 "goodgame", "connect" 则不是。

2. 加密后的信息同样是一个多元字符串,它与原始信息存在严格的一一对应关系。假设原始信息为 ,加密信息为 。 是字典序上刚好大于 的下一个多元字符串。

LYA 将这个加密函数记为 ,例如: , ,

需要注意的是,不存在字典序大于 小于 的多元字符串 。如果不存在字典序大于 的下一个多元字符串,则 ,例如:

现在,LYA 收到了一批新的加密信息 ,她需要你的帮助来破解出原始信息 。你能协助 LYA 完成这个任务吗?

输入格式

第一行一个整数 ,表示测试用例的数量 。

对于每个测试用例: 一行输入字符串 。

输出格式

对于每个测试用例,输出一行,为对应的原始信息 。

样例输入1

5
abc
abz
azyxwvutsrqponmlkjihgfedcb
zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvwyx

样例输出1

abcd
abzc
b
zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvx

样例解释

数据范围

• 
• 为一个多元字符串

题解

模拟题

检查是否可以直接在字符串末尾添加一个新字符

• 如果可以是最简单的情况，只需要找到最小的未使用字符并添加到末尾即可。

• 如果不能直接添加字符，就需要从字符串的末尾开始，找到第一个可以增大的位置。

  这个位置的特征是:它右边的字符都是按降序排列的。找到这个位置后，将这个位置的字符替换为比它大的最小字符，然后删除它右边的所有字符。

参考代码

• Python

def solve(s):
    # 将字符串转换为字符列表,方便操作
    chars = list(s)
    n = len(chars)
    
    # 检查是否可以直接在末尾添加字符
    used = set(chars)
    for c in range(ord('a'), ord('z') + 1):
        if chr(c) not in used:
            return s + chr(c)
    
    # 从后向前查找可以增大的位置
    i = n - 2
    while i >= 0 and chars[i] >= chars[i + 1]:
        i -= 1
    
    # 如果找不到可以增大的位置,返回原字符串
    if i == -1:
        return s
    
    # 找到比chars[i]大的最小字符
    j = n - 1
    while chars[j] <= chars[i]:
        j -= 1
    
    # 交换chars[i]和chars[j]
    chars[i], chars[j] = chars[j], chars[i]
    
    # 删除i之后的所有字符
    return ''.join(chars[:i+1])

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

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

• Java

import java.util.*;

public class Main {
    public static String solve(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        
        // 检查是否可以直接在末尾添加字符
        boolean[] used = new boolean[26];
        for (char c : chars) {
            used[c - 'a'] = true;
        }
        for (int i = 0; i < 26; i++) {
            if (!used[i]) {
                return s + (char)('a' + i);
            }
        }
        
        // 从后向前查找可以增大的位置
        int i = n - 2;
        while (i >= 0 && chars[i] >= chars[i + 1]) {
            i--;
        }
        
        // 如果找不到可以增大的位置,返回原字符串
        if (i == -1) {
            return s;
        }
        
        // 找到比chars[i]大的最小字符
        int j = n - 1;
        while (chars[j] <= chars[i]) {
            j--;
        }
        
        // 交换chars[i]和chars[j]
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        
        // 返回i之前的所有字符
        return new String(chars, 0, i + 1);
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        
        for (int t = 0; t < T; t++) {
            String s = scanner.nextLine();
            System.out.println(solve(s));
        }
    }
}

• Cpp

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

string solve(string s) {
    vector<char> chars(s.begin(), s.end());
    int n = chars.size();
    
    // 检查是否可以直接在末尾添加字符
    vector<bool> used(26, false);
    for (char c : chars) {
        used[c - 'a'] = true;
    }
    for (int i = 0; i < 26; i++) {
        if (!used[i]) {
            return s + char('a' + i);
        }
    }
    
    // 从后向前查找可以增大的位置
    int i = n - 2;
    while (