✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：星际旅行计划

1️⃣：统计数组中值为1的元素数量

2️⃣：计算曼哈顿距离并判断奇偶性关系

难度：中等

这道题目的关键在于理解移动的特性，值为0的元素让我们原地不动，值为1的元素允许在四个方向上移动一步。通过数学分析，我们可以推导出一个O(n)的高效解法，无需模拟实际移动过程。

题目二：图论专家的连通图分析

1️⃣：将条件转化为数组元素与索引差值的大小关系

2️⃣：计算前缀最大值和后缀最小值

3️⃣：寻找可切分的位置计算连通块数量

难度：中等

这道题目通过巧妙的数学变换，将复杂的图论问题转化为序列分析问题。利用转换后的数组特性，我们可以高效地找出断开连通性的位置，从而求出极大连通块的数量，时间复杂度为O(n)。

题目三：双递增子序列划分问题

1️⃣：利用Dilworth定理将问题转化为不存在长度为3的不增子序列

2️⃣：预处理每个位置的左右不增边界

3️⃣：使用扫描线算法和树状数组高效处理多次查询

难度：中等偏难

这道题目结合了经典的序列分解理论和高效的数据结构。通过理论分析，将问题转化为判断是否存在特定模式，然后设计离线算法高效处理多次查询，时间复杂度为O((n+q)logn)。

01. 星际旅行计划

问题描述

小柯是一名星际探险家，她正在一个无限广阔的二维宇宙中规划航行路线。初始时，她的飞船位于坐标 。

她的飞船能量系统由 个能量单元组成，每个能量单元的值为 。当小柯使用第 个能量单元时，她必须选择两个整数 和 ，满足 ，然后飞船会移动到新的位置 。

小柯想知道，在使用完所有 个能量单元后，她是否能恰好到达目标坐标 ？

输入格式

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

对于每个测试用例：

• 第一行包含一个整数 ，表示能量单元的数量。
• 第二行包含 个整数，第 个整数为 ，表示每个能量单元的值。
• 第三行包含四个整数 ，分别表示起始坐标和目标坐标。

数据保证单个测试文件中 。

输出格式

对于每个测试用例输出一行，如果小柯能够恰好到达目标坐标 ，则输出 "YES"，否则输出 "NO"。

样例输入

2
2
0 0
1 1 1 1
3 
1 1 1
1 1 2 2

样例输出

YES
NO

样例1	在这个例子中，小柯有两个值为0的能量单元。使用第一个能量单元，她可以选择 原地不动；使用第二个能量单元，仍选择 。最终她仍停留在初始位置 ，恰好是目标坐标。
样例2	小柯有三个值为1的能量单元。无论如何选择，她无法从 正好到达 。

数据范围

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

题解

这道题目看似复杂，但实际上有一个很直观的解法。让我们分析一下：

首先，我们需要理解能量单元的使用方式。当 时，我们只能选择 和 ，即原地不动。当 时，我们有四种选择：、、 或 ，相当于在四个方向上移动一步。

所以，我们的移动能力受到两个因素限制：

1. 总共能移动多少步（由 的数量决定）
2. 每一步只能在四个正交方向上移动

从起点 到目标点 的最短曼哈顿距离是 。这意味着我们至少需要这么多步才能到达目标。

此外，每次移动都会改变奇偶性。考虑到这一点，能否到达目标还需满足一个条件：如果总移动步数减去最短距离后的剩余步数是奇数，那么我们永远无法到达目标。因为每多走两步才能回到同一个奇偶性的位置。

综合这两个条件，我们可以得出解题的关键判断：

• 设 为数组中值为1的元素数量（即可移动的步数）
• 设 , 为横纵坐标的距离
• 当且仅当 且 时，才能到达目标

时间复杂度：，我们只需要遍历一次数组来统计值为1的元素数量。 空间复杂度：，只需要常数额外空间。

参考代码

• Python

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

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        x, y, p, q = map(int, input().split())
        
        # 统计可移动的步数
        ones = sum(1 for val in a if val == 1)
        
        # 计算目标距离
        dx = abs(p - x)
        dy = abs(q - y)
        
        # 判断是否可达
        if ones >= dx + dy and (ones - (dx + dy)) % 2 == 0:
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    solve()

• Cpp

