✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

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

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

百度-研发岗

题目一：魔法序列的神秘规律

1️⃣：发现斐波那契数列奇偶性的周期规律（奇、奇、偶）

2️⃣：利用数学公式 快速计算奇数个数

难度：中等

这道题目的关键在于观察斐波那契数列的奇偶性规律，发现每3项为一个周期。通过数学推导，可以得到一个 的高效解法，避免了暴力计算每一项的奇偶性。

题目二：智能配对系统优化

1️⃣：理解删除和调整操作对配对成功率的影响

2️⃣：使用动态规划记录是否使用删除操作的状态

3️⃣：计算相邻位置和跨越位置的最大收益

难度：中等偏难

这道题目结合了贪心思想和动态规划，需要深入理解调整规则的本质。通过状态转移，我们可以在 时间内找到最优策略，实现配对成功率的最大化。

题目三：时空传送门探险

1️⃣：将二维网格建模为图论问题

2️⃣：使用 Dijkstra 算法求解最短路径

3️⃣：按需计算传送边权值，避免显式建立完全图

难度：中等

这道题目将路径规划问题转化为最短路问题，需要理解两种移动方式的建模方法。虽然传送边构成完全图，但通过 Dijkstra 算法的按需计算，可以在可接受的时间复杂度内求解。

01. 魔法序列的神秘规律

问题描述

小兰是一位热爱数学的魔法师，她发现了一个神奇的魔法序列：。这个序列有个特殊的性质，从第三个数开始，每个数都等于前两个数的和。

在研究这个序列的过程中，小兰注意到序列中的数字有着奇妙的奇偶性规律。她想知道，对于给定的区间 ，这个魔法序列的第 项到第 项中，有多少个数是奇数。

作为小兰的助手，你需要回答她的多个询问。

输入格式

第一行包含一个正整数 （），表示询问的次数。

接下来 行，每行包含两个正整数 和 （），表示询问区间的左右端点。

输出格式

对于每个询问，输出一行一个整数，表示魔法序列第 项到第 项中奇数的个数。

样例输入

2
1 2
6 6

样例输出

2
0

样例	解释说明
样例1	序列前两项为 ，都是奇数，所以答案是
样例2	序列第 项为 ，是偶数，所以答案是

数据范围

题解

这道题目的关键在于发现魔法序列（斐波那契数列）的奇偶性规律。

让我们先观察序列的前几项：

• （奇数）
• （奇数）
• （偶数）
• （奇数）
• （奇数）
• （偶数）

仔细观察可以发现，奇偶性按照"奇、奇、偶"的模式循环，每 项为一个周期。

具体来说，第 项为偶数当且仅当 ，否则为奇数。

基于这个规律，我们可以快速计算区间 中奇数的个数。由于每 项中有 项为奇数，所以：

对于询问区间 ，答案就是：

这样我们就能在 时间内回答每个询问，总时间复杂度为 。

参考代码

• Python

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

def count_odd(n):
    # 计算区间 [1, n] 中奇数的个数
    return n - n // 3

T = int(input())
for _ in range(T):
    l, r = map(int, input().split())
    ans = count_odd(r) - count_odd(l - 1)
    print(ans)

• Cpp

#include <iostream>
using namespace std;
using ll = long long;

// 计算区间 [1, n] 中奇数的个数
ll count_odd(ll n) {
    return n - n / 3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        ll l, r;
        cin >> l >> r;
        
        // 区间 [l, r] 中奇数个数 = [1, r] - [1, l-1]
        ll ans = count_odd(r) - count_odd(l - 1);
        cout << ans << '\n';
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    // 计算区间 [1, n] 中奇数的个数
    public static long countOdd(long n) {
        return n - n / 3;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            long l = sc.nextLong();
            long r = sc.nextLong();
            
            // 区间 [l, r] 中奇数个数 = [1, r] - [1, l-1]
            long ans = countOdd(r) - countOdd(l - 1);
            System.out.println(ans);
        }
        
        sc.close();
    }
}

02. 智能配对系统优化

问题描述

小毛正在开发一个智能配对系统。系统中有两组长度为 的数据序列：用户偏好序列 和推荐序列 。

系统的"配对成功率"定义为满足 的位置对 的数量。

为了提升配对成功率，小毛设计了一套优化策略，包含两个阶段：

数据清理阶段（可选，至多执行一次）

• 可以选择一个位置 ，同时删除 和
• 删除后剩余元素保持相对顺序，形成长度为 的新序列

智能调整阶段

设当前序列长度为 ，对每个位置 按顺序执行以下操作（每步可选）：

1. 将 调整为 或保持不变
2. 将 调整为 或保持不变

