✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

百度-第二套

题目一：密码配对系统

1️⃣：理解异或运算性质，找到使所有ai⊕bi相等的常数C

2️⃣：为了使字典序最小，令C = a1，使得b1 = 0

3️⃣：计算bi = ai ⊕ a1得到最优解

难度：简单

这道题目的关键在于理解异或运算的性质和字典序优化。通过选择合适的常数C，可以保证所有位置的异或值相等，而选择C = a1可以使第一个元素b1 = 0，从而保证字典序最小。

题目二：投资收益分析

1️⃣：计算收益值bi = ai - i，转化为统计bi + bj > 0的对数

2️⃣：使用离散化处理值域范围

3️⃣：利用树状数组维护已处理元素，快速查询满足条件的个数

难度：中等

这道题目结合了数学转化和高效数据结构的应用。通过将问题转化为查询大于某个阈值的元素个数，再使用树状数组实现O(log n)的单次查询，整体达到O(n log n)的时间复杂度。

题目三：信号传输验证系统

1️⃣：理解按位或运算的单调性质

2️⃣：从后往前预处理后缀OR值

3️⃣：从前往后验证每个位置的两个必要条件

难度：中等

这道题目需要深入理解按位或运算的性质。关键洞察是OR运算的不可逆性：一旦某位被设置为1就无法变回0。通过维护前缀和后缀的OR值，可以有效判断每个目标值是否可达。

01. 密码配对系统

问题描述

小基 正在设计一个密码配对系统。她有一个长度为 的原始密码序列 ，现在需要构造一个对应的配对密码序列 。

系统的安全要求是：对于所有的位置 ，都必须满足 成立，其中 表示按位异或运算。

为了便于记忆，小基 希望配对密码序列 的字典序尽可能小。请你帮她找出满足条件的字典序最小的配对密码序列。

字典序定义：从两个序列的第一个元素开始逐个比较，直到找到第一个不同的元素，较小元素所在的序列字典序更小。如果比较到其中一个序列的结尾时依旧完全相同，则较短的序列字典序更小。

输入格式

第一行包含一个正整数 （），表示密码序列的长度。

第二行包含 个非负整数 （），表示原始密码序列。

输出格式

输出一行，包含 个非负整数，表示满足条件的字典序最小的配对密码序列 。

样例输入

6
1 1 4 5 1 4

样例输出

0 0 5 4 0 5

样例	解释说明
样例1	取 ，则 。验证：，，，以此类推，所有位置的异或值都等于1，且 序列字典序最小。

数据范围

• 
• 

题解

这道题的关键在于理解异或运算的性质和字典序的优化策略。

首先分析题目要求：要使得对所有下标 都有 成立，这意味着所有的 都必须等于同一个常数，不妨记这个常数为 。

那么对于每个位置 ，都有：

这样整个配对序列 就被常数 唯一确定了。现在的问题转化为：如何选择 使得序列 的字典序最小？

字典序比较的关键在于从左到右逐位比较。要使字典序最小，首先要让 尽可能小。由于 ，要使 最小，显然应该取 ，这样 ，达到了可能的最小值。

此时整个序列为：

容易验证这个解的正确性： 对所有 都成立。

而且这确实是字典序最小的解，因为任何其他的 值都会导致 ，从而字典序更大。

算法步骤：

1. 读入序列
2. 设置
3. 计算 对所有
4. 输出序列

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

参考代码

• Python

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

def solve():
    n = int(input())  # 读取序列长度
    a = list(map(int, input().split()))  # 读取原始密码序列
    
    # 选择常数C为a[0]，使得b[0] = 0，保证字典序最小
    c = a[0]
    
    # 计算配对密码序列
    res = []
    for i in range(n):
        # b[i] = a[i] ^ c，其中c = a[0]
        res.append(a[i] ^ c)
    
    # 输出结果
    print(' '.join(map(str, res)))

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;  // 读取序列长度
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];  // 读取原始密码序列
    }
    
    // 选择常数c为a[0]，使得b[0] = 0，保证字典序最小
    int c = a[0];
    
    // 计算并输出配对密码序列
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        // b[i] = a[i] ^ c，其中c = a[0]
        cout << (a[i] ^ c);
    }
    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 n = Integer.parseInt(br.readLine());  // 读取序列长度
        String[] tokens = br.readLine().split(" ");
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(tokens[i]);  // 读取原始密码序列
        }
        
        // 选择常数c为a[0]，使得b[0] = 0，保证字典序最小
        int c = a[0];
        
        // 计算并输出配对密码序列
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(" ");
            // b[i] = a[i] ^ c，其中c = a[0]
            sb.append(a[i] ^ c);
        }
        
        System.out.println(sb.toString());
    }
}

