Category: Coding | Yuhang's Blog

Category : Coding

经典游戏Green Hackenbush。给定一个有根图，每次删除一条边，每条边删除后，不再和根相连的所有边也自动删除。无法删除者为负。公平游戏版本中，两个玩家都可以删所有的边。 Read more

2021-02-16 Coding

程序竞赛中的博弈论入门。Nim游戏，SG函数，常见策略和变形。 Read more

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

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

2021-01-21 Coding

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

2021-01-18 Coding

背包的数学记法。 Read more

思路和现有的题解都有些差别，所以稍微写一下。 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 \n... 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),h... Read more

2020-12-31 Coding