• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CCF 202104-2 邻域均值 100分(二维前缀和)

互联网 diligentman 1周前 (06-08) 12次浏览
  定义式 递推式
二维前缀和 CCF 202104-2 邻域均值 100分(二维前缀和) CCF 202104-2 邻域均值 100分(二维前缀和)

两种求二维前缀和的方法:

1、使用两个数组

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin>>a[i][j];

int sum[]={0};
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];

2、使用一个数组(a[i][j]之前的前缀和都已经求出来了,和sum[i][j]等价,实际上就是覆盖一下)

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin>>a[i][j];

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+a[i][j];

思路:首先求出二维前缀和,通过二维前缀和的性质可求出指定区域和。

下面是此题AC代码。

CCF 202104-2 邻域均值 100分(二维前缀和)

#include<bits/stdc++.h>

using namespace std;
int n,l,r,t,a[601][601],sum[601][601];
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>l>>r>>t;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			cin>>a[i][j];

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

	int res=0;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			int max_i=min(n,i+r);
			int max_j=min(n,j+r);
			int min_i=max(0,i-r-1);
			int min_j=max(0,j-r-1);
			double tmp=double(sum[max_i][max_j]-sum[min_i][max_j]-sum[max_i][min_j]+sum[min_i][min_j])/double((max_i-min_i)*(max_j-min_j));
			if(tmp<=t)
				res++;
		}
	cout<<res;
	return 0;
}

下面是一维前缀和的介绍和例题解答。

CCF 202012-2 期末预测之最佳阈值 100分(一维前缀和)_m0_47618364的博客-CSDN博客


程序员灯塔
转载请注明原文链接:CCF 202104-2 邻域均值 100分(二维前缀和)
喜欢 (0)