✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魔法环的加权切割

1️⃣：枚举所有可能的切割位置

2️⃣：计算每个位置的加权交替和，找出最大值

难度：中等

这道题的关键在于理解加权交替和的计算方式，并通过枚举所有可能的切割位置，找出最大值。由于数据范围较小 ，O(n²) 的解法可以通过。实现时可以利用取模运算来简化数组访问。

题目二：时间序列自相关分析

1️⃣：计算序列的均值和方差

2️⃣：根据自相关函数公式计算各个延迟的相关系数

3️⃣：按照要求的格式输出结果

难度：中等

这道题需要理解自相关函数的定义，并正确实现计算过程。关键在于计算时间序列在不同延迟下与自身的相关性，处理好特殊情况（如方差为0）以及格式化输出。

题目三：镜像追踪游戏

1️⃣：理解角色和镜像怪之间的对称关系

2️⃣：使用BFS找出所有可到达的空地位置

3️⃣：检查每个爆炸陷阱的镜像位置是否可达

难度：中等偏难

这道题的突破口在于发现角色和镜像怪之间的镜像关系，利用广度优先搜索找出所有可到达的位置，然后检查爆炸陷阱的镜像位置是否在可到达集合中。理解这种空间对称关系是解题的关键。

01. 魔法环的加权切割

问题描述

小柯拥有一个魔法环，环上有 个数字 依次排列。她想通过一系列操作来获得最大的魔法能量。操作步骤如下：

1. 选择一个位置 切开魔法环，形成一个线性序列 ，其中：

2. 计算序列 的加权交替和：

小柯想知道，在所有可能的切割位置中，能获得的最大魔法能量值是多少。

输入格式

第一行包含一个整数 ，表示魔法环上的数字个数。

第二行包含 个整数 ，表示魔法环上的数字。

输出格式

输出一个整数，表示所有切割位置中，能获得的最大魔法能量值。

样例输入

4
1 2 3 4

5
1 4 2 3 5

样例输出

4

27

数据范围

• 
• 

样例 解释说明

样例1	当切割位置 时，得到序列 ，加权交替和为 ，这是所有可能的切割位置中的最大值。
样例2	当切割位置 时，得到序列 ，加权交替和为 ，这是所有可能的切割位置中的最大值。

题解

这道题让我们在魔法环的每个可能位置切开，然后计算加权交替和，找出最大值。

首先，我们需要理解什么是加权交替和。对于一个序列 ，加权交替和定义为：

这里的关键是"交替"，意味着符号在 +1 和 -1 之间交替，而"加权"表示每个元素乘以它在序列中的位置。

由于魔法环的数字个数 最大为 2000，如果我们尝试每个可能的切割位置，计算量为 ，对于这个数据范围是完全可接受的。

解题步骤如下：

1. 枚举所有可能的切割位置 (从 1 到 )
2. 对于每个位置，构建线性序列
3. 计算该序列的加权交替和
4. 更新最大值

实际编码时，我们可以避免显式构建序列 ，直接通过取模运算 (k + i) % n 来访问原始序列 中对应的元素。这样可以节省空间。

时间复杂度为 ，对于 的约束来说是高效的。空间复杂度为 ，主要用于存储原始序列。

参考代码

• Python

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

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

# 计算所有切割位置的加权交替和，找最大值
ans = float('-inf')
for k in range(n):
    s = 0
    for i in range(n):
        sign = 1 if i % 2 == 0 else -1
        w = i + 1
        s += sign * w * a[(k + i) % n]
    ans = max(ans, s)

# 输出结果
print(ans)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 枚举所有切割位置
    long long ans = LLONG_MIN;
    for (int k = 0; k < n; k++) {
        long long s = 0;
        for (int i = 0; i < n; i++) {
            long long sign = (i % 2 == 0) ? 1 : -1;
            long long w = i + 1;
            s += sign * w * a[(k + i) % n];
        }
        ans = max(ans, s);
    }
    
    // 输出结果
    cout << ans << endl;
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        long[] a = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }
        
        long ans = Long.MIN_VALUE;
        for (int k = 0; k < n; k++) {
            long s = 0;
            for (int i = 0; i < n; i++) {
                long sign = (i % 2 == 0) ? 1 : -1;
                long w = i + 1;
                s += sign * w * a[(k + i) % n];
            }
            ans = Math.max(ans, s);
        }
        
        System.out.println(ans);
    }
}

02. 时间序列自相关分析

问题描述

小基 正在研究一种时间序列数据分析方法，她需要计算数据的自相关函数。自相关函数是衡量时间序列在不同时间延迟下与自身相关性的重要指标。

对于一个时间序列 ，其自相关函数 定义为：

其中：

• 表示期望值
• 是序列的均值
• 是序列的方差
• 是时间延迟（lag）

小基 需要编写一个程序，接受一个浮点数序列作为输入，然后输出该序列在各个时间延迟下的自相关系数。

输入格式

输入一行浮点数，用空格分隔。

输出格式

输出一个列表，包含序列在各个时间延迟下的自相关系数，保留三位小数。

样例输入

1.0 2.0 3.0 4.0

样例输出

[4.0, 1.0, -1.2, -1.8]

数据范围

• 输入序列的长度至少为 2
• 对于时间延迟大于序列长度的情况，自相关系数定义为 0

样例 解释说明

样例1	输入序列为 [1.0, 2.0, 3.0, 4.0]。 计算均值 和方差 。 滞后0的自相关系数: 滞后1的自相关系数: 滞后2的自相关系数: 滞后3的自相关系数:

题解

这道题要求我们计算时间序列的自相关函数，这是时间序列分析中的一个基本概念。

自相关函数度量了时间序列在不同时间延迟下与自身的相关性。具体来说，对于延迟 ，我们需要计算:

解题步骤如下：

1. 计算时间序列的均值 ：

2. 计算时间序列的方差 ：

3. 对于每个延迟 (从0到n-1)，计算自相关系数：

   • 计算
   • 将结果除以方差

需要注意的是，随着延迟的增加，可以用于计算的数据点对会减少。当延迟等于序列长度时，没有数据点对可以计算，此时自相关系数定义为0。

时间复杂度为 ，其中 n 是序列长度。虽然对于长序列来说计算量较大，但对于这个问题的数据范围来说是可以接受的。

参考代码

• Python

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

# 读取输入数据
x = list(map(float, input().split()))
n = len(x)

# 计算均值
mu = sum(x) / n

# 计算方差
var = sum((xi - mu) ** 2 for xi in x) / n

# 计算自相关系数
res = []
for h in range(n):
    num = 0
    for i in range(n - h):
        num += (x[i + h] - mu) * (x[i] - mu)
    # 如果方差为0，自相关系数为0
    corr = num / var if var > 0 else 0
    res.append(round(corr, 1))

# 输出结果
print(res) 

• Cpp

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

int main() {
    // 关闭同步，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<double> x;
    double val;
    while (iss >> val) {
        x.push_back(val);
    }
    
    int n = x.size();
    
    // 计算均值
    double mu = 0;
    for (double xi : x) {
        mu += xi;
    }
    mu /= n;
    
    // 计算方差
    double var = 0;
    for (double xi : x) {
        var += (xi - mu) * (xi - mu);
    }
    var /= n;
    
    // 计算各延迟的自相关系数
    vector<double> res(n);
    for (int h = 0; h < n; h++) {
        double num = 0;
        for (int