笔试时间：2025年03月22日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：多少双手套

小 A 有很多双手套，但是由于他不是很爱收拾所以现在这些手套全部乱成一团。小 A 的手套是不分左右手的，但是需要两只相同花色的手套才能匹配成一双。小A现在将这些手套排成一行他想知道如果将区间[l, r]中的所有手套取出，且r-l+1是偶数，这些手套是否刚好能组成(r-l+1)/2双手套。小 A 会提出这个问题很多次，你能帮帮他吗?

输入描述

输入的第一行包含两个整数n和q，表示小A 手中的手套数量和询问次数；

接下来一行包含n个整数，其中第i个表示第i只手套的花色编号；

接下来q行每行两个整数l和r，表示小 A 的询问区间，保证r-l+1是一个偶数。

输出描述

对于每一次询问，如[l,r]中所有手套能够刚好组成(r-l+1)/2双，输出一行 “yes” ,否则输出 “no” 。(输出时均不包含引号，且均为小写)。

样例输入

6 4

2 3 1 1 2 3

1 4

3 4

3 6

1 6

样例输出

no

yes

no

yes

参考题解

异或哈希。若一个区间的所有元素出现偶数次，那么这个区间的异或值为0。由于可能出现哈希冲突（不同数异或得到相同结果），把每个数都替换成一个64位的随机数，再计算一下前缀异或，之和对于每个询问只需要看这段区间的异或和是否为0即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    unordered_map<int, uint64_t> hs;
    mt19937_64 rng(random_device{}());
    for (int i = 0; i < n; ++i) {
        if (hs.find(a[i]) == hs.end()) {
            hs[a[i]] = rng();
        }
    }
    vector<uint64_t> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pre[i + 1] = pre[i] ^ hs[a[i]];
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        uint64_t x = pre[r] ^ pre[l - 1];
        if (x == 0) {
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;
import java.security.SecureRandom;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        Map<Integer, Long> hs = new HashMap<>();
        Random rng = new SecureRandom();

        for (int i = 0; i < n; i++) {
            if (!hs.containsKey(a[i])) {
                hs.put(a[i], rng.nextLong());
            }
        }

        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] ^ hs.get(a[i]);
        }

        for (int i = 0; i < q; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            long x = pre[r] ^ pre[l - 1];
            System.out.println(x == 0 ? "yes" : "no");
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

import random

n, q = map(int, input().split())
a = list(map(int, input().split()))

hs = {}
rng = random.Random()

for val in a:
    if val not in hs:
        hs[val] = rng.getrandbits(64)

pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] ^ hs[a[i]]

for _ in range(q):
    l, r = map(int, input().split())
    x = pre[r] ^ pre[l - 1]
    print("yes" if x == 0 else "no")

第二题

题目：小李挂灯笼

过年了!大红灯笼高高挂!小李想在门前的大树上挂上灯笼。小李认为，每个非叶子结点(即树杈处)可以挂一串灯笼，同时平衡的灯笼最好看。这意味着，小李希望，对树上的所有节点，都满足:对所有以当前节点的儿子为根的子树，其上挂的灯笼总是相差不超过1。当满足能挂最多灯笼之后，小李会优先向节点编号小的节点上挂灯笼。请你计算小李最多在树上挂几串灯笼，如何挂。

输入描述

第一行包括一个正整数n，表示树的节点个数；

第二行包括n-1个正整数，第i个整数fi为i+1的父节点。

输出描述

第一行输出一个整数，表示小李最多挂几串灯笼

然后跟着n个整数，0表示第 i 节点没挂， 1表示第 i 节点挂了灯笼。

样例输入

10

1 1 2 2 3 4 5 6 7

样例输出

6

1 1 1 1 1 1 0 0 0 0

说明：

1，2，3，4，5，6均挂上灯笼就符合要求。

7是非叶子结点但是不能挂，否则2节点子数的灯笼为4，与3节点子树的灯笼数量2相差为2，超过题目要求。

参考题解

回溯，首先利用第一个DFS去维护出canNode数组，这个数组代表了每个节点作为根节点的子树最多可以挂多少个灯笼，这个过程中需要先得到子树的答案然后反推出当前节点的答案。再进行一次DFS2，这次的作用是来真正的挂灯笼，用has参数代表了当前这个子树能挂多少个。然后将当前节点挂上灯笼后，将剩余的灯笼平分并分配给每一个子树，因为第一次DFS已经限定了下限，因此分配过去的是一定能够挂完的。

C++：[此代码未进行大量数据的