✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：艺术画框排列

1️⃣：分析画框的两种放置方式（横放和竖放）

2️⃣：根据高度限制选择占用宽度最小的放置方式

3️⃣：累加所有画框的宽度贡献得到最终答案

难度：简单

这道题目考查贪心算法的基本应用。对于每幅画框，在满足高度限制的前提下选择宽度最小的放置方式。关键在于理解两种放置方式的宽度和高度关系，然后做出最优选择。时间复杂度O(n)，实现简单直观。

题目二：魔法宝石收藏

1️⃣：理解按位与运算的性质，分析核心宝石的二进制表示

2️⃣：对核心宝石值为0的每个二进制位构造新宝石

3️⃣：利用位运算特性保证任意两宝石按位与结果等于核心宝石值

难度：中等

这道题目的关键在于理解按位与运算的性质。通过分析核心宝石的二进制表示，发现可以通过将值为0的位逐个设为1来构造新宝石，使得任意两个宝石的按位与结果都等于核心宝石值。算法时间复杂度为O(20)，空间复杂度为O(1)，是一个巧妙的位运算应用题。

题目三：城市网络监控系统

1️⃣：使用重心分解技术对树进行预处理，构建分治树

2️⃣：维护每个重心的警戒节点计数和距离总和信息

3️⃣：利用容斥原理处理查询，实现O(log n)的单次操作复杂度

难度：困难

这道题目是树上动态查询的经典问题，需要掌握点分治（重心分解）这一高级数据结构。算法涉及重心寻找、分治树构建、容斥原理等多个知识点。实现复杂度较高，但时间效率优秀。适合有扎实算法基础的高级选手挑战。

01. 艺术画框排列

问题描述

小毛是一位艺术画廊的策展人，他收到了 幅珍贵的艺术画作。每幅画作都已经装裱在精美的矩形画框中，第 幅画的画框尺寸为长 ，宽 。

现在小毛需要在画廊的一面特殊展示墙上按顺序排列这些画作。这面墙有以下特点：

1. 墙面高度有限，最大高度为

2. 所有画框必须紧贴地面排列，不能悬空

3. 每幅画都可以选择横放或竖放（即可以旋转90度）

4. 画框之间不能重叠，必须紧密相邻排列

小毛希望计算出按照给定顺序排列所有画作时，最少需要占用多长的墙面宽度。

保证每幅画至少有一种放置方式能够满足高度限制。

输入格式

第一行包含两个正整数 （，），分别表示画作的数量和墙面的最大高度。

接下来 行，每行包含两个正整数 （），表示第 幅画的画框尺寸。

输出格式

输出一个整数，表示排列所有画作时需要占用的最小墙面宽度。

样例输入

3 4
1 2
2 5
4 2

样例输出

8

数据范围

• 

• 

• 

• 保证

样例	解释说明
样例1	第1幅画可以选择高度较小的方向放置（高度2），占用宽度1；第2幅画只能以高度2放置，占用宽度5；第3幅画选择高度较小的方向放置，占用宽度2。总宽度为1+5+2=8

题解

这道题目的核心思想很直观：对于每幅画，选择一个合适的放置方向使得占用的宽度最小，同时满足高度限制。

关键观察：对于一幅尺寸为 和 的画框，有两种放置方式：

1. 横放：高度为 ，宽度为

2. 竖放：高度为 ，宽度为

策略分析：

• 如果两种放置方式的高度都不超过墙面高度 ，那么应该选择占用宽度较小的那种方式，即竖放（宽度为 ）

• 如果只有一种放置方式满足高度限制，那么只能选择那种方式

具体算法：

1. 对于每幅画，计算两个尺寸的最大值和最小值

2. 如果最大值不超过 ，说明两种放置方式都可行，选择宽度较小的竖放方式，贡献

3. 否则只能选择横放方式，贡献

4. 将所有画作的宽度贡献相加得到答案

时间复杂度 ，对于每幅画只需要进行常数次比较操作。空间复杂度 。

需要注意使用64位整数避免溢出，因为最坏情况下答案可能达到 。

参考代码

• Python

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

