CCF 202104-2：邻域均值--C++

#include<iostream>
#include<bits/stdc++.h>

using namespace std;


int A[601][601];
int n;//长宽都为n个像素

double FindNeighborSum(int i,int j,int r,int A[][601])
{
	int sum=0;//像素和 
	int gs=0;//领域 中的像素个数 
	for(int x=i-r;x<=i+r;x++)//找到每一个领域像素点 
	{
		for(int y=j-r;y<=j+r;y++)
		{
			if(x>=0&&x<n)
			{
				if(y>=0&&y<n)
				{
				sum+=A[x][y];
				gs++;
				}
				
			}
		}
	}
	
	double result=(double)sum/gs;//要用double不能用int，不然等于t的数量会变多 
	return result;//
}

int main()
{
    
    
	int L;//像素的取值范围
	int r;//领域的范围
	int t;//阈值，当领域内的均值小于或等于阈值t时是较暗区域
	
	cin>>n>>L>>r>>t;
	 
	 for(int i=0;i<n;i++)
	 {
	 	for(int j=0;j<n;j++)
	 	cin>>A[i][j];
	 }
    
    
    int sum=0;//记录较暗区域个数 
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)//对每一个像素点分析 
    	{
    		if(FindNeighborSum(i,j,r,A)<=t) sum++;
		}
	}
	
	cout<<sum;
    
    return 0;
}

暴力求解：70分，要返回一个double类型的值，不然的话有些不是较暗区域的点也会被计为较暗区域

原本我想 分区域来运算，当邻域像素点个数为最大值（2*r+1）*（2*r+1）时用二维差分，否则用暴力

但是还是会超时

#include<iostream>
#include<bits/stdc++.h>

using namespace std;


int A[601][601];
int n;//长宽都为n个像素

int d[601][601];//记录（i，j）点的前缀和 

double FindNeighborSum(int i,int j,int r,int A[][601])
{
	int suml=0;//像素和 
	int gs=0;//领域 中的像素个数 
	for(int x=i-r;x<=i+r;x++)//找到每一个领域像素点 
	{
		for(int y=j-r;y<=j+r;y++)
		{
			if(x>=0&&x<n)
			{
				if(y>=0&&y<n)
				{
				suml+=A[x][y];
				gs++;
				}
				
			}
		}
	}
	
	double result=(double)suml/gs;//要用double不能用int，不然等于t的数量会变多 
	return result;//
}

int main()
{
    
    
	int L;//像素的取值范围
	int r;//领域的范围
	int t;//阈值，当领域内的均值小于或等于阈值t时是较暗区域
	
	memset(d,0,sizeof d);//将d清零 
	
	cin>>n>>L>>r>>t;
	 
	 for(int i=0;i<n;i++)
	 {
	 	for(int j=0;j<n;j++)
	 	{
	 		cin>>A[i][j];
	 	
	 	d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+A[i][j]; 
	 	//cout<<d[i][j]<<endl;
		 }
	 	
	 	
	 }
    
    
    int sum=0;//记录较暗区域个数 
    int NeighborSum=0;//记录邻域中像素数值之和 
    
    double NeighborAvg=0;
    
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)//对每一个像素点分析 
    	{	
    		
    		if(i-r>=0&&i+r<n&&j-r>=0&&j+r<n)//分区域来运算，当邻域像素点个数为最大值（2*r+1）*（2*r+1）时用差分，否则用暴力
			{
				
				NeighborSum=d[i+r][j+r]-d[i+r][j-r-1]-d[i-r-1][j+r]+d[i-r-1][j-r-1];
				
				NeighborAvg=(double)NeighborSum/((2*r+1)*(2*r+1));
				if(NeighborAvg<=t) sum++;
	     	}
			 
			 else
			 {//邻域的上下左右有些地方不全 
			 	if(FindNeighborSum(i,j,r,A)<=t) sum++;	  
			  } 
    		
		}
	}
	
	cout<<sum;
    
    return 0;
}

从上面的分区域到下面的满分优化，关键是怎么得到邻域的像素点个数，上面的分区域方法如果所判断的像素点（i，j）的邻域没有缺少，即邻域像素点个数达到最大（2*r-1）*（2*r-1），如果（i，j）的邻域不完整，那就暴力的一个一个判断使得gs++来得到邻域中像素点的个数。

可以通过邻域的上下左右来求得邻域中像素点的个数

如图，如果此时红色笔圈起来的数7是当前判断到的像素，设为（i，j），r=2, 那么（i，j）的邻域就应该是如图画的正方形，红色直线=left=j-r;? 橙色直线=right=j+r ，蓝色直线=top=i-r；绿色直线=buttom=i+r；

