✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

美团

题目一：智能配对系统

1️⃣：理解异或运算的奇偶性规律：两数异或为奇数当且仅当奇偶性不同

2️⃣：分析约束条件：奇数位置需要偶数，偶数位置需要奇数

3️⃣：判断可行性：只有n为偶数时才有解，构造方案为相邻数对交换

难度：中等

这道题的核心在于理解异或运算与奇偶性的关系。通过数学分析发现，要使位置编号与用户编号的异或为奇数，必须保证它们奇偶性不同。当n为偶数时，可以通过简单的相邻交换策略构造出合法解。

题目二：推荐系统效果评估

1️⃣：解析JSON格式输入，提取查询数据和截断参数k

2️⃣：对每个查询按置信度得分降序排序，计算累积精度

3️⃣：实现AP@k公式计算，最后求所有查询的平均值得到MAP@k

难度：中等

这道题目结合了信息检索理论与编程实现，需要准确理解AP@k和MAP@k的计算公式。关键是正确处理排序、精度累积和边界情况（如无相关文档的查询），体现了对推荐系统评估指标的深入理解。

题目三：古董收藏箱整理

1️⃣：利用数列快速增长的性质，发现实际可用的立方体数量有限（≤19个）

2️⃣：预处理所有可能的子集组合，计算每个子集的约束参数

3️⃣：使用树状数组和双指针技术，离线处理查询实现高效统计

难度：中等偏难

这道题的巧妙之处在于发现数列增长的数学性质，将看似复杂的组合问题转化为可枚举的规模。通过预处理+离线查询的方式，结合高效的数据结构，实现了在给定时间复杂度内的最优解。

题目四：网络连接状态监控

1️⃣：使用LCA（最近公共祖先）算法处理树上路径操作

2️⃣：通过差分数组技术批量处理路径激活，避免重复计算

3️⃣：应用连通分量计数公式：连通块数=节点数-内部边数

难度：中等偏难

这道题考查了树上算法的综合应用，包括LCA预处理、差分数组优化和连通分量理论。通过离线处理所有操作，将复杂的动态维护问题转化为静态统计问题，体现了算法设计中化动为静的重要思想。

01. 智能配对系统

问题描述

小兰在开发一个智能配对系统，该系统需要处理 个用户的配对请求。每个用户都有一个唯一的身份编号 ，系统需要为他们安排座位。

系统的特殊之处在于，它要求每个座位位置 （从 开始编号）上的用户编号 满足一个特殊条件：位置编号与用户编号进行二进制异或运算后必须是奇数，即 必须为奇数。

这样的安排能够最大化用户间的兼容性。现在请你帮助小兰设计一个座位安排方案。

输入格式

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

接下来 行，每行包含一个正整数 （），表示用户数量。

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

输出格式

对于每组测试数据，输出一行：

• 如果存在满足条件的座位安排，输出 个整数，表示座位 上对应的用户编号，数字之间用空格分隔。

• 如果不存在满足条件的安排，输出 。

样例输入

2
1
2

样例输出

-1
2 1

数据范围

• 

• 

• 保证单个测试文件中所有 的和不超过

样例	解释说明
样例1	对于 ，座位1上只能安排用户1，但 为偶数，不满足条件，因此无解
样例2	座位安排为 ：座位1安排用户2，；座位2安排用户1，，均为奇数，满足条件

题解

这道题的关键在于理解异或运算的奇偶性规律。当两个数进行异或运算时，结果为奇数当且仅当这两个数的奇偶性不同。

具体分析：

• 如果座位编号 是奇数，那么用户编号 必须是偶数，这样 才是奇数
• 如果座位编号 是偶数，那么用户编号 必须是奇数

因此，要满足条件需要：

1. 奇数座位的数量 = 偶数用户编号的数量
2. 偶数座位的数量 = 奇数用户编号的数量

在 到 的序列中：

• 当 为奇数时：奇数个数 = ，偶数个数 = ，无法满足条件
• 当 为偶数时：奇数个数 = 偶数个数 = ，可以满足条件

构造方法很简单：将相邻的数对进行交换，即 。

时间复杂度：每个测试用例 ，总体复杂度 。

参考代码

• Python

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

