笔试时间：2024年03月30日

历史笔试传送门：2023秋招笔试合集

第一题

题目：池化

牛牛在学习热门话题深度学习时，梦想早日毕业的牛牛受常用的卷积神经网络(CNN)的池化操作启发，创建了自己的池化并应用于在图像处理中。假设给定一个8* 8的矩阵。

1.将矩阵分成大小为2*2的子矩阵；

2.在每个2* 2的子矩阵中只留下第二大的数字。在这里，当子矩阵的四个元素为a4≤a3 ≤a2≤a1时，第二大数为元素a2。

3.重复2的过程，矩阵的大小不断缩小。现在牛牛想知道当N * N矩阵通过重复应用池化操作，最终变成1 * 1时，留下的数是多少?

输入描述

第—行给出N。且N总是2的幂；

接下来的N行，依次给出每行的N个元素；

矩阵的每个元素都是大于等于―10000且小于等于10000的整数。

2≤N≤1024

输出描述

输出最后剩余的数字。

样例输入一

4

-6 -8 7 -4

-5 -5 14 11

11 11 -1 -1

4 9 -2 -4

样例输出一

11

样例输入二

8

-1 2 14 7 4 -5 8 9

10 6 23 2 -1 -1 7 11

9 3 5 -2 4 4 6 6

7 15 0 8 21 20 6 6

19 8 12 -8 4 5 2 9

1 2 3 4 5 6 7 8

9 10 11 12 1314 15 16

17 18 19 20 21 22 23 24

样例输出二

17

参考题解

递归的思路，每次将矩阵四等分，找到第二大元素，进行返回即可。

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<vector<int>> arr(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> arr[i][j];
        }
    }
    auto helper = [&](auto&& self, int left, int top, int right, int bottom) {
        int n = right - left + 1;
        if (n == 1) {
            return arr[left-1][top-1];
        }
        vector<int> a(4);
        a[0] = self(self, left, top, left + n / 2 - 1, top + n / 2 - 1);
        a[1] = self(self, left, n / 2 + top, left + n / 2 - 1, bot