✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目一：魔术配对挑战

1️⃣：为每种图案构建64位随机哈希值，避免冲突

2️⃣：计算前缀异或和数组，用于快速查询区间异或和

3️⃣：利用异或性质判断区间内元素是否都出现偶数次

难度：中等

这道题目利用了异或运算的特性：相同元素异或结果为0。通过将元素映射为随机数并计算前缀异或，可以在O(1)时间内查询任意区间内的元素是否全部出现偶数次，从而将整体时间复杂度优化至O(n+q)，高效处理大规模查询。

题目二：花园灯饰平衡布置

1️⃣：自底向上DFS计算每个子树能挂的最大灯数

2️⃣：均衡化处理，限制子树差值不超过1

3️⃣：自顶向下分配灯的具体位置，优先考虑编号小的节点

难度：中等偏难

这道题目结合了树形DP和贪心算法。第一遍DFS自底向上计算每个子树的容量限制，第二遍DFS自顶向下分配灯的位置。通过巧妙的均衡化处理和优先级分配，确保满足平衡条件的同时挂最多的灯，时间复杂度为O(n log n)。

01. 魔术配对挑战

问题描述

小兰是一位魔术师，她有一套特殊的魔术卡片。这些卡片必须两两配对才能使用，每对卡片必须有相同的图案。由于最近表演频繁，小兰的卡片被弄得乱七八糟，现在它们被排成了一行。

在每场魔术表演前，小兰需要从这排卡片中取出连续的一段（从第 张到第 张）。为了保证魔术效果完美，小兰要求取出的卡片总数必须是偶数，并且所有卡片都能恰好配对成对（即每种图案的卡片都出现偶数次）。

小兰今晚有多场表演，每场都会取出不同区间的卡片。请你帮助她判断，对于每个区间，取出的卡片是否满足完美配对的条件。

输入格式

输入的第一行包含两个整数 和 ，表示小兰的卡片总数和询问次数。

接下来一行包含 个整数，其中第 个整数表示第 张卡片的图案编号（保证图案编号是 到 之间的整数）。

接下来 行，每行两个整数 和 ，表示小兰的询问区间，保证 是一个偶数。

输出格式

对于每一次询问，如果区间 中所有卡片能够刚好组成 对，输出一行 "yes"，否则输出 "no"（输出均为小写）。

样例输入

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

样例输出

no
yes
no
yes

数据范围

• 
• 
• 图案编号
• 
• 是偶数

题解

这道题目看似简单，但如果用暴力方法去统计每种图案的出现次数，时间复杂度会达到O(n×q)，在数据规模较大时会超时。我们需要一个更高效的解法。

关键发现：如果一个区间内的所有元素都出现偶数次，那么这个区间内每个元素的异或和为0。

异或运算有一个特性：任何数与自身异或等于0（a⊕a=0）。如果某个数出现了偶数次，它们互相异或后的结果就是0。因此，如果区间内所有卡片都能完美配对，意味着每种图案都出现偶数次，那么这个区间的所有元素异或和应该等于0。

但有个问题，不同的卡片图案可能异或后等于0（比如1⊕2⊕3=0），这会导致哈希冲突。为了避免这种情况，我们可以将每种图案映射为一个64位的随机数，然后计算这些随机数的异或和。这样哈希冲突的概率就变得极低。

算法步骤：

1. 为每种图案生成一个64位随机数
2. 计算前缀异或数组：pre[i]表示前i个卡片的异或和
3. 对于每个询问[l,r]，计算pre[r] ⊕ pre[l-1]
4. 如果结果为0，说明区间内的每种图案都出现偶数次，输出"yes"，否则输出"no"

时间复杂度：

• 预处理前缀异或数组: O(n)
• 处理每个询问: O(1)
• 总时间复杂度: O(n + q)

空间复杂度：O(n)，用于存储前缀异或数组和图案到随机数的映射。

这个算法在最坏情况下也能高效处理大量询问，适用于题目给出的数据范围（n, q <= 10^5）。

参考代码

• Python

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

def solve():
    # 读取输入
    n, q = map(int, input().split())
    cards = list(map(int, input().split()))
    
    # 为每种图案分配一个随机数
    pattern_map = {}
    for card in cards:
        if card not in pattern_map:
            pattern_map[card] = random.getrandbits(64)  # 生成64位随机数
    
    # 计算前缀异或和
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] ^ pattern_map[cards[i]]
    
    # 处理每个询问
    for _ in range(q):
        l, r = map(int, input().split())
        # 计算区间[l,r]的异或和
        xor_sum = pref[r] ^ pref[l - 1]
        
        if xor_sum == 0:
            print("yes")
        else:
            print("no")

