P9905 [COCI 2023/2024 #1] AN2DL 题解

本文主要是介绍P9905 [COCI 2023/2024 #1] AN2DL 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

首先考虑暴力算法，枚举每一个右端点，再遍历求最大值，枚举的时间复杂度为 $O(n^2)$ ，遍历复杂度同样 $O(n^2)$ 。显然，在 $n = 3000$ 时无法通过，考虑更优解法。

~~大眼观察~~，发现这道题和 P1886 滑动窗口 /【模板】单调队列是几乎一样的；也就是把一维单调队列变成了二维的单调队列。

当然，也可以理解成多个窗口在二维矩阵上面滑动；也就是一个 $r\times s$ 的滑动窗口。

分析发现，这种算法是可以通过的，我们不妨分步解决，跑两次单调队列就可以完美解决问题！

操作流程：

对 $n\times m$ 的矩阵每行都跑一次单调队列。

跑完后可以发现形成了一个 $n\times (m-s+1)$ 的矩阵 $A$ ，根据题意，不难发现， $A_{i,j}= \max\limits_{j\le y \le (j+s-1)}^{}\times C_{i,y}$ （设 $C$ 为题目输入的矩阵）

对 $A$ 矩阵每列都跑一次单调队列（这样就形成了一个二维的单调队列结果）。

跑完后可以发现形成了一个 $(n-r+1)\times (m-s+1)$ 的矩阵 $B$ ，根据题意，不难发现， $B_{i,j}= \max\limits_{i\le x \le (i+r-1)}^{}\times A_{x,y}$

此时的 $B$ 矩阵就是所期望的啦！

代码：

在_zuoqingyuan的代码基础上优化了码风，并增加了细节注释。

#include <bits/stdc++.h>
using namespace std;
int a[4005][4005], n, m, r, s; // a表示原始矩阵，n和m表示矩阵的行列数，r和s表示滑动窗口的大小。
vector <int> v1[4005], v2[4005]; // v1和v2用来存储中间结果和最终结果。
deque <int> q; // 双端队列用来维护滑动窗口。int main() {ios :: sync_with_stdio(false); // 禁用cin和cout的同步，提高I/O效率。cin >> n >> m; // 输入矩阵的行和列。for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++) cin >> a[i][j]; // 输入矩阵元素。cin >> r >> s; // 输入滑动窗口的大小。for (int i = 1; i <= n; i ++) {v1[i].push_back(0); // 初始化v1的每一行。for (int j = 1; j <= m; j ++) {while (q.size() && q.front() <= j - s) q.pop_front(); // 若队列头部的元素已不在窗口内，弹出。while (q.size() && a[i][q.back()] < a[i][j]) q.pop_back(); // 若当前元素大于队尾元素，弹出队尾，维持队列单调递减。q.push_back(j); // 将当前列加入队列。if (j >= s) v1[i].push_back(a[i][q.front()]); // 若已到窗口大小，加入v1中。}q.clear(); // 清空队列为下一行做准备。}m = m - s + 1; // 更新列的有效长度。for (int i = 1; i <= m; i ++) {v2[i].push_back(0); // 初始化v2的每一列。for (int j = 1; j <= n; j ++) {while (q.size() && q.front() <= j - r) q.pop_front(); // 类似上面的操作，但是这次是行。while (q.size() && v1[q.back()][i] < v1[j][i]) q.pop_back(); // 维持队列单调递减。q.push_back(j); // 将当前行加入队列。if (j >= r) v2[i].push_back(v1[q.front()][i]); // 若已到窗口大小，加入v2中。}q.clear(); // 清空队列为下一列做准备。}n = n - r + 1; // 更新行的有效长度。// 输出最终结果。for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) cout << v2[j][i] << endl;cout << endl;}return 0;
}