2020牛客暑期多校训练营(第二场)未完待续......
程序员文章站
2022-05-12 12:31:30
...
F. Fake Maxpooling
题目:
题目大意:
输入n,m,k。矩阵的尺寸为nm,其中每一个元素为A[i][j] = lcm( i , j )。从中找出所有kk的子矩阵中元素最大的数之和。
题解:
时间为3s,O()的算法和O()的算法。
- 构建矩阵:朴素算法O(),直接暴力就行。
- O()构建矩阵:类似于埃氏筛的写法:
出题人巨巨的写法
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!Gcd[i][j]) //没有被筛过,则证明i,j互质
for (int z = 1; z * i <= n && z * j <= m; z++)//z为扩大的倍数
{
Gcd[i * z][j * z] = z;
A[i * z][j * z] = i * j * z;//矩阵元素计算
}
- 查找最大值:二维的滑动窗口,我们用单调队列进行即可。
- 先按每一列or行进行一维的单调队列的查找并存入新的数组中。
- 然后再用新的数组进行另外每一行or列进行一维单调队列即可。
- 坑点:注意我们再进行另外一维的时候要用新的数组,新的数组要从列标or行标开始循环。
本人的ACcode:
/*
* @Author: NEFU_马家沟老三
* @LastEditTime: 2020-07-13 22:54:45
* @CSDN blog: https://blog.csdn.net/acm_durante
* @E-mail: aaa@qq.com
* @ProbTitle:
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define lowbit(x) ((x) & -(x))
const double PI = acos(-1.0);
int n, m, k;
int a[5005][5005];
int b[5005][5005];
int que[5005];
ll ans = 0;
void solvej(int i)
{
int l = 1, r = 0;
rep(j, 1, m)
{
while (r >= l && a[i][que[r]] <= a[i][j])
--r;
que[++r] = j;
while (r >= l && que[l] + k <= j)
++l;
if (j >= k)
b[i][j] = a[i][que[l]];
}
}
void solvei(int j)
{
int l = 1, r = 0;
rep(i, 1, n)
{
while (r >= l && b[que[r]][j] <= b[i][j])
--r;
que[++r] = i;
while (r >= l && que[l] + k <= i)
++l;
if (i >= k)
ans += b[que[l]][j];
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
if (n > m)
swap(n, m);
rep(i, 1, n)
{
rep(j, i, m)
{
a[i][j] = a[j][i] = i * j / __gcd(i, j);
}
}
rep(i, 1, n) //先对每一行进行单调队列处理
solvej(i);
rep(j, k, m) //对新数组每一列的单调队列处理,并求和
solvei(j);
printf("%lld\n", ans);
return 0;
}
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客多校第三场-J Just Shuffle
-
2020牛客多校第3场[Clam and Fish+贪心]
-
2020牛客多校第三场 E Two Matchings
-
2020牛客暑期多校训练营(第二场)Cover the Tree