2 条题解

  • 4
    @ 2025-2-27 10:11:30
    赛时有幸想出正解,先说一下做法:

    我们发现无论怎么放置这三个正方形,最后其分别所在区域一定可以划分成下面六种情况的其中一种:

    下面暂且称一个L*L内的数字之和为取数和虽然后面只提到了一次

    便不难想到

    预处理出以每个节点为分割点将矩形分割为四个部分后每个部分内的最大取数和

    注意:

    - 1.用前缀和维护

    - 2.细致使用下标@

    由此以来每个节点便都对应了四个参数,巧妙的利用这四个参数便可以处理出这六种情况下のans,再取个max,over~

    顺便送一个code:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=2077;
    int n,m,l;
    int a[N][N];
    int sum[N][N];
    int lu[N][N];
    int ru[N][N];
    int ld[N][N];
    int rd[N][N];
    int ans;
    int getsum(int x1,int y1,int x2,int y2){return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];}
    void I_N_I_T(){           //预处理part 
    	for(int i=l;i<=n;i++){
    		for(int j=l;j<=m;j++){
    			lu[i][j]=max(lu[i-1][j],lu[i][j-1]);
    			lu[i][j]=max(lu[i][j],a[i][j]);
    		}
    	}
    	for(int i=n-l+1;i>=1;i--){
    		for(int j=l;j<=m;j++){
    			ld[i][j]=max(ld[i+1][j],ld[i][j-1]);
    			ld[i][j]=max(ld[i][j],a[i+l-1][j]);
    		}
    	}
    	for(int i=l;i<=n;i++){
    		for(int j=m-l+1;j>=1;j--){
    			ru[i][j]=max(ru[i-1][j],ru[i][j+1]);
    			ru[i][j]=max(ru[i][j],a[i][j+l-1]);
    		}
    	}
    	for(int i=n-l+1;i>=1;i--){
    		for(int j=m-l+1;j>=1;j--){
    			rd[i][j]=max(rd[i+1][j],rd[i][j+1]);
    			rd[i][j]=max(rd[i][j],a[i+l-1][j+l-1]);
    		}
    	}
    } 
    signed main(){
    	cin.tie(0)->sync_with_stdio(0);
    	cin>>n>>m>>l; 
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>a[i][j];
    			sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    		}
    	}
    	for(int i=l;i<=n;i++){
    		for(int j=l;j<=m;j++){
    			a[i][j]=getsum(i-l+1,j-l+1,i,j); //L*L的区间数字和   
    		}
    	}
    	
    	I_N_I_T();
    	
    	//四种 2+1  
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			ans=max(ans,lu[i][j]+ru[i][j+1]+ld[i+1][m]);
    			ans=max(ans,ru[i][j]+rd[i+1][j]+lu[n][j-1]);
    			ans=max(ans,rd[i][j]+ld[i][j-1]+ru[i-1][1]);
    			ans=max(ans,ld[i][j]+lu[i-1][j]+rd[1][j+1]);
    		}
    	}
    	//两种 1+1+1  
    	for(int i=l;i<=n;i++){
    		for(int j=l;j<=m;j++){
    			ans=max(ans,lu[i-l][m]+a[i][j]+rd[i+1][1]);
    			ans=max(ans,ld[1][j-l]+a[i][j]+ru[n][j+1]);
    		}
    	}
    	cout<<ans;
    	//完结撒花
    	return 0;
    }
    
    
    
    

    题外话别看了

    赛后放榜,本人发现自己得了35分! 的好成绩,刺眼的Time Exceed如此鲜红,鲜红的Time Exceed如此刺眼,直到第二天上午才被告数据出锅,我的65pts啊呜呜

    o(╥﹏╥)o

    • @ 2025-2-27 10:41:27

      %%%rank1

  • -3
    @ 2025-2-26 16:03:25

    用两条线把整张图分成 33 部分,三个正方形一定分别分布在这 33 部分中,二维前缀和预处理,然后暴力枚举两条线即可,时间复杂度为 O(n2)O(n^2)。

    代码比较不友好。

    • @ 2025-2-27 8:43:53

      为什么我写的n方t到了35pts

    • @ 2025-2-27 9:41:41

      @ 人傻常数大,快读写爆炸

    • @ 2025-2-27 10:22:09

      @ wssb

  • 1

信息

ID
46
时间
1000ms
内存
256MiB
难度
9
标签
(无)
递交数
133
已通过
11
上传者