Fake Maxpooling（2020多校第二場F）

文章目錄

• • 題意：
  • 題解：
  • 代碼：

題意：

一個n * m的矩陣，第i行第j列的值是lcm（i，j），然后給定一個 k * k的子矩陣（k<=min(n,m)），然后求出大矩陣中每個子矩陣的最大值的和
看樣例：

3 4 2 38

給的矩陣是：
1 2 3 4
2 2 6 4
3 6 3 12
所有2 * 2的子矩陣的最大值分別是 ：
2,6，6,6，6,12，總和是38

題解：

暴力求法是O（n m log n），先考慮O（n m）的做法

for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++){if(!Gcd[i][j])for(int k=1;k*i<=n&&k*j<=m;k++)Gcd[k*i][k*j]=k,A[k*i][k*j]=i*j*i*k;} }

之后再用單調隊列

曾經做過一個叫滑動窗口的題，其實和這個是一個類型，那個是一維的，本題這個是二維的
滑動窗口的題解（含題目鏈接）
分別求出每行和每列的k個長度區間的最大值
tail表示尾，head表示頭，不斷得到區間內的最大值，并存進b中，最終覆蓋給a
其實就是把二維的拆分成行和列的一維，然后分別進行和滑動窗口那個題一樣的操作

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=5e3+5; int a[maxn][maxn]; int b[maxn]; int qu[maxn]; int n,m,k; int gcd(int a,int b) {if(b==0)return a;else return gcd(b,a%b); } int lcm(int a,int b) {return a*b/gcd(a,b); } void getr(int j)//固定列 {memset(qu,0,sizeof(qu));int head=0;int tail=1;for(int i=1;i<=n;i++){while(head<=tail&&qu[head]+k<=i)head++;while(head<=tail&&a[i][j]>a[qu[tail]][j])tail--;qu[++tail]=i;if(i>=k)b[i-k+1]=a[qu[head]][j]; }for(int i=1;i<=n-k+1;i++)a[i][j]=b[i];} void getl(int i)//固定行 {memset(qu,0,sizeof(qu));int head=0;int tail=1;for(int j=1;j<=m;j++){while(head<=tail&&qu[head]+k<=j)head++;while(head<=tail&&a[i][j]>a[i][qu[tail]])tail--;qu[++tail]=j;if(j>=k)b[j-k+1]=a[i][qu[head]];}for(int j=1;j<=m-k+1;j++)a[i][j]=b[j]; } int main() {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){a[i][j]=lcm(i,j);}for(int i=1;i<=m;i++)getr(i);for(int i=1;i<=n;i++)getl(i);long long sum=0;for(int i=1;i<=n-k+1;i++){for(int j=1;j<=m-k+1;j++){sum+=a[i][j];}}printf("%lld\n",sum); }

總結

以上是生活随笔為你收集整理的Fake Maxpooling（2020多校第二场F）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。