Eric Way's Personal Site

LightOJ 1027 & LightOJ 1395: Expectation

Two versions of a expectation problem, solved using properties of expectations of random variables and dynamic programming. Read more

2021-01-28 CodingMathematics

题目链接题意：给定一棵无根树，求出在每个节点被分别删除的情况下，剩下的森林中每棵树直径的最大值。 Read more

2021-01-21 Coding

对于一个树上问题，我们递归求解时需要将子问题的答案进行合并。如果求解时，我们需要利用若干大型数据结构（包括数组、map、set等）才能获得以... Read more

2021-01-18 Coding

背包的数学记法。 Read more

2021-01-17 CodingMathematics

思路和现有的题解都有些差别，所以稍微写一下。 Read more

2021-01-11 Coding

首先将所有点按横坐标、纵坐标排序，并删掉重复的点。然后分别求下凸壳和上凸壳。初始状态是点$P_0$和$P_1$。本质是单调队列，每次添加一个连边，保证删除队尾在凸包内的点。队尾的点在凸包内外，... Read more

2021-01-09 Coding

考虑状态转移方程： $$ f(i)=\min_{j \le i} \{g(j)+w(i,j)\} $$ 其中最小值可能改为最大值；$j \le i$可能改为$j<i$或$j \... Read more

2021-01-09 Coding

考虑如下形式的状态转移方程： $$ f(i) = \max_{j < i} \{ y(j) - x(j) k(i) \} +h(i) $$ 其中$x(j),y(j),k(i),... Read more

2020-12-31 Coding

考虑状态转移方程： $$ f(i)= \min _ {L(i)\le j \le R(i)} \{g(j)\} + h(i) $$ 其中$i\le N$， $j \le M$。显然暴... Read more

2020-12-29 Coding

更换树根会导致树的某个性质发生改变，而题目需要我们分别求出以每一点为根时，对应的性质的值。 Read more

2020-12-21 Coding