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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/233112.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

springboot3 liquibase SQL执行失败自动回滚，及自动打tag

springboot3 liquibase SQL执行失败自动回滚，及自动打tag

一&#xff1a; 自动执行回滚&#xff0c; 已执行成功的忽略&#xff0c;新sql执行失败则执行新sql文件中的回滚sql pom.xml <dependency> <groupId>org.liquibase</groupId> <artifactId>liquibase-core</artifactId> <version>4.25.0&…
阅读更多...
免费的数据采集软件，最新免费的几款数据采集软件【2024】

免费的数据采集软件，最新免费的几款数据采集软件【2024】

在当今数字化时代&#xff0c;数据是企业决策和业务发展的关键。而如何高效获取数据成为许多企业和研究机构的关注焦点。本文将深入探讨数据采集软件的种类。帮助大家选择最适合自己需求的数据采集工具。 数据采集软件种类 在众多数据采集软件中&#xff0c;有一类强大而多样…
阅读更多...
工作实践中如何使用ThreadLocal?

工作实践中如何使用ThreadLocal?

主要作用 多线程问题主要是多个线程共享一个对象导致的&#xff0c;我们不让他共享就行了&#xff0c;每个线程保存一份自己的对象&#xff0c;自己玩自己的对象&#xff0c;就不会出现线程问题了。 ThreadLocal这个作用就是让线程自己独立保存一份自己的变量副本。每个线程都…
阅读更多...
计算和传输背后的时空观

计算和传输背后的时空观

吞吐和速度(率)经常被混淆&#xff0c;当提到 100Gbps 网卡时&#xff0c;“它很快” 的意义可能只是 “它很多” 100Gbps 指 1s 内发送的比特数为 100G&#xff0c;如果在这 1s 内塞入更多比特&#xff0c;以下是两种方式&#xff1a; 显然&#xff0c;上面是更多&#xff…
阅读更多...
TypeScript入门实战笔记 -- 开篇 为什么要选择 TypeScript ？

TypeScript入门实战笔记 -- 开篇 为什么要选择 TypeScript ？

typescript 在线编辑器http://typescript.p2hp.com/play?#code/JYOwLgpgTgZghgYwgAgJIFUDO1Uhge2QG8AoZc5YAEwC5kQBXAWwCNoBuMikOJiOzGCigA5pwrI4ANzhg4UAPwChozgF8SmmAxAIwwfCGRYcefAAoADlHyXMdDNii4CASmJdyCQ5nwAbCAA6P3wRKxs7ABpkAHJrW0wY1xINEhNnM3MiSlpkAEZonj46GIBrROQ1…
阅读更多...
Python：核心知识点整理大全11-笔记

Python：核心知识点整理大全11-笔记

目录 ​编辑 6.2.4 修改字典中的值 6.2.5 删除键—值对 注意 删除的键—值对永远消失了。 6.2.6 由类似对象组成的字典 6.3 遍历字典 6.3.1 遍历所有的键—值对 6.3.2 遍历字典中的所有键 往期快速传送门&#x1f446;&#xff08;在文章最后&#xff09;&#xff1a; 6.…
阅读更多...
排序：归并排序

排序：归并排序

目录 归并排序——有递归的&#xff1a; 基本思想&#xff1a; 思路分析&#xff1a; 代码分析&#xff1a; 划分区间思路&#xff1a; 代码思路分析&#xff1a; 归并排序——有递归的&#xff1a; 基本思想&#xff1a; 归并排序&#xff08;MERGE-SORT&#xff…
阅读更多...
《Kafka权威指南》读书笔记

《Kafka权威指南》读书笔记

《Kafka权威指南》第一、三、四、六章&#xff0c;是重点。可以多看看。 一、 Kafka的组成 kafka是一个发布与订阅消息系统消息&#xff1a;kafka的数据单元称为"消息"。可以把消息看成是数据库中的一个"数据行"。 消息的key&#xff1a;为key生成一个一…
阅读更多...
鸿蒙开发组件之Image

鸿蒙开发组件之Image

Image组件加载图片方式有三种&#xff1a; 1、网络地址加载 直接Image(xxxx),添加上图片的网络地址就可以了。注意&#xff1a;真机、模拟题调试需要申请"ohos.permission.INTERNET"权限 Image(https://xxxxxxx) 2、PixelMap格式加载像素图 Image(PixelMapObjec…
阅读更多...
【小沐学Python】Python实现语音识别（vosk）

【小沐学Python】Python实现语音识别（vosk）

