CCF-CSP真题《202312-3 树上搜索》思路+c++满分题解

2024-04-21 06:36

本文主要是介绍CCF-CSP真题《202312-3 树上搜索》思路+c++满分题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全

问题描述

试题编号:202312-3
试题名称:树上搜索
时间限制:1.0s
内存限制:512.0MB
问题描述:

题目背景

问题描述

输入格式

输出格式

样例1输入

5 2
10 50 10 10 20
1 1 3 3
5
3

样例1输出

2 5
2 5 3 4

样例解释

子任务

真题来源:树上搜索

感兴趣的同学可以如此编码进去进行练习提交

 c++满分题解:

#include <bits/stdc++.h>
using  namespace std;
inline long long read()
{long long x = 0, f = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while ( c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}return x * f;
}struct Node
{long long Weight;long long WeightSum;long long Index;bool IsOut;Node* Child, * Brother, * Above, * LastChild, * PrevBrother;Node(long long Weigh, long long i) : Weight(Weigh), Child(nullptr), LastChild(nullptr), Above(nullptr), Brother(nullptr), WeightSum(Weigh), PrevBrother(nullptr), Index(i) {}
};Node* Nodes[2010];void LinkNode(Node* Parent, Node* Child)
{if (!Parent || !Child) return;Child->Above = Parent;if (!Parent->Child){Parent->Child = Child;Parent->LastChild = Child;return;}Parent->LastChild->Brother = Child;Child->PrevBrother = Parent->LastChild;Parent->LastChild = Child;
}long long AccWeights(Node* CurRoot)
{if (!CurRoot) return 0;CurRoot->WeightSum = CurRoot->Weight;Node* CurNode = CurRoot->Child;while (CurNode){CurRoot->WeightSum += AccWeights(CurNode);CurNode = CurNode->Brother;}return CurRoot->WeightSum;      
}bool HasTarIndex(Node* Root, long long Tar)
{if (!Root) return 0;else if (Root->Index == Tar) return 1;Node* CurNode = Root->Child;while(CurNode){if (HasTarIndex(CurNode, Tar)) return 1;CurNode = CurNode->Brother;}return 0;
}long long RemovedParents[2010]{-1}, RemovedChilds[2010]{-1};
long long RemovedPairs = 0;
void RemoveNode(Node* TarNode)
{if (!TarNode) return;if (!TarNode->PrevBrother) TarNode->Above->Child = TarNode->Brother;else TarNode->PrevBrother->Brother = TarNode->Brother;if (!TarNode->Brother) TarNode->Above->LastChild = TarNode->PrevBrother;else TarNode->Brother->PrevBrother = TarNode->PrevBrother;TarNode->Above = nullptr;TarNode->Brother = nullptr;TarNode->PrevBrother = nullptr;
}
void ReBuild()
{for (long long i = 0; i < RemovedPairs; ++i) LinkNode(Nodes[RemovedParents[i]], Nodes[RemovedChilds[i]]);RemovedPairs = 0;
}
long long GetDelta(Node* TarNode, long long& CurTotalWeight)
{if(!TarNode) return 114514;else if (!TarNode->Above) return TarNode->WeightSum;return abs(CurTotalWeight - 2 * TarNode->WeightSum);
}
long long CurMin = 0, CurIdx = 0;
void Bianli(Node* CurRoot, long long& CurTotalWeight)
{if (!CurRoot) return;long long Delta = GetDelta(CurRoot, CurTotalWeight);//cout << CurRoot->Index << ' '<<Delta<<'\n';if (Delta < CurMin || (CurMin == Delta && CurRoot->Index < CurIdx)){CurMin = Delta;CurIdx = CurRoot->Index;}Node* CurNode = CurRoot->Child;while (CurNode){Bianli(CurNode, CurTotalWeight);CurNode = CurNode->Brother;}
}
void PrintTree(Node* CurRoot)
{if (!CurRoot) return;cout << CurRoot->Index << '\n';Node* CurNode = CurRoot->Child;while (CurNode){cout << '\t' << CurNode->Index << '\n';system("pause");CurNode = CurNode->Brother;}CurNode = CurRoot->Child;while (CurNode){PrintTree(CurNode);CurNode = CurNode->Brother;}
}
int main()
{long long n = read(), m = read();for (long long i = 1; i<= n; ++i) Nodes[i] = new Node(read(), i);for (long long i = 2; i <= n; ++i) LinkNode(Nodes[read()], Nodes[i]);long long Index = 0;for (long long i = 1; i <= m; ++i){RemovedPairs = 0;Index = read();Node* CurRoot = Nodes[1];while(CurRoot->Child){/*cout << "___________________\n";PrintTree(CurRoot);cout << "___________________\n";*/long long SumWeight = AccWeights(CurRoot);CurMin = SumWeight, CurIdx = 0;Bianli(CurRoot, SumWeight);cout << CurIdx << ' ';if (HasTarIndex(Nodes[CurIdx], Index)) CurRoot = Nodes[CurIdx];else{RemovedParents[RemovedPairs] = Nodes[CurIdx]->Above->Index;RemovedChilds[RemovedPairs] = Nodes[CurIdx]->Index;++RemovedPairs;RemoveNode(Nodes[CurIdx]);}}ReBuild();cout << '\n';}for (long long i = 1; i<= n; ++i) delete Nodes[i];
}

运行结果: 

这篇关于CCF-CSP真题《202312-3 树上搜索》思路+c++满分题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/922384

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