🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 80+ 套笔试题，笔试真题 会在第一时间跟新

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

🧩 备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至 100 套后，价格会进行一波调整~

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

🪔 阿里控股秋招笔试来啦！！！

🍥 本次难度不大，不过T3需要字符串哈希优化，建议没用过的朋友可以参考一下这个模版

1️⃣ 又是一道考虑比大小的题，今年的秋招真的很喜欢考

2️⃣ 贪心+枚举，比较容易想到

3️⃣ 需要抽象一下模型，字符串哈希

🪐 01.LYA的特殊密码

问题描述

LYA是一位密码学爱好者，她最近发明了一种特殊的密码系统。在这个系统中，只有由数字5到9组成的数字序列才被认为是有效的密码。现在，LYA想要知道对于给定的一个数字N，比N大的最小有效密码是多少。

输入格式

第一行包含一个正整数 ，表示测试用例的数量。

接下来的 行，每行包含一个正整数 ，表示LYA给出的初始数字。

输出格式

输出 行，每行一个整数，表示对应初始数字的下一个有效密码。

样例输入

3
15
52
99

样例输出

55
55
555

数据范围

题解

贪心

1. 从左到右遍历给定数字的每一位。
2. 如果遇到小于5的数字，将其及其右边所有数字都替换为5，然后结束。
3. 如果所有数字都大于等于5，从右向左找到第一个不是9的数字，将其加1，右边的数字全部变为5。
4. 如果所有数字都是9，则在最左边添加一个5，其余位置全部变为5。

参考代码

• Python

import sys

def next_valid_password(n):
    # 将数字转换为字符列表
    digits = list(str(n))
    length = len(digits)
    
    # 从左到右遍历
    for i in range(length):
        if int(digits[i]) < 5:
            # 将当前位及其右边的所有位置为5
            digits[i:] = ['5'] * (length - i)
            return int(''.join(digits))
    
    # 如果所有数字都大于等于5，从右向左找第一个不是9的数字
    for i in range(length - 1, -1, -1):
        if digits[i] != '9':
            # 将该位加1，右边的所有位变为5
            digits[i] = str(int(digits[i]) + 1)
            digits[i+1:] = ['5'] * (length - i - 1)
            return int(''.join(digits))
    
    # 如果所有数字都是9，在最左边添加5，其余位置为5
    return int('5' + '5' * length)

# 读取测试用例数量
t = int(sys.stdin.readline().strip())

# 处理每个测试用例
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    print(next_valid_password(n))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(); // 读取测试用例数量
        
        for (int i = 0; i < t; i++) {
            long n = scanner.nextLong(); // 读取每个测试用例的数字
            System.out.println(nextValidPassword(n));
        }
        
        scanner.close();
    }
    
    public static long nextValidPassword(long n) {
        char[] digits = String.valueOf(n).toCharArray();
        int length = digits.length;
        
        // 从左到右遍历
        for (int i = 0; i < length; i++) {
            if (digits[i] < '5') {
                // 将当前位及其右边的所有位置为5
                for (int j = i; j < length; j++) {
                    digits[j] = '5';
                }
                return Long.parseLong(new String(digits));
            }
        }
        
        // 如果所有数字都大于等于5，从右向左找第一个不是9的数字
        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] != '9') {
                digits[i]++;
                for (int j = i + 1; j < length; j++) {
                    digits[j] = '5';
                }
                return Long.parseLong(new String(digits));
            }
        }
        
        // 如果所有数字都是9，在最左边添加5，其余位置为5
        char[] newDigits = new char[length + 1];
        newDigits[0] = '5';
        for (int i = 1; i <= length; i++) {
            newDigits[i] = '5';
        }
        return Long.parseLong(new String(newDigits));
    }
}

• Cpp

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 计算下一个有效密码
string nextValidPassword(string n) {
    int length = n.length();
    
    // 从左到右遍历
    for (int i = 0; i < length; i++) {
        if (n[i] < '5') {
            // 将当前位及其右边的所有位置为5
            fill(n.begin() + i, n.end(), '5');
            return n;
        }
    }
    
    // 如果所有数字都大于等于5，从右向左找第一个不是9的数字
    for (int i = length - 1; i >= 0; i--) {
        if (n[i] != '9') {
            n[i]++;
            fill(n.begin() + i + 1, n.end(), '5');
            return n;
        }
    }
    
    // 如果所有数字都是9，在最左边添加5，其余位置为5
    return string(length + 1, '5');
}