def solve():
    """求解艺术画框排列问题"""
    n, m = map(int, input().split())
    
    total_width = 0  # 总宽度
    
    for _ in range(n):
        x, y = map(int, input().split())
        
        # 计算两个尺寸的最大值和最小值
        max_size = max(x, y)
        min_size = min(x, y)
        
        # 如果最大尺寸不超过高度限制，选择宽度较小的放置方式
        if max_size <= m:
            width = min_size  # 竖放，宽度为较小值
        else:
            width = max_size  # 只能横放，宽度为较大值
        
        total_width += width
    
    print(total_width)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    long long m;
    cin >> n >> m;
    
    long long ans = 0;  // 总宽度
    
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        
        // 计算最大值和最小值
        long long max_val = max(x, y);
        long long min_val = min(x, y);
        
        // 选择最优放置方式
        if (max_val <= m) {
            ans += min_val;  // 竖放
        } else {
            ans += max_val;  // 横放
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        
        String[] firstLine = reader.readLine().split(" ");
        int frameNum = Integer.parseInt(firstLine[0]);
        long maxHeight = Long.parseLong(firstLine[1]);
        
        long totalWidth = 0;  // 记录总宽度
        
        for (int i = 0; i < frameNum; i++) {
            String[] sizeLine = reader.readLine().split(" ");
            long sizeA = Long.parseLong(sizeLine[0]);
            long sizeB = Long.parseLong(sizeLine[1]);
            
            // 计算尺寸的最大值和最小值
            long biggerSize = Math.max(sizeA, sizeB);
            long smallerSize = Math.min(sizeA, sizeB);
            
            // 根据高度限制选择放置方式
            if (biggerSize <= maxHeight) {
                totalWidth += smallerSize;  // 可以竖放
            } else {
                totalWidth += biggerSize;   // 只能横放
            }
        }
        
        System.out.println(totalWidth);
    }
}

02. 魔法宝石收藏

问题描述

小兰是一位热爱收集魔法宝石的法师。她拥有一颗特殊的核心宝石，这颗宝石具有独特的魔法能量值 （）。

现在小兰想要组建一个"和谐宝石阵"，这个宝石阵需要满足以下条件：

1. 阵中每颗宝石的魔法能量值都在 范围内

2. 阵中任意两颗宝石的魔法能量值都不相同

3. 对于阵中任意两颗不同的宝石，它们的魔法能量值进行"魔法共鸣"运算（按位与运算）后，结果必须等于核心宝石的魔法能量值

小兰希望找到最长的和谐宝石阵，请帮助她构造出这样的宝石阵。

输入格式

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

接下来 行，每行包含一个非负整数 （），表示核心宝石的魔法能量值。

输出格式

对于每组测试数据，首先输出一行整数 （），表示和谐宝石阵中宝石的数量。

第二行输出 个空格分开的非负整数，表示宝石阵中每颗宝石的魔法能量值（输出顺序任意）。

如果存在多种长度相同的最优方案，输出其中任意一种即可。

样例输入

2
1048575
1048573

样例输出

1
1048575
2
1048573 1048575

数据范围

• 

• 

• 输出的宝石阵长度

样例	解释说明
样例1	当核心宝石能量值为 时，所有二进制位都是1，无法构造长度超过1的和谐宝石阵，直接输出核心宝石本身
样例2	当核心宝石能量值为 时，可以构造包含 和 的宝石阵，因为

题解

这道题目的核心思想其实很巧妙。首先需要理解题目要求：对于和谐宝石阵中任意两颗宝石，它们的魔法能量值进行按位与运算后都要等于核心宝石的能量值 。

让我们从核心宝石的二进制表示入手分析。假设 的二进制表示中，值为 0 的位有 个。

关键观察：

1. 和谐宝石阵中一定要包含核心宝石本身（能量值为 ）

2. 对于 二进制表示中每个值为 0 的位置 ，可以构造一个新的宝石，其能量值为 （即只将第 位从 0 变为 1）

3. 这样构造出来的宝石之间满足条件：任意两个宝石的按位与结果都等于

为什么这个方法有效？

• 核心宝石 与任何其他宝石进行按位与，结果都是 （因为其他宝石都是在 基础上某些0位变成1）

• 两个不同的构造宝石之间进行按位与：它们在 原本为 1 的位置仍然是 1，在各自新增的 1 位（原本 为 0 的不同位置）会变成 0，结果恰好是

具体算法步骤：

1. 将核心宝石 加入宝石阵

2. 遍历 的每一个二进制位（从低位到高位）

3. 如果第 位为 0，就构造新宝石 并加入宝石阵

4. 输出宝石阵的长度和所有宝石的能量值

时间复杂度为 ，因为最多需要检查 20 个二进制位。宝石阵的最大长度为 21（核心宝石 + 最多 20 个构造宝石），远小于题目限制的 100。

参考代码

• Python

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

