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

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

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

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

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

🍥 本次难度较大，其中最后两题比较有区分度

1️⃣ 模拟题，遍历一遍即可

2️⃣ 枚举+判断质数，难度不大。

3️⃣ ST表优化DP，难度较大，要优化转移

4️⃣ 线段树，实际考试的时候建议大家可以直接上暴力骗分

🧸 01.命名风格转换器 评测链接🔗

问题描述

• C LYA 是一位热爱编程的大学生。她最近在学习不同的代码命名风格。她发现自己以前习惯使用下划线命名法（snake_case），例如：user_profile、calculate_total、update_database。

• C 然而，在参加了一个编程讲座后，LYA 学会了大驼峰命名法（PascalCase）。这种方法要求每个单词的首字母都大写，并且单词之间没有下划线，例如：UserProfile、CalculateTotal、UpdateDatabase。

现在，LYA 想要将她以前所有的代码中的变量名从下划线命名法转换为大驼峰命名法。你能帮助她完成这个转换任务吗？

输入格式

第一行包含一个正整数 （），表示需要转换的变量名数量。

接下来的 行，每行包含一个字符串 （），表示一个使用下划线命名法的变量名。

输出格式

输出 行，每行一个字符串，表示转换后的大驼峰命名法变量名。

样例输入1

2
now_coder
acm_icpc

样例输出1

NowCoder
AcmIcpc

样例输入2

3
user_profile
calculate_total
update_database

样例输出2

UserProfile
CalculateTotal
UpdateDatabase

样例解释

样例 解释说明

样例1	第一个变量 "now_coder" 转换为 "NowCoder"，第二个变量 "acm_icpc" 转换为 "AcmIcpc"。每个单词的首字母都变成了大写，并且删除了下划线。
样例2	三个变量名都按照大驼峰命名法进行了转换。注意每个单词的首字母都变成了大写，包括原变量名中的第一个单词。

数据范围

• 
• 

题解

模拟

常见的字符串处理问题

要求将下划线命名法（snake_case）转换为大驼峰命名法（PascalCase）

1. 将输入的字符串按下划线分割成多个单词。
2. 然后将每个单词的首字母转换为大写。
3. 最后将处理后的单词连接起来，形成大驼峰命名法的字符串。

参考代码

• Python

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

# 定义转换函数
def to_pascal_case(s):
    # 将第一个字符转换为大写
    result = s[0].upper()
    i = 1
    # 遍历剩余字符
    while i < len(s):
        if s[i] == '_':
            # 跳过下划线，将下一个字符转换为大写
            result += s[i+1].upper()
            i += 2
        else:
            # 其他字符保持不变
            result += s[i]
            i += 1
    return result

# 处理每个测试用例
for _ in range(t):
    # 读取变量名并转换
    variable = input().strip()
    print(to_pascal_case(variable))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取测试用例数量
        int t = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        for (int i = 0; i < t; i++) {
            // 读取变量名并转换
            String variable = scanner.nextLine();
            System.out.println(toPascalCase(variable));
        }
        scanner.close();
    }

    // 定义转换函数
    public static String toPascalCase(String s) {
        StringBuilder result = new StringBuilder();
        // 将第一个字符转换为大写
        result.append(Character.toUpperCase(s.charAt(0)));
        
        // 遍历剩余字符
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '_') {
                // 跳过下划线，将下一个字符转换为大写
                i++;
                if (i < s.length()) {
                    result.append(Character.toUpperCase(s.charAt(i)));
                }
            } else {
                // 其他字符保持不变
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}

• Cpp

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

// 定义转换函数
string toPascalCase(const string& s) {
    string result;
    // 将第一个字符转换为大写
    result += toupper(s[0]);
    
    // 遍历剩余字符
    for (size_t i = 1; i < s.length(); ++i) {
        if (s[i] == '_') {
            // 跳过下划线，将下一个字符转换为大写
            ++i;
            if (i < s.length()) {
                result += toupper(s[i]);
            }
        } else {
            // 其他字符保持不变
            result += s[i];
        }
    }
    return result;
}

int main() {
    int t;
    // 读取测试用例数量
    cin >> t;
    cin.ignore(); // 消耗换行符

    for (int i = 0; i < t; ++i) {
        string variable;
        // 读取变量名
        getline(cin, variable);
        // 转换并输出结果
        cout << toPascalCase(variable) << endl;
    }

    return 0;
}

🍭 02.卢小姐的糖果计划 评测链接🔗

问题描述

卢小姐是一位甜食爱好者，她最近收到了一大盒糖果作为生日礼物。为了控制糖分摄入，她制定了一个特别的糖果食用计划。

具体计划如下：

• 如果当天剩余的糖果数量是质数，她会吃掉 颗糖果。
• 如果当天剩余的糖果数量不是质数，她会吃掉 颗糖果。

其中， 表示当天剩余的糖果数量， 表示对 向下取整。例如，。

卢小姐想知道，按照这个计划，她的糖果可以吃多少天。

输入格式

输入一个整数 （），表示卢小姐初始的糖果数量。

输出格式

输出一个整数，表示卢小姐可以吃糖果的天数。

样例输入1

10

样例输出1

3

样例解释

样例 解释说明

样例1	第一天，10不是质数，吃掉 颗，剩余4颗。 第二天，4不是质数，吃掉 颗，剩余1颗。 第三天，1是质数，吃掉 颗，糖果吃完。 总共吃了3天。

数据范围

• 

题解

模拟+判断质数

这道题目的核心在于模拟卢小姐吃糖果的过程，直到糖果吃完为止。虽然初看起来数据范围很大（），但实际上糖果数量会快速减少，因此可以直接模拟整个过程。