int main() {
    int t;
    cin >> t; // 读取测试用例数量
    
    while (t--) {
        string n;
        cin >> n; // 读取每个测试用例的数字
        cout << nextValidPassword(n) << endl;
    }
    
    return 0;
}

💻 02.K小姐的魔法花园清理

问题描述

K小姐是一位魔法花园的管理员。她的花园里有一排魔法植物，每株植物都有不同的魔力值。为了维持花园的平衡，K小姐需要将所有植物的魔力总和降为0。她可以使用以下三种魔法：

1. 花费 点魔力，将第一株植物连根拔起。
2. 花费 点魔力，将最后一株植物连根拔起。
3. 花费 点魔力，对所有植物使用削弱魔法，每株植物的魔力值减少1（如果某株植物的魔力值已经为0，则不受影响）。

K小姐想知道，她最少需要花费多少点魔力才能使花园恢复平衡（即所有植物的魔力总和为0，注意：空花园的魔力总和也视为0）。

输入格式

第一行包含一个正整数 ，表示测试用例的数量。

对于每个测试用例：

• 第一行包含四个正整数 ，分别表示植物的数量和三种魔法的魔力消耗。
• 第二行包含 个正整数 ，表示每株植物的初始魔力值。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示K小姐使花园恢复平衡所需的最小魔力消耗。

样例输入

2
5 3 3 2
5 3 3 2 1
1 3 4 100
2

样例输出

13
2

数据范围

• 
• 
• 
• 
• 所有测试用例中 的总和不超过

题解

贪心

观察到第三种操作（减少所有植物魔力值）实际上是在处理剩余植物中的最大魔力值。

这给了我们一个重要的启示：我们可以先考虑从两端移除一些植物，然后用第三种操作处理中间剩下的部分。

可以枚举所有可能的左右边界，对于每种情况：

1. 计算移除左边和右边植物的成本。
2. 对于中间剩余的植物，找出最大魔力值，用第三种操作将它们全部清零。

这样，问题就转化为了在所有可能的左右边界组合中找出总成本最小的方案。参考代码

• Python

def solve():
    # 读取输入
    n, x, y, z = map(int, input().split())
    plants = list(map(int, input().split()))
    
    # 初始化最小魔力消耗为无穷大
    min_cost = float('inf')
    
    # 考虑所有可能的左右边界
    for left in range(n + 1):
        for right in range(left, n + 1):
            # 计算移除左右植物的成本
            cost = x * left + y * (n - right)
            
            # 如果有剩余植物，计算使用第三种魔法的成本
            if left < right:
                max_power = max(plants[left:right])
                cost += z * max_power
            
            # 更新最小魔力消耗
            min_cost = min(min_cost, cost)
    
    return min_cost

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

# 处理每个测试用例
for _ in range(t):
    print(solve())

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(); // 读取测试用例数量
        
        for (int i = 0; i < t; i++) {
            System.out.println(solve(scanner));
        }
    }
    
    public static long solve(Scanner scanner) {
        // 读取输入
        int n = scanner.nextInt();
        long x = scanner.nextLong();
        long y = scanner.nextLong();
        long z = scanner.nextLong();
        
        long[] plants = new long[n];
        for (int i = 0; i < n; i++) {
            plants[i] = scanner.nextLong();
        }
        
        // 初始化最小魔力消耗为最大长整型值
        long minCost = Long.MAX_VALUE;
        
        // 考虑所有可能的左右边界
        for (int left = 0; left <= n; left++) {
            for (int right = left; right <= n; right++) {
                // 计算移除左右植物的成本
                long cost = x * left + y * (n - right);
                
                // 如果有剩余植物，计算使用第三种魔法的成本
                if (left < right) {
                    long maxPower = 0;
                    for (int i = left; i < right; i++) {
                        maxPower = Math.max(maxPower, plants[i]);
                    }
                    cost += z * maxPower;
                }
                
                // 更新最小魔力消耗
                minCost = Math.min(minCost, cost);
            }
        }
        
        return minCost;
    }
}

• Cpp

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

using namespace std;

long long solve() {
    // 读取输入
    int n;
    long long x, y, z;
    cin >> n >> x >> y >> z;
    
    vector<long long> plants(n);
    for (int i = 0; i < n; i++) {
        cin >> plants[i];
    }
    
    // 初始化最小魔力消耗为最大长整型值
    long long min_cost = LLONG_MAX;
    
    // 考虑所有可能的左右边界
    for (int left = 0; left <= n; left++) {
        for (int right = left; right <= n; right++) {
            // 计算移除左右植物的成本
            long long cost = x * left + y * (n - right);
            
            // 如果有剩余植物，计算使用第三种魔法的成本