✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

米哈游-2026.03.14

米哈游

这一套题前两题都不难读懂，但切入口要找对。第一题是标准统计题，第二题看上去像删数构造，实质上就是最长摆动子序列；真正拉开差距的是第三题，需要把树上路径异或和改写成前缀异或的点对贡献。

题目一：展墙与橱窗配对

题面包装成展馆布置，本质却很朴素：行和与列和能否配对，只和总和数值有关，和格子内部怎么分布无关。先把每一行、每一列的总数算出来，再用哈希表统计频次，答案就是同值频次的配对和。

题目二：错峰站位

这题最容易在“删哪些人” 上绕进去，其实换个说法就通了：保留下来的序列必须让相邻差值符号交替。于是问题直接落成最长摆动子序列，贪心保留转折点即可，最后用总人数减去最长长度。

题目三：秘境回路异纹和

树上路径异或和如果硬枚举点对肯定不行，关键是先把每个点的“根到点前缀异或” 算出来。路径异或会变成两个前缀异或的异或，再按位拆贡献，统计每一位上 的总和，就能在线性级别内做完。

1. 展墙与橱窗配对

问题描述

K 小姐正在整理一张展馆布置表。表格一共有 行 列，第 行第 列的数字 表示第 条展墙在第 个橱窗区域对应的陈列数量。

现在要做一组“展墙 - 橱窗” 联动推荐。若某条展墙这一整行的陈列总数，恰好等于某个橱窗区域这一整列的陈列总数，那么这一对就能组成一组合法配对。

请统计一共有多少个这样的有序二元组 。

输入格式

第一行输入两个整数 ，表示展馆布置表的行数和列数。

接下来输入 行，每行包含 个整数，其中第 行第 个数表示 。

输出格式

输出一个整数，表示合法配对数量。

样例输入

3 3
1 1 1
1 1 1
1 1 1

样例输出

9

数据范围

样例	解释说明
样例1	三条展墙的总数都是 ，三个橱窗区域的总数也都是 ，所以任意一条展墙都能和任意一个橱窗区域配对，共有 对。

题解

题目真正关心的不是某个格子的数值，而是整行总数和整列总数能不能对上。

设某个值 作为“行和” 出现了 次，作为“列和” 出现了 次。那么凡是行和等于 的展墙，都能和列和等于 的橱窗区域一一配对，所以这一类一共贡献 个答案。

于是做法很自然：

1. 读入表格时，同时算出每一行的总和和每一列的总和。

2. 用哈希表统计每种行和出现了多少次。

3. 再扫一遍所有列和，把对应的行和频次累加到答案里。

这样每个合法配对只会按它共同的总和被统计一次，不会漏，也不会重。

复杂度分析

读入和求和是 ，统计答案是 ，总时间复杂度是 。额外空间复杂度是 。

参考代码

• Python

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

def solve():
    n, m = map(int, input().split())
    # rs 记录每条展墙的总数，cs 记录每个橱窗区域的总数。
    rs = [0] * n
    cs = [0] * m

    for i in range(n):
        row = list(map(int, input().split()))
        rs[i] = sum(row)
        for j, x in enumerate(row):
            cs[j] += x

    # 统计每种行和出现了多少次。
    mp = {}
    for x in rs:
        mp[x] = mp.get(x, 0) + 1

    # 每个列和都去匹配相同的行和频次。
    ans = 0
    for x in cs:
        ans += mp.get(x, 0)

    print(ans)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // rs 统计每一行总和，cs 统计每一列总和。
    vector<long long> rs(n, 0), cs(m, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            long long x;
            cin >> x;
            rs[i] += x;
            cs[j] += x;
        }
    }

    unordered_map<long long, long long> mp;
    mp.reserve(n * 2 + 1);
    for (long long x : rs) {
        ++mp[x];
    }

    // 对每个列和累加相同行和的出现次数。
    long long ans = 0;
    for (long long x : cs) {
        auto it = mp.find(x);
        if (it != mp.end()) {
            ans += it->second;
        }
    }

    cout << ans << '\n';
    return 0;
}

