详解CCF-CSP 202312-3 树上搜索

详解CCF-CSP 202312-3 树上搜索

原题连接

202312-3 树上搜索
在这里插入图片描述

代码及详细注释

//一个树形结构的处理程序,主要用于处理一些权重相关的查询
#include <iostream>
#include <vector>
#include <set>

//定义全局变量
//好处:
//(1)不是局部变量,不用入栈出栈,效率更高
//(2)不用传参,不用拷贝,效率更高
//(3)不需要寻址,效率更高
std::vector<long long> wi, temp; //wi存储当前节点及其子节点的权重,temp存储每个节点的输入权重
std::vector<std::vector<int>> ls; //存储树的邻接列表
std::set<int> yes, no; //yes存储本次查询中可访问且已访问的节点,no存储本次查询中不可访问,即已经被丢弃的节点

//深度优先搜索
void dfs(int node) {
	yes.insert(node); //将当前节点添加到已访问集合中
	for (int i : ls[node]) {
		//如果子节点没有被丢弃
		if (no.find(i) == no.end()) {
			dfs(i); //递归搜索子节点
			wi[node] += wi[i]; //更新当前节点的权重,当前节点的权重等于当前节点的权重加上子节点的权重
		}
	}
}


//获取最小差异权重的节点索引
int getMinIdx(int currentNode){
	int minDiffNode = 1; //初始化最小差异权重的节点索引
	long long minDiff = LLONG_MAX; //初始化最小差异权重
	for (int j : yes) {
		long long diff = std::abs(wi[currentNode] - 2 * wi[j]); //计算以currentNode为根节点的子树的权重和与以j为根节点的子树的权重和的差异权重
		if (diff < minDiff) { //如果差异小于最小差异权重
			minDiff = diff; //更新最小差异权重
			minDiffNode = j; //更新最小差异权重的节点索引
		}
	}
	return minDiffNode; //返回最小差异权重的节点索引
}

//检查目标节点是否在子树中
bool check(int minDiffNode, int targetNode) {
	if(minDiffNode == targetNode) return true; //如果最小差异权重的节点索引等于目标节点,返回true

	for (int i : ls[minDiffNode]) { //遍历最小差异权重的节点的所有子节点
		if (no.find(i) != no.end()) continue; //如果子节点在不可访问集合中,跳过
		if (check(i, targetNode)) return true; //递归检查子节点是否在子树中
	}
	return false; //返回false
}

int main() {

	int n, m; //定义全部的类别和需要查询的类别数量
	std::cin >> n >> m;

	temp.resize(n + 1); //调整临时权重的大小,大小设置为n+1是因为下标从1开始
	ls.resize(n + 1); //调整邻接列表的大小,大小设置为n+1是因为下标从1开始

	//输入每个节点的权重,存储到temp中,下标从1开始
	for (int i = 1; i <= n; i++) {
		std::cin >> temp[i];
	}

	//初始化邻接列表,方便使用[]进行访问
	for (int i = 1; i <= n; i++) {
		ls[i] = std::vector<int>();
	}

	//输入树的邻接列表,下标从2开始,1为根节点,根节点没有父节点
	for (int i = 2; i <= n; i++) {
		int parent;
		std::cin >> parent;
		ls[parent].push_back(i);
	}

	//输入与遍历所有查询节点
	for (int queryIndex = 0; queryIndex < m; ++queryIndex) { // 遍历所有查询
		int targetNode; // 目标节点(类别)
		std::cin >> targetNode; // 输入目标节点
		no.clear(); // 清空不可访问集合

		int currentNode = 1; // 从根节点开始
		while (true) {
			wi = temp; // 重置权重为每个节点的权重
			yes.clear(); // 清空已访问集合
			dfs(currentNode); // 从当前节点开始深度优先搜索,计算当前节点及其子节点的权重和

			// 如果只有一个节点,表明currentNode就是目标节点
			if (yes.size() == 1) {
				break;
			}

			 获取最小差异权重的节点索引
			int minDiffNode = getMinIdx(currentNode); 

			// 如果目标节点在子树中,更新当前节点;否则,将该节点添加到不可访问集合中
			if (check(minDiffNode, targetNode)) {
				currentNode = minDiffNode; // 如果目标节点在子树中,更新当前节点,用于下一次搜索
			}
			else {
				no.insert(minDiffNode); // 否则,将该节点添加到不可访问集合中
			}

			std::cout << minDiffNode << " "; // 输出当前节点索引
		}
		std::cout << "\n"; // 输出换行
	}


	return 0;
}