请帮助小毛计算在最优策略下能够获得的最大配对成功率。

输入格式

第一行包含一个正整数 （），表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 （），表示序列长度
• 第二行包含 个正整数 （）
• 第三行包含 个正整数 （）

保证所有测试数据的 之和不超过 。

输出格式

对于每组测试数据，输出一行一个整数，表示能够获得的最大配对成功率。

样例输入

2
3
1 2 3
3 2 1
3
1 2 3
3 1 2

样例输出

2
0

数据范围

题解

这道题目需要我们理解调整规则的本质，并使用动态规划来求解最优策略。

首先分析调整规则：对于相邻两个位置 和 ，我们可以选择是否将位置 的值"更新"为位置 的值。这意味着我们可以让某些位置获得额外的配对机会。

关键观察：

1. 每个位置都有原地配对的机会（）
2. 相邻位置之间可以通过调整获得额外配对机会
3. 删除操作可能让原本不相邻的位置变成相邻

我们用动态规划来解决：

• ：处理前 个相邻对，未使用删除操作的最大收益
• ：处理前 个相邻对，已使用删除操作的最大收益

对于每个相邻对 ，计算所有可能调整方式的最大收益：

• 保持原样：（原地配对）
• 调整 ：检查
• 调整 ：检查
• 同时调整：检查

时间复杂度 ，空间复杂度 。

参考代码

• Python

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    # 计算每个位置的原地匹配
    d = [1 if a[i] == b[i] else 0 for i in range(n)]
    
    # 计算相邻位置的最大收益
    m = n - 1
    g = []
    for i in range(m):
        best = d[i]  # 原地匹配
        if b[i+1] == b[i]: best = max(best, 1)  # 调整 a[i]
        if a[i] == a[i+1]: best = max(best, 1)  # 调整 b[i]  
        if a[i+1] == b[i+1]: best = max(best, 1)  # 同时调整
        g.append(best)
    
    # 计算删除位置 k 后的跨越收益
    g_cross = [0] * n
    for k in range(1, n-1):
        best = d[k-1]  # 原地匹配
        if b[k+1] == b[k-1]: best = max(best, 1)
        if a[k-1] == a[k+1]: best = max(best, 1)
        if a[k+1] == b[k+1]: best = max(best, 1)
        g_cross[k] = best
    
    # 动态规划
    NEG = float('-inf')
    dp = [[NEG, NEG] for _ in range(m + 1)]
    dp[0][0] = 0
    
    for s in range(1, m + 1):
        dp[s][0] = dp[s-1][0] + g[s-1]
        dp[s][1] = dp[s-1][1] + g[s-1]
        
        if s >= 2:
            cross = dp[s-2][0] + g_cross[s-1]
            dp[s][1] = max(dp[s][1], cross)
        elif s == 1:
            dp[s][1] = max(dp[s][1], g_cross[s-1])
    
    ans = max(dp[m][0], dp[m][1]) + d[n-1]
    return ans

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        
        // 计算每个位置的原地匹配
        vector<int> d(n);
        for (int i = 0; i < n; i++) {
            d[i] = (a[i] == b[i]) ? 1 : 0;
        }
        
        int m = n - 1;
        vector<ll> g(m);
        
        // 计算相邻位置的最大收益
        for (int i = 0; i < m; i++) {
            ll best = d[i];
            best = max(best, (ll)(b[i+1] == b[i] ? 1 : 0));
            best = max(best, (ll)(a[i] == a[i+1] ? 1 : 0));
            best = max(best, (ll)(a[i+1] == b[i+1] ? 1 : 0));
            g[i] = best;
        }
        
        // 计算删除后的跨越收益
        vector<ll> g_cross(n, 0);
        for (int k = 1; k < n - 1; k++) {
            ll best = d[k-1];
            best = max(best, (ll)(b[k+1] == b[k-1] ? 1 : 0));
            best = max(best, (ll)(a[k-1] == a[k+1] ? 1 : 0));
            best = max(best, (ll)(a[k+1] == b[k+1] ? 1 : 0));
            g_cross[k] = best;
        }
        
        // 动态规划
        const ll NEG = LLONG_MIN / 4;
        vector<vector<ll>> dp(m + 1, vector<ll>(2, NEG));
        dp[0][0] = 0;
        
        for (int s = 1; s <= m; s++) {
            dp[s][0] = dp[s-1][0] + g[s-1];
            dp[s][1] = dp[s-1][1] + g[s-1];
            
            ll cross = (s >= 2 ? dp[s-2][0] : 0) + g_cross[s-1];
            dp[s][1] = max(dp[s][1], cross);
        }