if __name__ == "__main__":
    solve()

• Cpp

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

int solve() {
    // 读取输入
    int n, q;
    cin >> n >> q;
    
    vector<int> cards(n);
    for (int i = 0; i < n; ++i) {
        cin >> cards[i];
    }
    
    // 为每种图案分配一个随机数
    unordered_map<int, uint64_t> hash_map;
    mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
    
    for (int card : cards) {
        if (hash_map.find(card) == hash_map.end()) {
            hash_map[card] = rnd();  // 生成64位随机数
        }
    }
    
    // 计算前缀异或和
    vector<uint64_t> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] ^ hash_map[cards[i]];
    }
    
    // 处理每个询问
    while (q--) {
        int l, r;
        cin >> l >> r;
        
        // 计算区间[l,r]的异或和
        uint64_t xor_val = pref[r] ^ pref[l - 1];
        
        if (xor_val == 0) {
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
    
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int q = Integer.parseInt(line[1]);
        
        int[] cards = new int[n];
        line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(line[i]);
        }
        
        // 为每种图案分配一个随机数
        Map<Integer, Long> hashMap = new HashMap<>();
        Random rand = new Random();
        
        for (int card : cards) {
            if (!hashMap.containsKey(card)) {
                hashMap.put(card, rand.nextLong());  // 生成64位随机数
            }
        }
        
        // 计算前缀异或和
        long[] pref = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] ^ hashMap.get(cards[i]);
        }
        
        // 处理每个询问
        for (int i = 0; i < q; i++) {
            line = br.readLine().split(" ");
            int l = Integer.parseInt(line[0]);
            int r = Integer.parseInt(line[1]);
            
            // 计算区间[l,r]的异或和
            long xorVal = pref[r] ^ pref[l - 1];
            
            if (xorVal == 0) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }
    }
}

02. 花园灯饰平衡布置

问题描述

小基是一名园艺设计师，为了迎接即将到来的园艺节，她决定在一棵树状结构的园艺装置上布置彩灯。

这棵树有 个节点，每个非叶子节点（即有子节点的位置）都可以挂一串彩灯。但小基特别注重美感平衡，她希望对于树上的每个节点，其所有子树上挂的彩灯数量的差值不超过1。也就是说，如果某个节点有多个子节点，那么这些子节点为根的子树上挂的彩灯数量最多相差1。

当满足能挂最多彩灯的条件后，小基会优先在编号较小的节点上挂灯。请你计算小基最多能在装置上挂几串彩灯，以及具体的挂灯方案。

输入格式

第一行包含一个正整数 ，表示树的节点个数。

第二行包含 个正整数，第 个整数 表示节点 的父节点。

保证 ，即父节点的编号总是小于子节点的编号。

输出格式

第一行输出一个整数，表示小基最多能挂几串彩灯。

第二行输出 个整数，用空格分隔，第 个整数表示节点 是否挂了彩灯，1表示挂了彩灯，0表示没有挂彩灯。

样例输入

10
1 1 2 2 3 4 5 6 7

样例输出

6
1 1 1 1 1 1 0 0 0 0

数据范围

• 
• 对于所有的

题解

这道题考察的是树形DP和贪心算法。我们需要找出在满足平衡条件下最多能挂多少串彩灯，并给出具体方案。

首先，让我们明确一下问题中的平衡条件：对于树中任意节点，其所有子树挂灯数量的差值不能超过1。这意味着如果一个节点有多个子节点，这些子节点领导的子树上的灯数量必须尽可能相等。

解题思路主要分两步：

1. 自底向上计算每个子树最多能挂多少灯（第一次DFS）
2. 自顶向下分配灯的具体位置（第二次DFS）

在第一次DFS中，我们计算每个节点为根的子树最多能挂多少灯，这是个"容量"限制。计算方法是：

• 对于叶子节点，最多能挂0个灯（因为题目说只有非叶子节点才能挂灯）
• 对于非叶子节点，我们先对其所有子树能挂的灯数进行排序
• 然后进行"均衡化"处理：如果某个子树能挂的灯比最少的子树多超过1个，就将其限制为最少的子树数量+1
• 最后加上当前节点自己能挂1个灯

在第二次DFS中，我们实际分配灯的位置：

• 优先在当前节点挂灯
• 然后将剩余的灯尽量平均分配给各个子树
• 如果不能平均分配，优先分给编号小的子节点

时间复杂度分析：

• 建立树的邻接表：O(