CCF-CSP考试2021年4月第2题(202104-2邻域均值)

题目:计算机软件能力认证考试系统

特别注意评测用例规模与约定!

        70 的测试数据满足 n≤100、r≤10。

        全部的测试数据满足 0<n≤600、0<r≤100 且 2≤t<L≤256。

思路:

刚开始直接用四层for循环遍历,暴力求解,只得了70分,运行时间超时,需要对代码的循环进行优化。

通过分析可以知道,矩阵中同一行元素邻域的纵向范围是一样的,变化的是横向范围,并且同一行相邻的两个元素的邻域范围重合度非常高,所以我们可以用同一行的前一个元素的邻域来避免重复计算。

在同一行中,元素邻域的范围经历扩张、大小不变位置平移以及收缩这三个阶段。(j是元素在某一行的位置,r是邻域的范围)

j-r<=0时,(相比于前一个元素)邻域扩张,这时需要考虑j+r是否超过了矩阵的边界:

        若j+r超过了矩阵边界,邻域范围不变(特殊情况);否则,邻域将扩张。

j-r>0时,(相比于前一个元素)邻域有平移和收缩两种情况:

        当j+r<=n-1时,邻域大小保持不变位置向右平移;当j+r>n-1时,邻域开始收缩。

代码1:暴力遍历(70分)

#include<iostream>
using namespace std;
int twoArray[600][600];
int main(){
	// n是矩阵的边长,L是最大灰度值,r指明附近元素的具体范围,t是阈值 
	int n,L,r,t;
	cin>>n>>L>>r>>t;
	// count计数暗区域总数 
	int count=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>twoArray[i][j];
		}
	}
	
	for(int i = 0;i<n;i++){
		for(int j=0;j<n;j++){
			double temp = 0; // 记录某元素附近所有元素的像素和 
			int num = 0; // 记录某元素附近所有元素个数 
			// k1到k4表示某元素附近元素的边界 
			int k1=0,k2=0,k3=0,k4=0;
			if(j-r<0){ k1=0; }  // 横向左 
			else if(j-r>=0){ k1=j-r; }
			
			if(j+r>=n){ k2=n-1; } // 横向右 
			else if(j+r<n){ k2 = j+r; }
			
			if(i-r<0){ k3=0; } // 纵向上 
			else if(i-r>=0){ k3=i-r; }
			
			if(i+r>=n){ k4=n-1; } // 纵向下 
			else if(i+r<n){ k4=i+r; }
			
			for(int m=k3;m<=k4;m++){
				for(int n=k1;n<=k2;n++){
					temp+=twoArray[m][n];
					num++;
				}
			}
			if((double)(temp/num) <= t){
				count++;
			}
		}
	}
	cout<<count;
}

代码2:优化后(100分)

#include<iostream>
using namespace std;
int twoArray[600][600];
int main(){
	int n,L,r,t;
	cin>>n>>L>>r>>t;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>twoArray[i][j];
		}
	}
	int count = 0;
	// 计算均值
	for(int i=0;i<n;i++){
		// 先算出每行第一个元素的邻域值之和
		int start_y=i-r>0?i-r:0;
		int bound_y=i+r>n-1?n-1:i+r;
		int bound_x=0+r>n-1?n-1:r; 
		double sum = 0;
		int num = 0;
		for(int j=start_y;j<=bound_y;j++){
			for(int k=0;k<=bound_x;k++){
				sum+=twoArray[j][k];
				num++;
			}
		}
		if((sum/num)<=t){
			count++;
		}
		// 同一行元素的 start_y bound_y都是一样的,不一样的是横向的边界 
		for(int j=1;j<n;j++){
			if(j-r<=0){
				if(j+r<=n-1){
					// 邻域范围在扩张 
					for(int k=start_y;k<=bound_y;k++){
						sum+=twoArray[k][j+r];
						num++;
					}
				}
			}
			else if(j-r>0){
				if(j+r<=n-1){
					// 邻域范围不变 
					for(int k=start_y;k<=bound_y;k++){
						sum=sum+twoArray[k][j+r]-twoArray[k][j-r-1];
						// num值不变 
					}
				}
				else{
					// 邻域范围在收缩 
					for(int k=start_y;k<=bound_y;k++){
						sum-=twoArray[k][j-r-1];
						num--;
					}
				}
			}
			if((sum/num)<=t){
				count++;
			}
		}
	} 
	cout<<count;
}

上一篇:P7072 [CSP-J2020] 直播获奖


下一篇:每日一题:600.不含连续1的非负整数