文章目录 1、简介1.1 vosk简介1.2 vosk模型1.3 vosk服务 2、安装3、测试3.1 命令行测试3.2 代码测试 结语 1、简介 https://alphacephei.com/vosk/index.zh.html Vosk 是一个语音识别工具包。 1.1 vosk简介 支持二十种语言 - 中文&#xff0c;英语&#xff0c;印度英语&#…
阅读更多...
Mac虚拟机CrossOver23破解版下载和许可证下载

Mac虚拟机CrossOver23破解版下载和许可证下载

CrossOver Mac Mac 和 Windows 系统之间的兼容工具。使 Mac 操作系统的用户可以运行 Windows 系统的应用&#xff0c;从办公软件、实用工具、游戏到设计软件&#xff0c; 您都可以在 Mac 程序和 Windows 程序之间随意切换。 系统要求 运行macOS的基于Intel或Apple Silicon 的…
阅读更多...
【原创】【一类问题的通法】【真题+李6卷6+李4卷4(+李6卷5)分析】合同矩阵A B有PTAP=B，求可逆阵P的策略

【原创】【一类问题的通法】【真题+李6卷6+李4卷4(+李6卷5)分析】合同矩阵A B有PTAP=B，求可逆阵P的策略

【铺垫】二次型做的变换与相应二次型矩阵的对应&#xff1a;二次型f&#xff08;x1&#xff0c;x2&#xff0c;x3&#xff09;xTAx&#xff0c;g&#xff08;y1&#xff0c;y2&#xff0c;y3&#xff09;yTBy ①若f在可逆变换xPy下化为g&#xff0c;即P为可逆阵&#xff0c;有P…
阅读更多...
【SpringBoot篇】5种类型参数传递json数据传参的操作

【SpringBoot篇】5种类型参数传递json数据传参的操作

&#x1f38a;专栏【SpringBoot】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f33a;普通参数&#x1f33a;POJO参数&#x1f33a;嵌套…
阅读更多...
Java面试遇到的一些常见题

Java面试遇到的一些常见题

目录 1. Java语言有几种基本类型&#xff0c;分别是什么&#xff1f; 整数类型&#xff08;Integer Types&#xff09;&#xff1a; 浮点类型&#xff08;Floating-Point Types&#xff09;&#xff1a; 字符类型&#xff08;Character Type&#xff09;&#xff1a; 布尔类…
阅读更多...
Unity中Batching优化的GPU实例化（4）

Unity中Batching优化的GPU实例化（4）

文章目录 前言一、构建需要实例化的额外数据二、在顶点着色器&#xff0c;将实例化 ID 从 appdata 存入 v2f 传给片元着色器三、在片断着色器中访问具体的实例化变量三、使用代码修改Shader材质属性&#xff0c;实现GPU实例化后不同对象颜色不同的效果1、在C#测试脚本生成小板凳…
阅读更多...
Redis 环境搭建2

Redis 环境搭建2

文章目录 第2关&#xff1a;使用 Redis 第2关&#xff1a;使用 Redis 本文是接着上篇文章写的第二关代码&#xff0c;部分人再进入第二关时不会保留第一关的配置的环境&#xff0c;可以通过下面一句代码进行检验。 redis-cli -p 7001 -c如果进入到了redis界面就是有环境&…
阅读更多...
Android 分享小结

Android 分享小结

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、微信 分享 三、 QQ 、QQ空间&#xff08;Qz…
阅读更多...
2024 年顶级的 Android 系统修复软件与方法

2024 年顶级的 Android 系统修复软件与方法

您是否正在寻找可以修复 PC 上 Android 操作系统的工具&#xff1f;这是我们精选的最好的 Android 系统修复软件&#xff01; Android 是世界著名的智能手机操作系统。全世界有数百万人使用这个操作系统&#xff0c;这使得它安全可靠。然而&#xff0c;这仍然不能使它完美无缺…
阅读更多...
STM32之SPI总线

STM32之SPI总线

一、SPI总线概述 1、SPI总线介绍 SPI是一种通信协议&#xff0c;它是摩托罗拉公司研发出来的一种通信协议&#xff0c;就有自己的特点&#xff08;串行&#xff0c;并行&#xff0c;单工&#xff0c;半双工&#xff0c;全双工&#xff0c;同步异步&#xff09;。它主要应用于音…
阅读更多...
Kotlin Flow 操作符

Kotlin Flow 操作符

前言 Kotlin 拥有函数式编程的能力&#xff0c;使用Kotlin开发&#xff0c;可以简化开发代码&#xff0c;层次清晰&#xff0c;利于阅读。 然而Kotlin拥有操作符很多&#xff0c;其中就包括了flow。Kotlin Flow 如此受欢迎大部分归功于其丰富、简洁的操作符&#xff0c;巧妙使…
阅读更多...
最新文章

Copyright @ 2022~2023