# 主函数处理多组测试数据
def solve():
    t = int(input())  # 读取测试数据组数
    
    for _ in range(t):
        z = int(input())  # 读取核心宝石能量值
        stones = [z]  # 初始化宝石阵，包含核心宝石
        
        # 检查z的每个二进制位
        for i in range(20):
            # 如果第i位为0，构造新宝石
            if not (z >> i & 1):
                new_val = z | (1 << i)  # 将第i位设为1
                stones.append(new_val)
        
        # 输出结果
        print(len(stones))
        print(' '.join(map(str, stones)))

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;  // 读取测试数据组数
    
    while (t--) {
        int z;
        cin >> z;  // 读取核心宝石能量值
        
        vector<int> gems;  // 存储宝石阵
        gems.push_back(z);  // 加入核心宝石
        
        // 遍历20个二进制位
        for (int bit = 0; bit < 20; bit++) {
            // 检查第bit位是否为0
            if ((z >> bit & 1) == 0) {
                int new_gem = z | (1 << bit);  // 构造新宝石
                gems.push_back(new_gem);
            }
        }
        
        // 输出宝石阵大小
        cout << gems.size() << "\n";
        
        // 输出所有宝石的能量值
        for (int i = 0; i < gems.size(); i++) {
            if (i > 0) cout << " ";
            cout << gems[i];
        }
        cout << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());  // 读取测试数据组数
        
        while (testCase-- > 0) {
            int coreVal = Integer.parseInt(br.readLine());  // 读取核心宝石能量值
            List<Integer> magicArr = new ArrayList<>();  // 存储宝石阵
            
            magicArr.add(coreVal);  // 添加核心宝石
            
            // 检查每个二进制位位置
            for (int pos = 0; pos < 20; pos++) {
                // 如果第pos位为0，创建新宝石
                if ((coreVal >> pos & 1) == 0) {
                    int newGem = coreVal | (1 << pos);  // 设置第pos位为1
                    magicArr.add(newGem);
                }
            }
            
            // 输出宝石阵大小
            System.out.println(magicArr.size());
            
            // 输出所有宝石能量值
            for (int idx = 0; idx < magicArr.size(); idx++) {
                if (idx > 0) System.out.print(" ");
                System.out.print(magicArr.get(idx));
            }
            System.out.println();
        }
    }
}

03. 城市网络监控系统

问题描述

小柯负责管理一个智慧城市的网络监控系统。这个城市有 个关键节点，它们通过道路网络连接成一棵树状结构，其中节点 是中央控制中心。每条道路都有一定的长度，表示为正整数权重。

在这个监控系统中，某些节点被设置为"警戒状态"，用于重点监控。系统需要支持两种动态操作：

1. 状态切换：将某个节点的警戒状态进行切换（从警戒状态变为普通状态，或从普通状态变为警戒状态）

2. 距离查询：查询某个指定节点到所有当前处于警戒状态的节点的道路距离总和

小柯需要你帮助她设计一个高效的系统来处理这些操作。

输入格式

第一行包含两个正整数 （），分别表示节点数量和操作次数。

第二行包含 个整数 ，其中 。 表示第 个节点初始处于警戒状态， 表示普通状态。

接下来 行，每行包含三个正整数 （，，），表示节点 和 之间有一条长度为 的道路。

随后 行，每行包含两个整数 和 （，），表示一次操作：

• 当 时，表示切换节点 的警戒状态
• 当 时，表示查询节点 到所有警戒状态节点的距离总和

输出格式

对于每个类型为 的查询操作，输出一行整数，表示查询结果。

样例输入

5 5
1 0 1 0 1
1 2 1
1 3 2
3 4 3
3 5 4
2 1
2 2
1 3
2 2
2 2

样例输出

8
11
8
8

数据范围

• 

• 

• ，

• 

• 保证输入构成一棵树

• 至少存在一个类型为 的查询操作

样例	解释说明
样例1	初始警戒节点为{1,3,5}。查询1到警戒节点距离：0+2+6=8。查询2到警戒节点距离：1+3+7=11。切换节点3状态后，警戒节点变为{1,5}。查询2到警戒节点距离：1+7=8

题解

这是一个经典的树上动态查询问题。需要高效地处理节点状态的动态变化和距离查询。

核心思想是使用**点分治（重心分解）**技术：

1. 重心分解预处理：

   • 对原树进行重心分解，构建一棵分治树
   • 每个原树节点在分治树中对应一条到根的路径
   • 预处理每个节点到其分治树路径上各重心的距离

2. 状态维护：

   • 对每个重心维护两个信息：
     • cnt[c]：当前有多少个警戒节点在重心c的子树中
     • sum[c]：这些警戒节点到重心c的距离总和

3. 状态切换操作：

   • 沿着节点v在分治树中的路径，更新每个重心的信息
   • 时间复杂度：O(log n)

4. 距离查询操作：

   • 沿着节点v在分治树中的路径，累加距离贡献
   • 对每个重心c，贡献为：sum[c] + cnt[c] * dist(v,c)
   • 需要使用容斥原理避免重复计算
   • 时间复杂度：O(log n)

关键优化：使用容斥原理处理重复计算。对于分治树上的路径，需要减去子树内部的贡献，只保留外部的贡献。

整体时间复杂度：预处理O(n log n)，单次操作O(l