题解 CF263E Rhombus

itisover · 2022-07-21 16:20:06 · 题解

idea 是偷网上的，那就算一下复杂度吧。

考虑转成切比雪夫，那么要加的区域就把一个斜 45 正方形转成了一个正方形（dis(a,b)=\max\{|x_a-x_b|,|y_a-y_b|\} 结论显然），那这样就可以二维前缀和直接做了，正方形内的系数还是一层一层递减的，所以我们直接枚举点坐标和当前计算贡献的层数 i\in [k,n-k+1],j\in[k,m-k+1],z\in[0,k-1] 爆算就行了。

算一下复杂度：O(i\cdot j\cdot z)=O((n-2k)(m-2k)k)，显然 n=m=1000 时取的最大，这时候就是 10^6k-4000k^2+4k^3,k\le500，求导一下可知最大值为 74074074.41591052711，综上能过。

能懂这个正方形长什么样吧，能懂吧能懂吧。来张图，这能理解了吧。

#include<bits/stdc++.h>
using namespace std;
const int _=2005;
int n,m,k;
long long b[_][_],maxn;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>k;
    pair<int,int> ans={k,k};
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>b[i+j][i-j+m];//+m是因为有负数
    for(int i=1;i<=n+m;++i)
        for(int j=1;j<=n+m;++j)
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
    for(int i=k;i<=n-k+1;++i){
        for(int j=k;j<=m-k+1;++j){
            int x=i+j,y=i-j+m;
            long long sum=0;
            for(int z=0;z<k;++z) sum+=b[x+z][y+z]-b[x-z-1][y+z]-b[x+z][y-z-1]+b[x-z-1][y-z-1];//理解成一圈一圈加
            if(maxn<sum) ans={i,j},maxn=sum;
        }
    }
    cout<<ans.first<<" "<<ans.second;
    return 0;
}
//O(74074074.41591052711)