所以这个邻域中像素点的个数 等于 (right-left+1)*(buttom-top+1)

这是理想的情况，即邻域是完整的

当邻域不完整时，应该通过判断来调整上下左右的取值，但是像素点个数求法还是一样的

? ? ? ? ? ? ? if(i-r<0)//上边不够
?? ??? ??? ??? ?top=0;
?? ??? ??? ??? ?else//上边够那么可能下边不够?
?? ??? ??? ??? ?{
?? ??? ??? ??? ?if(i+r>=n)//下边不够?
?? ??? ??? ??? ?buttom=n-1;?? ?
?? ??? ??? ??? ?}
?? ??? ??? ??? ?
?? ??? ??? ??? ?
?? ??? ??? ??? ?if(j-r<0)//左边不够
?? ??? ??? ??? ?left=0;
?? ??? ??? ??? ?else?? ? ?
?? ??? ??? ??? ?if(j+r>=n)//右边不够
?? ??? ??? ??? ?right=n-1;?

再用前缀和来求解一个区域中像素点的数值和

优化：用二维差分，记录一下我的第一次自己优化?

#include<iostream>
#include<bits/stdc++.h>

using namespace std;


int A[601][601];
int n;//长宽都为n个像素

int d[601][601];//记录（i，j）点的前缀和 

int main()
{
    
    
	int L;//像素的取值范围
	int r;//领域的范围
	int t;//阈值，当领域内的均值小于或等于阈值t时是较暗区域
	
	memset(d,0,sizeof d);//将d清零 
	
	cin>>n>>L>>r>>t;
	 
	 for(int i=0;i<n;i++)
	 {
	 	for(int j=0;j<n;j++)
	 	{
	 		cin>>A[i][j];
	 	
	 	d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+A[i][j]; 
	 	//cout<<d[i][j]<<endl;
		 }
	 	
	 	
	 }
    
    
    int sum=0;//记录较暗区域个数 
    int NeighborSum=0;//记录邻域中像素数值之和 
    
    double NeighborAvg=0;
    
    int Neighbor=0;//记录邻域中像素个数 
    
    int left=0,right=0,top=0,buttom=0;//记录邻域的上下左右，方便计数 
    
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)//对每一个像素点分析 
    	{
    		
                //首先将邻域当作理想情况，后面通过判断再调整
    		    top=i-r;
			 	buttom=i+r;
			 	left=j-r;
			 	right=j+r;
			 	
			 	
			 	if(i-r<0)//上边不够
				top=0;
				else//上边够那么可能下边不够 
				{
				if(i+r>=n)//下边不够 
				buttom=n-1;	
				}
				
				
				if(j-r<0)//左边不够
				left=0;
				else	  
				if(j+r>=n)//右边不够
				right=n-1; 
				
				Neighbor=(buttom-top+1)*(right-left+1); //邻域中像素点个数 
					  
				
				NeighborSum=d[buttom][right]-d[buttom][left-1]-d[top-1][right]+d[top-1][left-1];
				//cout<<NeighborSum<<endl;
				NeighborAvg=(double)NeighborSum/Neighbor;
				if(NeighborAvg<=t) sum++;
		
		  
				  
			  } 
    		
	}
	
	cout<<sum;
    
    return 0;
}

我自己的理解，之前看过一篇特别好的差分法的文章，可惜找不到了

差分法就是在输入的时候求得对应位置的前缀和，当你需要对某个区间或区域进行加减时不用一个一个加减，直接对前缀和数组操作

一维差分：

int n=10;
for(int i=0;i<n;i++)
{
cin>>A[i];
d[i]=d[i-1]+A[i];//前缀和数组，代表第i位以及前面所有数据的和
}

//对[1,5]的数据全部加1
d[1]+=1;
d[5]-=1;

//只需要对区间两端的前缀和数组进行操作即可
//A[i]=d[i]-d[i-1];//得到新的加一之和的值

例题：非零段划分202109-2 非零段划分--C++-CSDN博客? ??

二维差分：

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>A[i][j];
d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+A[i][j];
}
}

当i=3，j=3时，d[i][j]就是如图左上角的所有数之和

这样我们通过输入就可以得到每一个数的二维前缀和，当我们想要求一个区域的所有数之和（在本题中相对于求邻域中的所有数值之和），当我们想要求红色区域的所有数之和，可以用黄色区域所有数之和即d[4][5]，减去蓝色区域所有数之和即d[4][2]，再减去粉色区域所有数之和即d[1][5]，重复减去的区域要加回来，加上d[2][2],就可以得到想要求的区域的所有数之和

差分法~超详细（公式+原理+例题）-CSDN博客