• Java

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

public class Main {
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= 32 && c != -1);

            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }

            long val = 0;
            while (c > 32) {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = (int) fs.nextLong();
        int m = (int) fs.nextLong();

        // rs 和 cs 分别维护行和与列和。
        long[] rs = new long[n];
        long[] cs = new long[m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                long x = fs.nextLong();
                rs[i] += x;
                cs[j] += x;
            }
        }

        Map<Long, Integer> mp = new HashMap<>();
        for (long x : rs) {
            mp.put(x, mp.getOrDefault(x, 0) + 1);
        }

        // 枚举列和并查找对应的行和频次。
        long ans = 0;
        for (long x : cs) {
            ans += mp.getOrDefault(x, 0);
        }

        System.out.println(ans);
    }
}

2. 错峰站位

问题描述

K 小姐正在给一组演员安排舞台站位。第 位演员的站位高度记为 。

如果一段站位序列满足下面两个条件，就称它是“错峰站位”：

• 对于每个中间位置，当前演员的高度要么严格高于左右两侧，要么严格低于左右两侧。

• 任意相邻两位演员的高度都不能相等。

现在可以从原序列中删除若干位演员，剩下的演员保持原有相对顺序不变。请计算最少要删除多少人，才能让剩余队形变成“错峰站位”。

输入格式

第一行输入一个整数 ，表示演员人数。

第二行输入 个整数 ，表示每位演员的站位高度。

输出格式

输出一个整数，表示最少删除人数。

样例输入

7
1 3 1 4 5 2 0

3
2 2 2

样例输出

2

2

数据范围

样例	解释说明
样例1	删除 这两位高度后，可以保留序列 ，此时相邻高低关系交替出现，满足要求。
样例2	所有人高度都相同，不可能留下长度至少为 的合法相邻关系，最优只能留下 1 人，所以要删掉 2 人。

题解

把题意翻成更熟悉的话，剩下的序列要满足“相邻差值的正负号严格交替”，并且不能出现相邻相等。这正是经典的最长摆动子序列。

所以原问题可以改写成：

• 尽量保留更多演员，使保留下来的高度序列成为摆动序列。

• 设这个最长长度是 ，那么最少删除人数就是 。

为什么可以贪心

从左到右看相邻差值：

• 若当前差值为正，说明这一段趋势在上升。

• 若当前差值为负，说明这一段趋势在下降。

• 若当前差值为 ，这个位置对制造起伏没有帮助，可以直接忽略。

真正有价值的是“趋势改变”的那一刻。只要发现当前差值和上一段有效差值符号不同，就说明出现了一个新的波峰或波谷，可以把答案加一。

这件事之所以能贪心，是因为在一段连续上升里，保留更靠后的更高位置只会更有利；在一段连续下降里，保留更靠后的更低位置也只会更有利。也就是说，同方向的一长段走势，中间点没有必要全部留下，只保留转折点就够了。

做法

1. 先把答案设成 ，表示至少可以保留一个人。

2. 维护上一段有效差值 pre。

3. 依次考察相邻两人的差值 cur：

   • 若 cur=0，跳过。

   • 若 cur 与 pre 异号，说明出现新转折，保留人数加一，并更新 pre。

4. 最终输出 。

复杂度分析

只需要一趟扫描，时间复杂度是 ，额外空间复杂度是 。

参考代码

• Python

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    # 至少可以保留 1 人。
    ans = 1
    # pre 记录上一段有效差值的符号。
    pre = 0

    for i in range(1, n):
        cur = a[i] - a[i - 1]
        if cur == 0:
            continue
        # 遇到新的转折点，就把它计入摆动序列。
        if (cur > 0 and pre <= 0) or (cur < 0 and pre >= 0):
            ans += 1
            pre = cur

    print(n - ans)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullpt