行业知识
【CSP】2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟
2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟
- 2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟
- 题目重述
- 思路
- 遇到的问题(学到的知识)
- 完���代码
2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟
这题原本是需要优化的算法,但是鉴于我弱鸡的实力,考试的时候肯定是不会A出来的第四题的100分的,最多混一混(要是能混到也算是很不错了)。所以这题我就尝试使用暴力来解题,没想到还是拿到了超过了一半的分数。
但是从这道题我也明白了就算是混分也是需要训练的。
题目重述
这题别看那么多公式什么的,实际上就是几句话就能解释清楚。
首先背景是一个公司的,可以用一棵树来表示,上级就是父节点,下属就是子节点,然后对于每个节点我们可以获取一个可重复集合,就是包括自己所有的子节点(包括子节点的子节点,儿子的儿子……)就是整个子树的节点,和自己的集合。
之后我们明白这个集合,然后我们可以针对每一个集合计算一个ans 然后输出。这个ans计算方法就是,遍历这个集合中的所有元素找到离他最近的元素(不能是他自己)然后求出距离后平方,最后ans再加上这个值。
思路
主要就是分两部分,第一部分是求得每个节点的集合,第二部分就是求个每个集合的ans。
第一部分,我们先可以把每个节点的第一层子节点保存下来,然后再递归把每个节点的子树的所有的节点加进去
第二部分,我们先对每个集合进行排个序,然后遍历里面的每个元素,找前后两个点看谁最近,然后加到ans中,最后输出(有个特殊情况,就是只有一个节点的集合求出是0)
遇到的问题(学到的知识)
- 思路问题
本来想着直接用一个递归函数求得,就是边求集合边求每个元素的离得最近的距离,但是发现不太可行,因为集合不仅是每个节点的子节点,而且是整个子树(包含儿子的儿子)
这是幡然醒悟,然后开始写。
- 实现问题:找子节点无限递归无限循环
原来是因为我把每个节点的字节点存到了集合中,也把那个节点本身也存到的集合中,这样就会无限递归不能停止,而且会导致重复添加的问题。
修改办法就是:区别对待添加个if
void getChild(int i, int j) // 父节点是i 子节点是j 要把j的所有子节点都填入到i的child数组中{ if (child1[j].size() == 1) { child[i].push_back(child1[j][0]); return; } for (auto item : child1[j]) { if (item.id == j) // 因为此数组中包括本节点,防止无限递归所以使用了特殊处理此节点 { child[i].push_back(item); } else getChild(i, item.id); }}- 还是发现总是有重复添加
原来在初始的第一层循环中,也是出现了上面的问题,也就是我遍历的两边子树,添加了两遍子树
修改前
for (int i = 1; i
上一篇:怎么注册新浪服务器地址?
下一篇:电子围栏主机发出声音怎么解决视频