✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线60+套真题改编解析，后续会持续更新的

春秋招合集 -> 互联网必备刷题宝典🔗

淘天-算法

题目一：最优数组分割求积

1️⃣：计算数组的总和，用于后续计算

2️⃣：枚举分割点，计算两部分和的乘积，找到最大值

难度：中等

这道题目的关键在于发现表达式可以简化为前缀和与后缀和的乘积，通过一次遍历即可找到最优分割点，实现O(n)的时间复杂度解法。

题目二：完美拼图挑战

1️⃣：计算所有拼图块的总面积，检查是否为完全平方数

2️⃣：根据目标正方形边长的奇偶性判断拼图是否可行

难度：中等

这道题目结合了数学推理和条件判断，需要分析正方形拼图的可行性条件。通过计算总面积和分析边长的奇偶性，我们可以在O(1)时间内判断是否有解。

题目三：信号增强最小操作次数

1️⃣：分析每个二进制位的传播特性

2️⃣：计算每个二进制位的最大间隔距离

3️⃣：根据最大间隔计算最少操作次数

难度：中等偏难

这道题目需要理解按位或运算的传播特性，并分析每个二进制位的传播速度。通过计算位值为1的最大间隔，我们可以得到实现目标的最少操作次数，时间复杂度为O(n)。

01. 最优数组分割求积

问题描述

小柯拥有一个长度为 的数组 ，她希望将这个数组分割为两个连续的部分： 和 （其中 ）。

分割后，小柯想要计算以下表达式的值：

也就是第一部分中的每个元素与第二部分中的每个元素的乘积之和。

小柯希望找到一个最优的分割点 ，使得上述表达式的值最大。你只需要告诉她这个最大值是多少，而不需要告诉她具体的分割位置。

由于答案可能非常大，请将结果对 取模后输出。

输入格式

第一行输入一个正整数 ()，表示数组的大小。

第二行输入 个整数 ()，表示数组中的各个元素。

输出格式

输出一个整数，表示上述表达式的最大可能值，对 取模后的结果。

样例输入

5
3 2 4 1 5

样例输出

54

样例 解释说明

样例1	最优的分割点是 ，将数组分为 和 。 计算表达式：

数据范围

• 
• 

题解

这道题的关键在于找到一种高效计算表达式的方法，避免暴力枚举所有元素对。

首先，让我们仔细分析这个表达式：

这个双重求和可以重写为：

也就是说，我们只需要计算数组前 个元素的和与剩余元素和的乘积，然后找到使这个乘积最大的 值。

解题步骤如下：

1. 计算整个数组的总和
2. 枚举每个可能的分割点 （从1到n-1）
3. 对于每个 ，计算前 个元素的和
4. 计算表达式 的值，并记录最大值
5. 最后将最大值对 取模后输出

时间复杂度分析：

• 计算数组总和需要 时间
• 枚举分割点并计算前缀和需要 时间
• 总体时间复杂度为

这个算法非常高效，即使在最大的数据范围（）下也能迅速得出结果。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    
    # 计算数组总和
    total = sum(nums)
    
    # 枚举分割点
    left_sum = 0
    max_prod = 0
    mod = 998244353
    
    for i in range(n-1):
        left_sum += nums[i]
        right_sum = total - left_sum
        # 计算两部分和的乘积
        prod = (left_sum * right_sum) % mod
        max_prod = max(max_prod, prod)
    
    return max_prod

print(solve())

• Cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 计算数组总和
    ll total = 0;
    for (int val : arr) {
        total += val;
    }
    
    // 枚举分割点
    ll lsum = 0, ans = 0;
    const int MOD = 998244353;
    
    for (int i = 0; i < n-1; i++) {
        lsum += arr[i];
        ll rsum = total - lsum;
        // 计算乘积并更新最大值
        ll prod = (lsum * rsum) % MOD;
        ans = max(ans, prod);
    }
    
    cout << ans << endl;
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        
        String[] line = br.readLine().trim().split(" ");
        long[] arr = new long[n];
        long total = 0;
        
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(line[i]);
            total += arr[i];
        }
        
        // 枚举分割点
        long lsum = 0;
        long maxProd = 0;
        
        for (int i = 0; i < n-1; i++) {
            lsum += arr[i];
            long rsum = total - lsum;
            // 计算两部分和的乘积
            long prod = (lsum * rsum) % MOD;
            maxProd = Math.max(maxProd, prod);
        }
        
        System.out.println(maxProd);
    }
}

02. 完美拼图挑战

问题描述

小毛是一位拼图爱好者，他有两种形状的拼图块： 个 的小正方形和 个 的大正方形。他想知道能否使用这些拼图块来精确地拼成一个更大的正方形，满足以下条件：

1. 大正方形的每个位置都必须被某个拼图块覆盖
2. 拼图块之间不能有重叠
3. 所有的拼图块都必须使用
4. 不能有任何部分超出大正方形的边界

请你帮助小毛判断，是否可能完成这个挑战。

输入格式

第一行输入一个整数 ()，表示测试数据的组数。

接下来 行，每行包含两个整数 和 ()，分别表示 和 正方形拼图块的数量。

输出格式

输出共 行，每行一个字符串。如果能够拼成一个完整的大正方形，输出"YES"；否则，输出"NO"。

样例输入

2
5 1
1 2

样例输出

YES
NO

样例 解释说明

样例1	有5个 的小正方形和1个 的大正方形，可以拼成一个 的正方形。 将 的大正方形放在左上角，剩余5个位置用 的小正方形填充。
样例2	有1个 的小正方形和2个 的大正方形，总面积为 ，理论上可以拼成 的正方形。 但由于2个 的大正方形无法在 的网格中摆放不重叠，所以无法拼成完整的大正方形。

数据范围

• 
• 

题解

这道题目要求判断能否使用给定数量的 和 的正方形拼成一个完整的大正方形。

首先，我们需要考虑面积是否满足要求：

• 的小正方形占据1个单位面积
• 的大正方形占据4个单位面积

所以总面积为：

要能拼成一个大正方形，这个总面积必须是某个完全平方数，即存在一个整数 使得 。如果不满足这个条件，直接输出"NO"。

但是，即使总面积是完全平方数，也不一定能拼成大正方形。我们还需要考虑以下条件：

1. 如果目标正方形的边长 是偶数，那么一定可以拼成功：
   • 可以先用 的大正方形尽可能地填充
   • 剩余的位置用 的小正方形填充
2. 如果目标正方形的边长 是奇数，情况稍微复杂：
   • 要考虑 的小正方形数量是否足够
   • 具体来说，需要检查

总结一下，如果满足以下任一条件，则可以拼成大正方形：

• 且 是偶数
• 且

时间复杂度分析：

• 对于每个测试用例，我们只需要常数时间进行计算和判断
• 总时间复杂度为 ，其中 是测试用例的数量

这个解法非常高效，即使在最大的数据范围下也能迅速得出结果。

参考代码

• Python

import sys
import math
input = lambda:sys.stdin.readline().strip()

def solve():
    t = int(input())
    for _ in range(t):
        a, b = map(int, input().split())
        
        # 计算总面积
        area = a + 4 * b
        
        # 检查是否为完全平方数
        k = int(math.sqrt(area))
        if k * k != area:
            print("NO")
            continue
        
        # 检查是否满足拼图条件
        if k % 2 == 0 or a >= k:
            print("YES")
        else:
            print("NO")

solve()

• Cpp

#include <bits