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博客