POJ1639:Picnic Planning 题解

大体思路

做过 LCT 么?(做过基本上就可以切这一道题)

考虑把跟节点先去掉,然后会产生很多个联通块:每一个连通块求出最小生成树,然后找到整个连通块与根节点连接的最小边,连上。

之后如果还剩下一定的可以使用的度数,我们可以考虑用根节点剩余的边去更新整个最小生成树。具体而言,我们找到了一个\((1, v)\)未使用的边,然后我们找\(1 \to v\)上所有的边,找到一个差值最大的。如果这个差值是正数,那么加入这条边,删去之前的边,就会发现答案减掉了这个正差值。不停重复就可以得到答案。

继续阅读POJ1639:Picnic Planning 题解

LCT 的一类题目

LCT 简述

LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是,LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边,所以很多题目就可以打破一些限制进行求解。

继续阅读LCT 的一类题目

[Fortuna OJ]Aug 10th – Group A 解题报告

A – 数学题

这道题二次函数的暴力分有 60 分,正解来自于论文。

这道题的主要是利用了一个结论,并且运用了辗转相除法的一种思想来对问题进行化简。首先,我们把向量调整至同向,且使\(|\vec{a}| < |\vec{b}|\),然后再来推导一个结论:

结论   对于\(\vec{a}, \vec{b}\),如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\),那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。

这个结论的证明参见《欧几里得算法的应用》。所以,我们就可以大概知道,我们可以将较长的向量分解:\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道,这道题可以笑掉这个\(k \vec{a}\),所以就可以用辗转相除法的套路进行处理。具体见代码:

继续阅读[Fortuna OJ]Aug 10th – Group A 解题报告

P3317:[SDOI2014]重建题解

矩阵树定理的运用

正常来讲,在矩阵树中,我们其实要算的东西就是这个:

\[ \sum_T  \prod_{e \in T} p_e, \forall p_e = 1 \]

我们算的其实就是概率都为\(0/1\)的情况。现在我们要算:

\[ \sum_T \prod_{e \in T} p_e \prod_{e \notin T} (1-p_e) \]

我们可以考虑写成和式内仅与矩阵有关的式子:

\[ \sum_T \prod_{e \in T} p_e \frac{ \prod_e (1 – p_e) }{\prod_{e \in T} (1-p_e) } \]

合并积和式:

\[ \prod_e p_e \sum_T \prod_{e \in T} \frac{p_e}{1 – p_e} \]

然后我们把矩阵的内容改成\( \frac{p_e}{1 – p_e} \)就行了。

继续阅读P3317:[SDOI2014]重建题解

P4899:[IOI2018] werewolf 狼人题解

解法

这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态,我们要找到一个点点权小于\(L\)的点,就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl,其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值,然后按最小生成树的方式去构造重构树;符合狼形规律的 Kruskal 重构树被记为 Tu,其中构造它的方式就是将端点编号最小值赋为边权,然后按最大生成树的方式构造。之后,我们再到主席树中求交集即可,如果有交集那么查询结果为一个不为零的数,输出\(1\)即可;没有交集那么查询结果即为\(0\),输出\(0\)。

继续阅读P4899:[IOI2018] werewolf 狼人题解

Kruskal 重构树

简述

Kruskal 重构树是图的一种生成树,主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质,所以很容易就可以解决边权的取值限制。

建法

Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似,但是结构有所不同:Kruskal 重构树将边权变成点权,点权依深度变小。我们假设有一张这样的图:

继续阅读Kruskal 重构树