2.2k 字 2 分钟

# CF890 E PermuTree 题解 [背包 dp][二进制拆分] # 题目大意 给出一个以111 为根节点大小为NNN 的树。 给这个数确定一个长度为NNN 的排列ppp，分配给各节点作为权值。对于一个点对(u,v)(u,v)(u,v)，若满足au<alca(u,v)<ava_u\lt a_{lca(u,v)} \lt a_vau​<alca(u,v)​<av​，则产生111 个贡献。 求总贡献的最大值。 # 题解 首先对一个排列计算贡献的过程，实际上就是对于每一个点xxx，从它的一个子树中选一个点uuu...
1.9k 字 2 分钟

# 点到线段的距离 # 两种情况 首先要判断点PPP 到直线ABABAB 的投影是否落在线段ABABAB 上。 若落在线段内，即∠A\angle A∠A 和∠B\angle B∠B 为锐角，则距离为点到直线ABABAB 的距离 若落在线段外，即∠A\angle A∠A 或∠B\angle B∠B 为钝角，则距离为点到线段ABABAB 的最近端点的距离 # 如何判断垂足是否落在线段上？ 有两种做法。 第一种根据角度判断，若∠A\angle A∠A、∠B\angle B∠B...