def solve():
    # 读取测试用例数量
    t = int(input())
    
    for _ in range(t):
        n = int(input())
        
        # 如果n为奇数，无解
        if n & 1:
            print(-1)
            continue
        
        # 构造解：相邻数对交换
        ans = []
        for i in range(1, n + 1, 2):
            ans.append(i + 1)  # 先放偶数
            ans.append(i)      # 再放奇数
        
        print(' '.join(map(str, ans)))

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 n;
        cin >> n;
        
        // 如果n为奇数，无解
        if (n & 1) {
            cout << -1 << '\n';
            continue;
        }
        
        // 构造解：相邻数对交换
        vector<int> ans;
        for (int i = 1; i <= n; i += 2) {
            ans.push_back(i + 1);  // 先放偶数
            ans.push_back(i);      // 再放奇数
        }
        
        for (int i = 0; i < n; i++) {
            if (i > 0) cout << ' ';
            cout << ans[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 t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            
            // 如果n为奇数，无解
            if ((n & 1) == 1) {
                System.out.println(-1);
                continue;
            }
            
            // 构造解：相邻数对交换
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= n; i += 2) {
                if (i > 1) sb.append(' ');
                sb.append(i + 1).append(' ').append(i);  // 先偶数后奇数
            }
            
            System.out.println(sb.toString());
        }
    }
}

02. 推荐系统效果评估

问题描述

小基正在为公司的推荐系统开发一个效果评估工具。该工具需要计算推荐系统在多个查询上的平均精度指标。

对于每个用户查询，系统会返回一系列推荐结果，每个结果都有一个相关性标签（1表示相关，0表示不相关）和一个置信度得分。小基需要计算在截断位置 处的平均平均精度（）。

具体计算方法如下：

第一步：计算单查询的

对于某个查询，将推荐结果按置信度得分降序排列，取前 个结果。设第 个位置的相关性标签为 ，则：

其中 是该查询的总相关结果数。如果 ，则 。

第二步：计算

其中 是查询总数。

输入格式

输入为单行 JSON 格式，包含：

• ：截断位置（）
• ：查询列表，每个查询包含：
  • ：相关性标签数组（只含0或1）
  • ：置信度得分数组（任意实数）

输出格式

输出一行实数，表示 的值，四舍五入保留6位小数。

样例输入

{"k":3,"queries":[{"labels":[1,0,0],"scores":[0.9,0.8,0.7]},{"labels":[0,1,0],"scores":[0.9,0.8,0.7]}]}

样例输出

0.750000

数据范围

• 

• 查询数量

• 每个查询的标签和得分数组长度相等且

• 标签数组只含0或1

• 得分数组为任意实数

样例	解释说明
样例1	第一个查询按得分排序后标签为[1,0,0]，；第二个查询按得分排序后标签为[0,1,0]，；因此

题解

这道题考查对信息检索评估指标的理解和实现能力。关键步骤如下：

1. 解析JSON输入：提取截断位置k和所有查询的标签、得分信息。

2. 处理每个查询：

   • 将标签和得分配对，按得分降序排序
   • 计算该查询的总相关文档数R
   • 如果R=0，直接设AP=0；否则继续计算

3. 计算AP@k：

   • 遍历前k个位置（或实际长度）
   • 维护累积相关文档数
   • 当当前位置相关时，累加 当前精度 到分子
   • 最后除以min(k,R)得到AP值

4. 计算MAP@k：所有查询的AP值求平均

时间复杂度：设总文档数为M，排序需要O(M log M)，其余操作为线性时间。

参考代码

• Python

import json
import sys

def solve():
    # 读取输入并解析JSON
    data = json.loads(sys.stdin.readline().strip())
    k = data['k']
    queries = data['queries']
    
    ap_vals = []
    
    for query in queries:
        labels = query['labels']
        scores = query['scores']
        
        # 将标签和得分配对并按得分降序排序
        pairs = sorted(zip(scores, labels), key=lambda x: -x[0])
        
        # 计算总相关文档数
        total_rel = sum(labels)
        
        if total_rel == 0:
            ap_vals.append(0.0)
            continue
        
        # 计算AP@k
        max_pos = min(k, len(pairs))
        rel_sum = 0
        ap_sum = 0.0
        
        for pos in range(max_pos):
            rel_sum += pairs[pos][1]
            if pairs[pos][1] == 1:  # 当前位置相关
                prec = rel_sum / (pos + 1)
                ap_sum += prec
        
        ap_val = ap_sum / min(k, total_rel)
        ap_vals.append(ap_val)
    
    # 计算MAP@k
    map_k = sum(ap_vals) / len(ap_vals)
    print(f"{map_k:.6f}")

solve()

03. 古董收藏箱整理

问题描述

小毛是一位古董收藏家，他收集了 个特殊的古董立方体。这些立方体的边长遵循一个神秘的数列规律：第 个立方体的边长为 ，其中 是黄金比例数列的第 项。

这个数列的定义如下：