02. 投资收益分析

问题描述

小兰是一名投资分析师，她手里有一个长度为 的投资项目评分数组 。由于投资是有时间成本的，她定义每个项目 的实际收益值为 （其中 表示投资的时间成本）。

现在小兰想要统计所有满足 且 的项目对 的数量，这样的组合表示两个项目的合作收益为正，值得考虑投资。

输入格式

每个测试文件包含多组测试数据。

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

对于每组测试数据：

第一行包含一个整数 （），表示投资项目的数量。

第二行包含 个整数 （），表示各个项目的评分。

除此之外，保证单个测试文件的所有 之和不超过 。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的项目对数量。

样例输入

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

样例输出

4
2

样例	解释说明
样例1	，，。满足 的对有：、、、，共4对。
样例2	，，。满足 的对有：、，共2对。

数据范围

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

题解

这道题的核心是要统计满足 且 的有序对数量，其中 。

直接的暴力算法是枚举所有 的对，但时间复杂度为 ，对于 的数据会超时。

我们需要一个更高效的算法。关键观察是：对于固定的 ，我们要统计有多少个 满足 ，即 。

这提示我们可以用数据结构来维护已经处理过的 值，并快速查询有多少个值大于某个阈值。

算法思路：

1. 计算所有的
2. 将所有可能出现的 和 值收集起来并离散化
3. 使用树状数组（Fenwick Tree）来维护已经出现的 值的计数
4. 从左到右遍历每个位置 ：
   • 查询树状数组中有多少个值严格大于
   • 将这个计数加到答案中
   • 将 加入到树状数组中

具体实现细节：

• 使用离散化将值映射到较小的坐标范围
• 树状数组支持单点更新和前缀查询
• 通过前缀查询的差值来得到区间查询结果

时间复杂度：，主要瓶颈在离散化的排序和树状数组操作。

参考代码

• Python

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

class BIT:
    def __init__(self, n):
        self.n = n  # 树状数组大小
        self.tree = [0] * (n + 1)  # 树状数组
    
    def update(self, idx, val):
        # 单点更新：在位置idx增加val
        while idx <= self.n:
            self.tree[idx] += val
            idx += idx & (-idx)  # 移动到下一个需要更新的位置
    
    def query(self, idx):
        # 前缀查询：返回[1, idx]的和
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & (-idx)  # 移动到父节点
        return res

def solve():
    t = int(input())
    
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        
        # 计算收益值数组b
        b = [a[i] - (i + 1) for i in range(n)]
        
        # 收集所有可能的值进行离散化
        vals = []
        for i in range(n):
            vals.append(b[i])    # b[i]本身
            vals.append(-b[i])   # -b[i]用于查询
        
        # 排序并去重
        vals = sorted(set(vals))
        
        # 建立值到索引的映射
        def get_idx(x):
            return bisect.bisect_left(vals, x) + 1
        
        import bisect
        
        # 初始化树状数组
        bit = BIT(len(vals))
        ans = 0
        
        # 从左到右处理每个位置
        for j in range(n):
            # 查询有多少个已处理的b[i] > -b[j]
            # 即查询在vals中大于-b[j]的元素个数
            threshold = -b[j]
            pos = bisect.bisect_right(vals, threshold)  # 第一个>threshold的位置
            
            # 计算严格大于threshold的元素个数
            cnt = bit.query(len(vals)) - bit.query(pos)
            ans += cnt
            
            # 将当前b[j]加入树状数组
            bit.update(get_idx(b[j]), 1)
        
        print(ans)

if __name__ == "__main__":
    solve()

• Cpp

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

struct BIT {
    int n;
    vector<long long> tree;
    
    BIT(int size) : n(size) {
        tree.assign(n + 1, 0);  // 初始化树状数组
    }
    
    void update(int idx, int val) {
        // 单点更新：在位置idx增加val
        while (idx <= n) {
            tree[idx] += val;
            idx += idx & (-idx);  // 移动到下一个需要更新的位置
        }
    }
    
    long long query(int idx) {
        // 前缀查询：返回[1, idx]的和
        long long res = 0;
        while (idx > 0) {
            res += tree[idx];