欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-28 17:55:10
题意给一个n*m的矩阵,矩阵的值为A(i,j) = lcm(i,j),i表示所在列,j为所在行,...

题意

给一个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

相关标签: 算法