小毛有 个收纳盒，第 个盒子的尺寸为长 、宽 、高 。由于古董的特殊性质，立方体的摆放需要满足两个严格的条件：

1. 尺寸限制：选中的立方体中最大边长不能超过盒子的长和宽中的较小值，即：

2. 重量限制：所有选中立方体的边长之和不能超过盒子的高度，即：

对于每个收纳盒，请计算有多少种不同的立方体组合方案能够满足上述条件。

输入格式

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

对于每组测试数据：

第一行包含两个正整数 （, ），分别表示立方体数量和收纳盒数量。

接下来 行，每行包含三个正整数 （），表示第 个收纳盒的宽度、长度和高度。

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

输出格式

对于每组测试数据，输出一行包含 个整数，第 个整数表示第 个收纳盒能容纳的不同立方体组合方案数。

样例输入

1
3 3
3 5 7
1 1 1
2 3 3

样例输出

7 1 3

数据范围

• 

• 

• 

• 

• 保证单个测试文件中所有 的和不超过

样例	解释说明
样例1	对于 ，数列为 。第一个盒子 限制为 ，，所有非空子集都满足条件，共 种方案

题解

这道题的核心是子集枚举和约束检查。由于黄金比例数列增长很快，当数值超过 时就无法放入任何盒子，因此实际需要考虑的立方体数量很少（不超过19个）。

关键观察：

• 黄金比例数列快速增长：，
• 无论 多大，真正可能装入盒子的立方体最多19个

算法思路：

1. 预处理所有子集：枚举所有非空子集（最多 个）
2. 离线处理：对每个子集计算最大边长、边长和、最大索引
3. 排序优化：将子集按最大边长排序，盒子按尺寸限制排序
4. 树状数组统计：使用Fenwick树维护满足尺寸限制的子集中符合重量限制的数量

具体步骤：

• 将盒子按 升序排序
• 使用双指针：当盒子的尺寸限制增大时，将更多子集加入树状数组
• 对每个盒子查询树状数组中边长和 的子集数量

时间复杂度：预处理 ，每组测试 ，其中 。

参考代码

• Python

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

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, val):
        i += 1  # 1-indexed
        while i <= self.n:
            self.tree[i] += val
            i += i & (-i)
    
    def query(self, i):
        i += 1  # 1-indexed
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res

def solve():
    # 预计算数列（最多到边长10000）
    fib = [0, 1, 2]  # 1-indexed, fib[0]为占位
    while True:
        next_val = fib[-1] + fib[-2]
        if next_val > 10000:
            break
        fib.append(next_val)
    
    max_cubes = len(fib) - 1  # 实际可用的立方体数
    
    # 预处理所有非空子集
    subsets = []
    for mask in range(1, 1 << max_cubes):
        max_edge = 0
        sum_edge = 0
        max_idx = 0
        
        for i in range(max_cubes):
            if mask & (1 << i):
                val = fib[i + 1]
                max_edge = max(max_edge, val)
                sum_edge += val
                max_idx = i + 1
        
        if sum_edge <= 10000:  # 过滤无用子集
            subsets.append((max_edge, sum_edge, max_idx))
    
    # 按最大边长排序
    subsets.sort()
    
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        
        boxes = []
        for j in range(m):
            w, l, h = map(int, input().split())
            boxes.append((min(w, l), h, j))
        
        # 按尺寸限制排序
        boxes.sort()
        
        # 使用树状数组统计
        ft = FenwickTree(10000)
        ans = [0] * m
        
        ptr = 0  # 子集指针
        for lim, h, orig_idx in boxes:
            # 加入所有满足尺寸限制的子集
            while ptr < len(subsets) and subsets[ptr][0] <= lim:
                max_edge, sum_edge, max_idx = subsets[ptr]
                if max_idx <= n:  # 确保索引不超过n
                    ft.update(sum_edge, 1)
                ptr += 1
            
            # 查询满足重量限制的子集数
            ans[orig_idx] = ft.query(min(h, 10000))
        
        print(' '.join(map(str, ans)))

solve()

• Cpp

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

struct FenwickTree {
    int n;
    vector<int> tree;
    
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
    
    void update(int i, int val) {
        for (++i; i <= n; i += i & -i) {
            tree[i] += val;
        }
    }
    
    int query(int i) {
        int res = 0;
        for (++i; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }
};

struct Subset {
    int max_edge, sum_edge, max_idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 预计算数列
    vector<int> fib = {0, 1, 2};  // 1-indexed
    while (true) {
        int next_val = fib.back() + fib[fib.size() - 2];
        if (next_val > 10000) break;
        fib.push_back(ne