LibreOJ 2187:「SHOI2014」三叉神经树 – 题解

主要思路

先建好树,大概思考一下应该可以推导出:倍增找标记点,然后根到区间修改。然而正解也是这样写,只不过细节有点多,我在这里提一下:回答询问\(x\)时,先把他父亲提到根,然后找最近的点;找到了就把深度大的全部打标记反过来。

继续阅读LibreOJ 2187:「SHOI2014」三叉神经树 – 题解

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 4th – Group A 解题报告

今天被各路神仙吊打,顺利 gg。

A – Forging 锻造

在考场上我推了个有后效性的 DP,还以为是高斯消元,然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。

首先,对一个概率为\(p\)的事件,它的期望次数是\(\frac{1}{p}\)(参见这里)。然后,考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。

考虑\(dp[1]\)的求法,首先需要两个级别为\(0\)的武器,然后发现无论失败与否都可以保证至少又一个\(0\)级武器,所以我们只需要注意另外一个武器的花费就可以了:

\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]

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