Fake Maxpooling
题目链接:https://ac.nowcoder.com/acm/contest/5667/F
来源:牛客网
题目大意:
有一个矩阵,他的元素为A[i][j]=lcm(i,j) ,然后给出一个k,问这个矩阵里所有k*k大小的子矩阵里最大值的和。
思路:
子矩阵里最值的和 / 区间最值的和 的问题求解,很容易联想到单调队列上,然后子矩阵的话,要压缩一下矩阵,分成两维求,先求行最值,然后求列最值,然后累加答案即可。
求矩阵lcm给出一个线性筛的做法,具体见代码。
Code:
#include <iostream> #include <cstdio> #include<cmath> #include <cstring> #include <algorithm> #include <vector> #include <deque> #include <map> #define inf 0x3f3f3f3f #define ll long long using namespace std; const int maxn=5e3+5; const int mod=998244353; int ma[maxn][maxn]; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int lcm(int i,int j){ return i/gcd(i,j)*j; } int main() { int n,m,k; ll ans=0; ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;i++){ // 线性求矩阵lcm for(int j=1;j<=m;j++){ if(!ma[i][j]){ for(int k=1;k*i<=n&&k*j<=m;k++){ ma[i*k][j*k]=i*j*k; } } } } for(int i=1;i<=n;i++){ // 第一维 deque<int> q; for(int j=1;j<k;j++){ while(q.size()&&ma[i][q.back()]<=ma[i][j]) q.pop_back(); q.push_back(j); } for(int j=k;j<=m;j++){ int l=j-k+1; while(q.size()&&ma[i][q.back()]<=ma[i][j]) q.pop_back(); q.push_back(j); while(q.size()&&q.front()<l) q.pop_front(); ma[i][j]=ma[i][q.front()]; } } for(int j=k;j<=m;j++){ // 第二维 deque<int> q; for(int i=1;i<k;i++){ while(q.size()&&ma[q.back()][j]<=ma[i][j]) q.pop_back(); q.push_back(i); } for(int i=k;i<=n;i++){ int l=i-k+1; while(q.size()&&ma[q.back()][j]<=ma[i][j]) q.pop_back(); q.push_back(i); while(q.size()&&q.front()<l) q.pop_front(); ans+=ma[q.front()][j]; } } cout<<ans<<endl; return 0; }