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

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

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

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

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

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

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

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

PDD 秋招笔试，来啦！！！

这次知识点考察的非常很全面！！！，思维+数据结构+动态规划+快速幂+负数取模+二维前缀和，但对于每道题来说难度并不大哈。

1️⃣ 本题的做法很多，可以哈希+前缀和 或者 直接 DP 也是ok的

2️⃣动态规划，这个概念笔试考到很多次了，最大子数组的和，这题需要找到最大子数组和，然后 ，中间注意负数的取模

3️⃣ 思维题，等价于所有相同的数中距离相隔最远的，这个维护起来不难

4️⃣应该是pdd秋招最容易的T4了，对于每个V去对矩阵求个gcd，并根据结果是否为1构建01矩阵，然后根据这个做二维前缀和判断就行

拼多多-2024年-秋招(第3场)

01.LYA的彩虹花园

问题描述

LYA是一位热爱园艺的女孩，她精心打造了一个独特的彩虹花园。这个花园里的花朵排成一排，每朵花不是红色就是蓝色。LYA想要在花园里选择一段连续的花朵来布置一个特别的展览区。

为了让展览区看起来和谐美观，LYA希望选择的区域中红色和蓝色的花朵数量相等。她想知道，在她的花园里，最多可以选择多少朵花来布置这个特别的展览区。

输入格式

第一行包含一个正整数 ，表示花园里花朵的总数。（）

第二行包含一个长度为 的字符串，只包含字符 'R' 和 'B'，分别代表红色和蓝色的花朵。

输出格式

输出一个整数，表示符合条件的最大展览区花朵数量。

样例输入

7
RBRBRBB

样例输出

6

样例解释

LYA可以选择前 6 朵花作为展览区，其中包含 3 朵红色花和 3 朵蓝色花。

样例输入

8
RRRRBBRR

样例输出

4

数据范围

题解

哈希表+前缀和。

这题是力扣的原题，525. 连续数组

思路如下：

1. 遍历字符串，将 'R' 视为 +1，'B' 视为 -1。
2. 计算前缀和，记录每个前缀和第一次出现的位置。
3. 如果某个位置的前缀和之前出现过，说明这两个位置之间的子串中 'R' 和 'B' 的数量相等。

参考代码

• Python

def max_balanced_substring(s):
    n = len(s)
    prefix_sum = 0
    sum_index = {0: -1}  # 初始化前缀和为0的位置为-1
    max_length = 0

    for i in range(n):
        # 更新前缀和
        if s[i] == 'R':
            prefix_sum += 1
        else:
            prefix_sum -= 1
        
        # 检查当前前缀和是否出现过
        if prefix_sum in sum_index:
            max_length = max(max_length, i - sum_index[prefix_sum])
        else:
            sum_index[prefix_sum] = i

    return max_length

# 读取输入
n = int(input())
s = input().strip()

# 计算并输出结果
print(max_balanced_substring(s))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        System.out.println(maxBalancedSubstring(s));
    }

    public static int maxBalancedSubstring(String s) {
        int n = s.length();
        int prefixSum = 0;
        Map<Integer, Integer> sumIndex = new HashMap<>();
        sumIndex.put(0, -1);  // 初始化前缀和为0的位置为-1
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            // 更新前缀和
            prefixSum += (s.charAt(i) == 'R' ? 1 : -1);

            // 检查当前前缀和是否出现过
            if (sumIndex.containsKey(prefixSum)) {
                maxLength = Math.max(maxLength, i - sumIndex.get(prefixSum));
            } else {
                sumIndex.put(prefixSum, i);
            }
        }

        return maxLength;
    }
}

• Cpp

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

using namespace std;

int maxBalancedSubstring(const string& s) {
    int n = s.length();
    int prefixSum = 0;
    unordered_map<int, int> sumIndex;
    sumIndex[0] = -1;  // 初始化前缀和为0的位置为-1
    int maxLength = 0;

    for (int i = 0; i < n; ++i) {
        // 更新前缀和
        prefixSum += (s[i] == 'R' ? 1 : -1);

        // 检查当前前缀和是否出现过
        if (sumIndex.find(prefixSum) != sumIndex.end()) {
            maxLength = max(maxLength, i - sumIndex[prefixSum]);
        } else {
            sumIndex[prefixSum] = i;
        }
    }

    return maxLength;
}

int main() {
    int n;
    string s;
    cin >> n >> s;
    cout << maxBalancedSubstring(s) << endl;
    return 0;
}

✨ 02.LYA的魔法花园

问题描述

LYA是一位热爱园艺的魔法师。她有一个神奇的花园，里面种植了 朵魔法花。每朵花都有一个魔力值，可能为正也可能为负。LYA想要通过魔法来增强她的花园。

她发现了一个古老的魔法咒语，可以连续使用 次。每次使用咒语时，她可以在花园的任意位置种下一朵新的魔法花。这朵新花的魔力值等于花园中任意一段连续的花（可以是空段）的魔力值之和。

