标题 3161: 蓝桥杯2023年第十四届省赛真题-子矩阵
标题https://i-blog.csdnimg.cn/direct/a510f6f394fe451f80e86ecc7eb4cdd2.png
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010, mod = 998244353;
int g;
int rmin, rmax;
ll mmin, mmax;
int q;
int hh, tt;
int n, m, a, b;
int main()
{
cin >> n >> m >> a >> b;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> g;
}
}
for (int i = 1; i <= n; i++)
{
hh = 0, tt = -1;
for (int j = 1; j <= m; j++)
{
if (hh <= tt && j - q + 1 > b)
hh++;
while (hh <= tt && g] >= g)
tt--;
q[++tt] = j;
if (j >= b)
rmin = g];
}
}
for (int j = 1; j <= m; j++)
{
hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
{
if (hh <= tt && i - q + 1 > a)
hh++;
while (hh <= tt && rmin] >= rmin)
tt--;
q[++tt] = i;
if (i >= a)
mmin = rmin];
}
}
for (int i = 1; i <= n; i++)
{
hh = 0, tt = -1;
for (int j = 1; j <= m; j++)
{
if (hh <= tt && j - q + 1 > b)
hh++;
while (hh <= tt && g] <= g)
tt--;
q[++tt] = j;
if (j >= b)
rmax = g];
}
}
for (int j = 1; j <= m; j++)
{
hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
{
if (hh <= tt && i - q + 1 > a)
hh++;
while (hh <= tt && rmax] <= rmax)
tt--;
q[++tt] = i;
if (i >= a)
mmax = rmax];
}
}
ll ans = 0;
for (int i = 1; i + a - 1 <= n; i++)
{
for (int j = 1; j + b - 1 <= m; j++)
{
ans = (ans + (mmin * mmax) % mod) % mod;
}
}
cout << ans;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]