2020牛客多校联赛F题-Fake Maxpolling

题意

给一个nm的矩阵，矩阵的值为A(i,j) = lcm(i,j),i表示所在列，j为所在行。给定一个k值，求在nm矩阵中，所有k*k的子矩阵的最大的A(i,j)之和。

思路

两次单调队列，第一次求行的最大值，将其转化为一个n-k，m-k的子矩阵，第二次求列的最大值。最后求和。

自己写的gcd函数会超时，调用__gcd函数可以过。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#include<vector>
#include<string>
#include<deque>
const int mod = 998244353;
using namespace std;
typedef long long ll;
//ll Q[6000][6000];
struct node
{
	ll ans, vel;
};
vector<ll> v[6000];

ll gcd(ll numberA, ll numberB)
{
	if (numberA == numberB)
		return numberA;
	if (numberA < numberB)
		return gcd(numberB, numberA);
    else
	{
		//和1做按位与运算，判断奇偶
		if (!numberA & 1 && !numberB & 1)  //都是偶数
			return gcd(numberA >> 1, numberB >> 1) << 1;
		else if (!numberA & 1 && numberB & 1)
			return gcd(numberA >> 1, numberB);
		else if (numberA & 1 && !numberB & 1)
			return gcd(numberA, numberB >> 1);
		else
			return gcd(numberB, numberA - numberB);
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(0);
	ll n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		deque<node>Q;
		for (int j = 1; j <= m; j++)
		{
			ll lcm = i * j / (gcd(i, j));
			while (!Q.empty() && lcm > Q.back().vel)
				Q.pop_back();
			Q.push_back({ j,lcm });
			while (!Q.empty() && Q.front().ans <= j - k)
			{
				Q.pop_front();
			}
			if (j >= k)
			{
				v[i].push_back(Q.front().vel);
			}
		}
	}
	ll sum = 0;
	for (int i = 0; i < m - k + 1; i++)
	{
		deque<node>Q;
		for (int j = 1; j <= n; j++)
		{
			while (!Q.empty() && Q.back().vel < v[j][i])
				Q.pop_back();
			Q.push_back({ j,v[j][i] });
			while (!Q.empty() && Q.front().ans <= j - k)
				Q.pop_front();
			if (j >= k)
			{
				sum += Q.front().vel;
			}
		}
	}
	cout << sum << endl;
}

本文地址：https://blog.csdn.net/weixin_43832788/article/details/107350065