收获

  • 基于全局变量的性质和C++内存管理的相关知识,对程序中的函数的参数传递及程序的性能进行优化
  • vector在使用[]进行随机访问之前,一定要初始化容量
  • 最大长整形的写法:LLONG_MAX

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

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

相关文章

《DiffusionNER: Boundary Diffusion for Named Entity Recognition》

Submitted 22 May, 2023; originally announced May 2023. Comments: Accepted to ACL 2023, submission version https://github.com/tricktreat/DiffusionNER 在这里插入图片描述 问题&#xff1a; 命名实体识别任务中存在的噪声跨度&#xff08;边界不清晰&#xff09…

MS17-010---利用“永恒之蓝”漏洞攻击 win7主机

免责声明:本文仅做技术交流与学习.... 目录 一.前置知识 1.何为永恒之蓝&#xff1f; 2.什么是SMB协议&#xff1f; 3.SMB工作原理是什么&#xff1f; 二、实验环境 三、实验步骤 nmap扫描 msf一把梭哈 shell执行命令 远程连接 一&#xff0e; 二&#xff0e; 一.前…

数字化转型新篇章:企业通往智能化的新范式

早在十多年前&#xff0c;一些具有前瞻视野的企业以实现“数字化”为目标启动转型实践。但时至今日&#xff0c;可以说尚无几家企业能够在真正意义上实现“数字化”。 在实现“数字化”的征途上&#xff0c;人们发现&#xff0c;努力愈进&#xff0c;仿佛终点愈远。究其原因&a…

大象机器人开源协作机械臂myCobot 630 全面升级!

1. 开篇概述 在快速发展的机器人技术领域中&#xff0c;Elephant Robotics的myCobot 600已经证明了其在教育、科研和轻工业领域的显著适用性。作为一款具备六自由度的机械臂&#xff0c;myCobot 600以其600mm的工作半径和2kg的末端负载能力&#xff0c;满足了多样化的操作需求。…

VUE的生命周期图和各函数

函数 beforeCreate(){ }, created(){ }, beforeMount(){ }, mounted(){ }, beforeUpdate(){ }, updated(){ }, beforeDestroy(){ }, destroyed(){ } 创建时生命周期图 运行时生命周期图

Java---数据类型与变量

1.字面常量 字面常量就是我们经常所说的常量&#xff0c;常量即在程序运行期间&#xff0c;固定不变的量。且常量是无法改变的&#xff0c;如果我们的代码有改变常量的操作&#xff0c;程序就会报错。 1.1字面常量的分类 字符串常量&#xff0c;整型常量&#xff0c;浮点数常…

XMind轮播图banner测试点

banner测试点 显示1到5张banner图片 [1,5] 6 1 一张不轮播 5 3 0可选 自动轮播,3秒切换一张 鼠标悬停,不轮播 实心为当前图 点击可以跳转 点击左,切换一张图片 点击右, 切换一张图片…

使用MATLAB/Simulink的PID控制系统设计和自动调整

书籍&#xff1a;Pid Control System Design and Automatic Tuning Using Matlab/Simulink 作者&#xff1a;Liuping Wang 出版&#xff1a;Wiley-IEEE Press 书籍下载-《使用MATLAB/Simulink的PID控制系统设计和自动调整》本书涵盖了具有操作约束的PID控制系统的设计、实施…

Android使用ProtoBuf 适配 gradle7.5 gradle8.0

ProtoBuf 适配 Gradle7.5 gradle-wrapper.properties 配置 distributionUrlhttps\://services.gradle.org/distributions/gradle-7.5-bin.zipProject&#xff1a;build.gradle: plugins {id com.android.application version 7.4.2 apply falseid com.android.library versio…

模拟 枚举 贪心(C++ 题目 代码 注解)

