✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

🌸 目前本专栏已经上线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