#include <iostream>
#include <cmath>
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;
        
        ll ones = 0;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            ones += (a == 1);
        }
        
        ll x, y, p, q;
        cin >> x >> y >> p >> q;
        
        ll dx = abs(p - x);
        ll dy = abs(q - y);
        
        if (ones >= dx + dy && (ones - (dx + dy)) % 2 == 0)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    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 t = Integer.parseInt(br.readLine().trim());
        
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String[] vals = br.readLine().trim().split(" ");
            
            long ones = 0;
            for (int i = 0; i < n; i++) {
                if (vals[i].equals("1")) ones++;
            }
            
            String[] coords = br.readLine().trim().split(" ");
            long x = Long.parseLong(coords[0]);
            long y = Long.parseLong(coords[1]);
            long p = Long.parseLong(coords[2]);
            long q = Long.parseLong(coords[3]);
            
            long dx = Math.abs(p - x);
            long dy = Math.abs(q - y);
            
            if (ones >= dx + dy && (ones - (dx + dy)) % 2 == 0)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

02. 图论专家的连通图分析

问题描述

小毛是一位图论爱好者，他正在研究一种特殊的无向图构建方法。他有一个长度为 的数组 ，他定义一对数字 是"和谐对"当且仅当： 且 。

小毛构建图的规则是：对于任意一对索引 和 （），如果 是和谐对，则在点 和点 之间连接一条无向边。

现在，小毛想知道他所构建的图中有多少个极大连通块。由于图中的边可能非常多，他希望你能帮他计算。

（注：对于图上的两个点，如果它们之间有边相连或者可以通过一系列边间接相连，则称它们位于同一个连通块中。对于一个连通块，如果无法再加入更多的点，则称其为极大连通块。）

输入格式

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

对于每个测试用例：

• 第一行包含一个整数 ，表示数组 的长度。
• 第二行包含 个正整数 ，表示数组 的元素。

数据保证单个测试文件中所有 的总和不超过 。

输出格式

对于每个测试用例输出一行，包含一个整数，表示图中极大连通块的数量。

样例输入

2
4
3 3 4 6
5
1 2 3 4 5

样例输出

2
5

样例1	对于数组 ，构建的图有两个极大连通块。根据和谐对的定义，点 1 和点 3、点 1 和点 4、点 2 和点 3、点 2 和点 4 之间有边，形成一个连通块；而点 3 和点 4 之间没有边，单独形成另一个连通块。
样例2	对于数组 ，每个点都是一个独立的连通块，因为没有任何点对满足和谐对的定义。

数据范围

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

题解

这道题目看似复杂，但通过数学变换可以找到一个优雅的解法。

首先，分析一下"和谐对"的条件：

我们可以将其变形为：

定义一个新的数组 ，其中 ，则条件变为：（当 时）

这意味着，我们在所有形成"逆序对"的位置 且 之间连边。这种特殊的图结构的连通块数量等价于将序列 切分为若干段，使得每一段内部存在逆序对，而不同段之间没有逆序对。

当某个位置 满足以下条件时，可以在 和 之间"断开"连通性：

最终的连通块数就是这样的切分段数。

我们可以通过以下步骤求解：

1. 计算后缀最小值
2. 从左到右遍历，维护前缀最大值
3. 每当 时，就可以在位置 和 之间切分，连通块数量加一

时间复杂度：，我们只需要两次遍历数组 空间复杂度：，需要额外存储转换后的数组和后缀最小值

参考代码

• Python

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

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = [0] + list(map(int, input().split()))
        
        # 计算b[i] = a[i] - i
        b = [0] * (n + 1)
        for i in range(1, n + 1):
            b[i] = a[i] - i
        
        # 计算后缀最小值
        suffix_min = [float('inf')] * (n + 2)
        for i in range(n, 0, -1):
            suffix_min[i] = min(b[i], suffix_min[i + 1])
        
        # 扫描切分
        prefix_max = b[1]
        comps = 1  # 至少有一个连通块
        
        for i in range(1, n):
            prefix_max = max(prefix_max, b[i])
            if prefix_max <= suffix_min[i + 1]:
                comps += 1
        
        print(comps)

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
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;
        
        // 读取数组并计算b[i] = a[i] - i
        vector<ll> b(n + 1);
        for (int i = 1; i <= n; i++) {
            ll a;
            cin >> a;
            b[i] = a - i;
        }
        
        // 计算后缀最小值
        vector<ll> suffix_min(n + 2, LLONG_MAX);
        for (int i = n; i >= 1; i--) {
            suffix_min[i] = min(b[i], suffix_min[i + 1]);
        }
        
        // 扫描切分
        ll prefix_max = b[1];
        int comps = 1;  // 至少有一个连通块
        
        for (int i = 1; i < n; i++) {
            prefix_max = max(prefix_max, b[i]);
            if (prefix_max <= suffix_min[i + 1]) {
                comps++;
            }
        }
        
        cout << comps << "\n";
    }
    
    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 t = Integer.parseInt(br.readLine().trim());
        
        while (t-- > 0) {
            int n = Integer.parseInt