~ Esoteria Algorithm in Reverse Observatory

Cover Image

树的中心

CAUTION
本文含有大段写得很丑的 Golang,可能会引起不适(

题目描述
蓮子和梅莉玩游戏。梅莉掏出一棵无根树,要蓮子在规定时间内确定一个点,使得这个点到其他点的最长路径最小,蓮子是一个只会 AK IPhO 的巨佬,所以她请教你帮她,事成之后就和梅莉结婚。

轻重链剖分与树上路径操作

Prologue

前置技能

一些定义

  • 树上的路径称为树链
  • 非叶节点的儿子中子树大小最大的儿子为重儿子,其它为轻儿子
  • 从非叶节点到重儿子的边称为重边,其它为轻边
  • 由重边构成的链称为重链,其它为轻链
    • 重链中深度最小的节点为链顶
    • 重链的链顶都是其父节点轻儿子
    • 轻叶节点独自构成一条重链
  • 将树分割为重链和轻链即为剖分
  • 树链剖分就是用数据结构去维护重链和轻链
  • 左闭右开区间跟国际接轨

分块

Prologue

  • 块:将一个数列分为若干个不相交区间,每一个区间称为块
  • 完整块:进行区间操作时被区间完全覆盖的块
  • 不完整块:进行区间操作时部分被区间覆盖的块

LGOJ P1174 | 打砖块

Portal

假设所以砖块都为 NN,无论打的顺序如何对后面的砖块都没有影响,这就是一个普通的多重背包。

NOIAC52 | 计算机

Portal

计算机将重复上述过程,直到稳定

题中改写值的操作相当于最短路中对最短路长度的更新。每个节点上的值可以看作是从 1 号点到其它点的最短路的长度,而每个边的编号可以看作是该边的权。

hzwer7629 | 小奇挖矿 2

Portal

对于 60% 的数据,可以直接写出状态转移方程:
fi=max{fi4,fi7}+aif_i=\max {f_{i-4},f_{i-7}} +a_i

然后当成普通的一维 DP 做可以拿下 60pts。

对于 100% 的数据,由于 m109m\leq 10^9 如果直接用数组记录每个点的收益显然会 MLE。

hzwer4605 | 肥得更高

Portal

解法很多,机房有巨佬强行用线段树做。

由于每次施肥都会使肥力下降,最小值可以直接贪心解决,不断对肥力最低的施肥即可。如果求最大值,由于施肥使肥力下降,所以不更新当前最优选择显然是错误的。

NOIP2010T3 | 关押罪犯

Portal

考虑这样一个问题:是否存在一种分配罪犯的方案,使冲突事件的影响力不超过 midmid 。显然,当 midmid 较小时可行的方案对于更大的 midmid 仍然可行。换言之,本题的答案具有单调性,可以通过二分法,把求最值的问题转化为判断问题。

NOIP2017D2T2 | 宝藏

Portal

观察题目,12 个顶点,1000 条边,显然有很多重边(显然是状压 DP)。所以在输入时不断取最短边,最后边数不超过 122 条。由于题目求的是一个花费最小的生成树,并不关心从以哪个点为根,显然对于一棵生成树,取不同的点为根只会有深度的差别,在输出时找出所有深度中花费最小的即可,而不必枚举根节点。因为有 12 个顶点,显然状态有一维应为状态压缩的被探索过的顶点。