高度由习惯堆积

分类 算法:差分 下的文章

February 17, 2019

NOIP2015 运输计划

题目公元 2044 年,人类进入了宇宙纪元。L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,...

HDU5156 (树上差分 离线 树状数组)

题目给出一颗大小为n的树,以1为根,然后给出m次染色,每次将节点u加上一种颜色(一个节点可以有多个颜色)。最后查询树上每个节点对应子树上包含的不同颜色数量。思路1(离线+树状数组)这个算法较为自然,对于每一个点,我们先将其按照R[i]排序,然后根据这个顺序,完全可以按照HDU3333 Turing Tree那题的做法,很容易求解。