Yuhang's Blog

Luogu P3256：半平面交

思路和现有的题解都有些差别，所以稍微写一下。 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

考虑状态转移方程： $$ 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

题意给定一棵树，对于树上任意路径$P$，定义毛毛虫为点集... Read more

2020-12-20 Coding

树上, 状态必然有一个维度是“子树的根节点编号”, 记作$u$. 需要完全理解题意, 可构造出本题用$f(u,j)$来表示“将以$u$为根节点的子树拆成一棵大小是$j$的子树至少需要切断多少条边... Read more

2020-12-19 Coding

看了很多插头DP的教程，感觉都说的不是很清楚。但我还是搞明白了它是什么。 Read more

2020-12-19 Coding

这题做了半天。美丽的数的定义是“可以被自己的所有非零数位整除的数”。做数位DP，想的就是每个状态需要什么参量来表示。注意到这个定义的限制并不在选取每个数位的时候，而是... Read more

2020-12-16 Coding