小工具知识网

当前位置: 首页 > 行业知识 > 【CSP】2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟

行业知识

【CSP】2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟

2026-11-16 13:24:31 来源:互联网转载

2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟

  • 2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟
    • 题目重述
    • 思路
    • 遇到的问题(学到的知识)
    • 完���代码

      2022–12-4 聚集方差 暴力混分 65分思路 没有算法纯模拟

      这题原本是需要优化的算法,但是鉴于我弱鸡的实力,考试的时候肯定是不会A出来的第四题的100分的,最多混一混(要是能混到也算是很不错了)。所以这题我就尝试使用暴力来解题,没想到还是拿到了超过了一半的分数。

      但是从这道题我也明白了就算是混分也是需要训练的。

      题目重述

      这题别看那么多公式什么的,实际上就是几句话就能解释清楚。

      首先背景是一个公司的,可以用一棵树来表示,上级就是父节点,下属就是子节点,然后对于每个节点我们可以获取一个可重复集合,就是包括自己所有的子节点(包括子节点的子节点,儿子的儿子……)就是整个子树的节点,和自己的集合。

      之后我们明白这个集合,然后我们可以针对每一个集合计算一个ans 然后输出。这个ans计算方法就是,遍历这个集合中的所有元素找到离他最近的元素(不能是他自己)然后求出距离后平方,最后ans再加上这个值。

      思路

      主要就是分两部分,第一部分是求得每个节点的集合,第二部分就是求个每个集合的ans。

      第一部分,我们先可以把每个节点的第一层子节点保存下来,然后再递归把每个节点的子树的所有的节点加进去

      第二部分,我们先对每个集合进行排个序,然后遍历里面的每个元素,找前后两个点看谁最近,然后加到ans中,最后输出(有个特殊情况,就是只有一个节点的集合求出是0)

      遇到的问题(学到的知识)

      1. 思路问题

      本来想着直接用一个递归函数求得,就是边求集合边求每个元素的离得最近的距离,但是发现不太可行,因为集合不仅是每个节点的子节点,而且是整个子树(包含儿子的儿子)

      这是幡然醒悟,然后开始写。

      1. 实现问题:找子节点无限递归无限循环

      原来是因为我把每个节点的字节点存到了集合中,也把那个节点本身也存到的集合中,这样就会无限递归不能停止,而且会导致重复添加的问题。

      修改办法就是:区别对待添加个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);    }}
      1. 还是发现总是有重复添加

      原来在初始的第一层循环中,也是出现了上面的问题,也就是我遍历的两边子树,添加了两遍子树

      修改前

          for (int i = 1; i 

上一篇:怎么注册新浪服务器地址?

下一篇:电子围栏主机发出声音怎么解决视频