【题解】[NOI2002] 贪吃的九头龙 树形 DP—chiimo

我水平很菜,你忍一下。 题面 树形 DP。 首先可以发现, $m>2$ 时,难受度只出现在最大的头吃的果子上(因为我把果子分成最大的头吃的和其他的,其他的里面,相邻的果子让不同的头吃即可)。 然后我定义 $f_{i,j,k}$ 为当前为 $i$ 节点,当前节点分 $j$ 个果子给最大的头,当前节点选 阅读更多…

【题解】Ynoi2010 Brodal queue 分块 — Qiuly

本题不弱于小 Z 的袜子,考虑分块,令 $B$ 为块数。 先考虑单点修改,可以令 $f(x,y)$ 表示从块 $x$ 中选出一个数,然后从块 $y$ 中选出同样的数的方案数,放到平面上,有值的地方就是一个三角形,询问也是询问一个三角形中的 $f(x,y)$ 和。 怎么做修改,对每个颜色维护一个前缀出 阅读更多…

【算法】左偏树(可并堆)— Nt_Yester

前言 关于我想去学环状树却学了左偏树这件事 正文 前置芝士 并查集 性质 根据算法名称就可以知道,这是一个森林中所包含的所有树都向左偏的森林(也是因为他向左偏,并且可以进行合并,所以他也是可并堆)。 算法函数 建树: 很简单,并查集实现(就不放代码了)。 合并: 也就是把两棵树合并先放代码: int 阅读更多…

【算法】DP 之背包 — Nt_Yester

前言 欢迎各位纠错 正文 背包问题,作为 DP 经典问题,也是 OIer 必须掌握的一门算法,一般有 01 背包,完全背包,多重背包。 01 背包 01 背包是背包中最简单也是最基础的,一般用 $w_i$ 表示第 $i$ 个物品的价值,$v_i$ 表示第 $i$ 个物品的体积,而 $f_{i,j}$ 阅读更多…

【算法】并查集 — Nt_Yester

正文 并查集你可以理解为是族谱森林(一开始每个节点初始化为自己),我们用 $f_i$ 表示 $i$ 的父亲,一般有以下操作:并和查。 先来说查,查就是字面意思:查找 $i$ 的最早祖先,我们可以递归查找,查找 $i$ 的父亲,再查找 $i$ 的父亲的父亲,依次递归,就有了以下代码。 int find 阅读更多…

【题解】CF627F Island Puzzle 构造 + 模拟 — Qiuly

这种 d1f 绝对是搞人心态的。 因为一条路径走偶数次是没用的,只考虑树的情况的话,$0$ 走的路径是一定的,简单判断一下即可。 由于操作可逆,将 $0$ 所在目标节点移做根,先把 $0$ 移过去。考虑新增一条边能干啥:对于所在的环,​和 $0$ 最近的节点不动,其他的节点按照顺时针或者逆时针不断轮 阅读更多…