目录 题目一&#xff1a; 题目描述 输入描述: 输出描述: 输入 输出 说明 代码&#xff1a; 题目二&#xff1a; 题目描述 输入描述: 输出描述: 输入 输出 代码&#xff1a; 题目三&#xff1a; 题目描述 输入描述: 输出描述: 输入 输出 输入 输出 输入…

C语言函数指针的使用、函数指针数组及使用、指向函数指针数组的指针,指针进阶版的冒泡排序等介绍

文章目录 前言一、函数指针的使用1. 加减乘除计算器普通实现2. 加减乘除计算机函数指针实现 二、函数指针数组1. 函数指针数组的书写2. 两个有趣的代码3. 函数指针数组的使用 三、指向函数指针数组的指针四、指针进阶_冒泡排序1.整型冒泡排序2. C语言qsort函数3. 仿写C语言qsor…

笔试刷题-Day11

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 一、游游的水果大礼包 题目链接&#xff1a;https://ac.nowcoder.com/acm/problem/255193 类型&#xff1a;求一个表达式的最值&#xff08;并不是贪心,因为该题条件太少&…

PC 自动化测试入门 - pywinauto 上篇:初识

文章目录 前言PC 自动化测试 是什么&#xff1f;常用 PC 自动化测试工具pywinauto 是什么&#xff1f;Windows上支持的可访问性技术列表 操作记事本自动写入问题app Application(backend"uia").start("notepad.exe") 无法正常启动组件选择器和 print_cont…

clickhouse学习笔记05

ClickHouseSpringBoot2.XMybatisPlus整合搭建 添加需要的依赖&#xff1a; 添加clickhouse依赖&#xff1a; 配置数据库配置&#xff1a; 我们框架就搭建完了。 ClickHouse的项目案例统计需求讲解 ClickHouse的项目案例统计库表和数据准备 添加数据&#xff1a; 数据都插入进来…

算法必备数学基础:图论方法由浅入深实践与应用

作者介绍&#xff1a;10年大厂数据\经营分析经验&#xff0c;现任大厂数据部门负责人。 会一些的技术&#xff1a;数据分析、算法、SQL、大数据相关、python 欢迎加入社区&#xff1a;码上找工作 作者专栏每日更新&#xff1a; LeetCode解锁1000题: 打怪升级之旅 python数据分析…

python 入门第三天(高级进阶:str、set、dict、slice、推导式、高级变量类型的公共语法)

一、字符串str 字符串就是一串字符&#xff0c;是编程语言中表示文本的数据类型 1. 字符串定义 Python中可以使用一对双引号或者一对单引号定义字符串 str1 hello str2 "hello" 2. 获取字符串中元素 和列表一样&#xff0c;字符串也是通过索引获取元素 str …

CentOS7上安装部署Consul服务(小白版)

文章目录 1.Consul服务介绍2.Consul服务下载安装3.Consul服务配置3.1.创建Consul服务的运行用户3.2.下载服务配置生成脚本3.3.配置执行脚本需要的临时变量3.4.生成配置文件3.5.启动测试3.6.开机自启配置 1.Consul服务介绍 Consul 是一种开源的服务网格解决方案&#xff0c;由 …

pytorch库 01 安装Anaconda、Jupyter,Anaconda虚拟环境连接pycharm

文章目录 一、安装Anaconda1、卸载Anaconda&#xff08;可选&#xff09;2、下载并安装Anaconda3、配置环境变量4、桌面快捷方式 二、安装 PyTorch&#xff08;GPU 版&#xff09;库1、创建虚拟环境&#xff0c;并安装一些常用包2、GPU 基础3、检查驱动4、安装CUDA&#xff08;…

Linux搭建局域网私有yum仓库/配置本地光盘镜像仓库/搭建公有yum仓库--7700字详谈

帮助与补全功能 1.补全 yum &#xff08;options&#xff09;COMMAND check check-update clean deplist downgrade erase fs fssnapshot groups help history info install list makecache provides reinstall repo-pkgs repolist search shell swap update update-minimal …

每周一算法:单源次短路

题目描述 “您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。 比荷卢经济联盟有很多公交线路。每天公共汽车都会从一座城市开往另一座城市。沿途汽车可能会在一些城市&#xff08;零或更多&#xff09;停靠。 旅行社计划旅途从 S S S 城市出发&#xff0c;到 F …