需要一个函数来判断一个数是否为质数。可以使用简单的试除法，只需要检查到 即可。

模拟卢小姐每天吃糖果的过程：

• 如果当前糖果数量是质数，吃掉 颗
• 否则，吃掉 颗

每次吃完后，更新剩余糖果数量，并将天数加一。

重复这个过程，直到糖果数量变为0。

时间复杂度分析：

虽然输入的 可以达到 ，但每次操作都会使糖果数量至少减半（不考虑+1的情况）。因此，最坏情况下，操作次数不会超过 次。每次操作中，判断质数的复杂度为

参考代码

• Python

def is_prime(n):
    """
    判断一个数是否为质数
    """
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def eat_candies(n):
    """
    模拟吃糖果的过程，返回可以吃的天数
    """
    days = 0
    while n > 0:
        if is_prime(n):
            n -= n // 3 + 1
        else:
            n -= n // 2 + 1
        days += 1
    return days

# 读取输入
n = int(input())

# 计算并输出结果
print(eat_candies(n))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        System.out.println(eatCandies(n));
    }

    // 判断一个数是否为质数
    private static boolean isPrime(long n) {
        if (n < 2) return false;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 模拟吃糖果的过程，返回可以吃的天数
    private static int eatCandies(long n) {
        int days = 0;
        while (n > 0) {
            if (isPrime(n)) {
                n -= n / 3 + 1;
            } else {
                n -= n / 2 + 1;
            }
            days++;
        }
        return days;
    }
}

• Cpp

#include <iostream>
#include <cmath>

using namespace std;

// 判断一个数是否为质数
bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 模拟吃糖果的过程，返回可以吃的天数
int eatCandies(long long n) {
    int days = 0;
    while (n > 0) {
        if (isPrime(n)) {
            n -= n / 3 + 1;
        } else {
            n -= n / 2 + 1;
        }
        days++;
    }
    return days;
}

int main() {
    long long n;
    cin >> n;
    cout << eatCandies(n) << endl;
    return 0;
}

📖 03.图书馆藏书分类优化 评测链接🔗

问题描述

K小姐是一位图书馆管理员。她最近接到了一项特殊任务：将一排 本书重新分类成 个书架。每本书都有一个独特的分类号 。K小姐希望通过巧妙的分组方式，使得每个书架上的书籍分类号的最大公约数（GCD）之和最大。

为了保持书籍的原有顺序，K小姐决定只能将连续的书籍放在同一个书架上。她需要你的帮助来计算出最优的分组方案，使得 个书架上的书籍分类号的GCD之和最大。

输入格式

第一行包含两个整数 和 ，分别表示书籍总数和需要分成的书架数量。

第二行包含 个整数 ，表示每本书的分类号。

输出格式

输出一个整数，表示 个书架上的书籍分类号的最大公约数之和的最大值。

样例输入1

4 2
5 6 3 2

样例输出1

6

样例输入2

5 3
10 5 15 20 25

样例输出2

20

样例解释

样例 解释说明

样例1	最优分组方案是 [5, 6] 和 [3, 2]。第一组的GCD是3，第二组的GCD是1，总和为4。
样例2	最优分组方案是 [10, 5], , [20, 25]。这三组的GCD分别是5, 15, 5，总和为25。

数据范围

• 
• 

题解

数据结构优化DP

定义 表示将前 本书分成 个书架时能获得的最大GCD和。

1. **预处理：**使用ST表（Sparse Table）预处理任意区间的GCD。这样可以在O(1)时间内查询任意区间的GCD。

2. 动态规划：

   • 状态定义： 表示前 本书分成 个书架的最大GCD和。
   • 转移方程：，其中 从 到 。
   • 边界条件：

3. 最终答案：

时间复杂度分析：

• ST表预处理时间复杂度：
• DP过程时间复杂度：
• 总时间复杂度：

对于给定的数据范围（），这个复杂度是可以接受的。

参考代码

• Python

import math

def gcd(a, b):
    """计算两个数的最大公约数"""
    while b:
        a, b = b, a % b
    return a

def build_st_table(arr):
    """构建ST表用于快速区间GCD查询"""
    n = len(arr)
    log = [0] * (n + 1)
    for i in range(2, n + 1):
        log[i] = log[i // 2] + 1
    
    st = [[0] * (log[n] + 1) for _ in range(n)]
    for i in range(n):
        st[i][0] = arr[i]
    
    for j in range(1, log[n] + 1):
        for i in range(n - (1 << j) + 1):
            st[i][j] = gcd(st[i][j-1], st[i + (1 << (j-1))][j-1])
    
    return st, log

def query_gcd(st, log, l, r):
    """查询区间[l, r]的GCD"""
    j = log[r - l + 1]
    return gcd(st[l][j], st[r - (1 << j) + 1][j])

def max_gcd_sum(n, m, arr):
    """计算最大GCD和"""
    st, log = build_st_table(arr)
    dp = [[-float('inf')] * (m + 1) for _ in range(n + 1)]
    
    # 初始化边界条件：只有一个书架的情况
    for i in range(1, n + 1):
        dp[i][1] = query_gcd(st, log, 0, i - 1)
    
    # 动态规划过程
    for j in range(2, m + 1):
        for i in range(j, n + 1):
            for k in range(j - 1, i):
                # 尝试所有可能的分割点，更新dp[i][j]
                dp[i][j] = max(dp[i][j], dp[k][j-1] + query_gcd(st, log, k, i - 1))
    
    # 返回最终结果
    return dp[n][m]

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

# 计算并输出结果
result = max_gcd_sum(n, m, arr)
print(result)

• Java

import java.util.*;

public class Main {
    static int[