LYA希望通过巧妙地使用这个咒语，使得最终花园里所有花的魔力值之和最大。你能帮助她计算出最大可能的魔力值总和吗？

输入格式

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

对于每个测试用例：

• 第一行包含两个整数 和 ，分别表示初始花园中魔法花的数量和可以使用魔法咒语的次数。
• 第二行包含 个整数，表示每朵魔法花的初始魔力值。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最终可能达到的最大魔力值总和。由于结果可能很大，请对 取模。

样例输入

3
3 3
2 2 8
2 2
-4 -7
7 2
8 14 -9 6 0 -1 3

样例输出

96
999999996
87

数据范围

• 每朵花的魔力值

题解

在做这题之前需要会一个子问题，找出 最大子数组和，这题也是力扣的一道原题 53. 最大子数组和

本题需要注意对负数的取模，操作为

主要思路如下

1. 计算原始数组的总和 。
2. DP找出数组中的最大子数组和 。
3. 观察到，每次使用魔法咒语，都可以选择添加这个最大子数组和。
4. 经过 次操作后，最终的魔力值总和为：

参考代码

• Python

MOD = 10**9 + 7

def quick_pow(base, exp):
    """快速幂计算"""
    result = 1
    while exp > 0:
        if exp & 1:
            result = (result * base) % MOD
        base = (base * base) % MOD
        exp >>= 1
    return result

def max_magic_power(n, k, flowers):
    """计算最大魔力值总和"""
    # 计算原始总和
    total_sum = sum(flowers) % MOD
    
    # 找最大子数组和
    max_sum = current_sum = 0
    for flower in flowers:
        current_sum = max(flower, current_sum + flower)
        max_sum = max(max_sum, current_sum)
    
    # 计算最终结果
    result = (max_sum * (quick_pow(2, k) - 1) + total_sum) % MOD
    return (result % MOD + MOD) % MOD  # 确保结果为正

# 处理输入和输出
T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    flowers = list(map(int, input().split()))
    print(max_magic_power(n, k, flowers))

• Java

import java.util.*;

public class Main {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int[] flowers = new int[n];
            for (int i = 0; i < n; i++) {
                flowers[i] = scanner.nextInt();
            }
            System.out.println(maxMagicPower(n, k, flowers));
        }
    }

    private static long maxMagicPower(int n, int k, int[] flowers) {
        // 计算原始总和
        long totalSum = 0;
        for (int flower : flowers) {
            totalSum = (totalSum + flower + MOD) % MOD;
        }

        // 找最大子数组和
        long maxSum = 0, currentSum = 0;
        for (int flower : flowers) {
            currentSum = Math.max(flower, currentSum + flower);
            maxSum = Math.max(maxSum, currentSum);
        }

        // 计算最终结果
        long result = (maxSum * (quickPow(2, k) - 1) % MOD + totalSum) % MOD;
        return (result % MOD + MOD) % MOD;  // 确保结果为正
    }

    private static long quickPow(long base, int exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }
}

• Cpp

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

using namespace std;

typedef long long LL;
const int MOD = 1e9 + 7;

// 快速幂计算
LL quickPow(LL base, int exp) {
    LL result = 1;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

// 计算最大魔力值总和
LL maxMagicPower(int n, int k, vector<int>& flowers) {
    // 计算原始总和
    LL totalSum = 0;
    for (int flower : flowers) {
        totalSum = (totalSum + flower + MOD) % MOD;
    }

    // 找最大子数组和
    LL maxSum = 0, currentSum = 0;
    for (int flower : flowers) {
        currentSum = max((LL)flower, currentSum + flower);
        maxSum = max(maxSum, currentSum);
    }

    // 计算最终结果
    LL result = (maxSum * (quickPow(2, k) - 1) % MOD + totalSum) % MOD;
    return (result % MOD + MOD) % MOD;  // 确保结果为正
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> flowers(n);
        for (int& flower : flowers) {
            cin >> flower;
        }
        cout << maxMagicPower(n, k, flowers) << "\n";
    }
    return 0;
}

03. LYA的魔法书架整理

问题描述

LYA是一位热爱阅读的魔法师。她有一个神奇的书架，上面排列着 本魔法书。每本书都有一个独特的魔法编号。LYA发现，当她将书架上的一段连续的书籍取下来重新排序后，有时会得到与其他段落相同的排列顺序，她称这两段书籍为"魔法相似段"。

例如，如果书架上的编号序列为 ，那么 和 就是两个魔法相似段，因为它们排序后都是 。

LYA经常需要进行两种操作：

1. 更换某本书的魔法编号。
2. 询问当前书架上最长的魔法相似段有多长。

你能帮助LYA完成这些操作吗？

输入格式

第一行包含两个正整数 和 ，分别表示书架上魔法书的数量和LYA要进行的操作次数。()

第二行包含