冷滟泽的个人博客

2020-03-12 lengyanze 阅读(39) 评论(0)

题意 给定一棵 n 个节点的树，现有有一张完全图，两点 x,y 之间的边长为 w_x+w_y+dis_{x,y}，其中 dis 表示树上两点的距离。 求完全图的 MST。 题解 关于最小生成树，有一个定理： 设 \...

2020-03-09 lengyanze 阅读(89) 评论(0)

有时候用哈希总会感觉心里不稳，怕脸黑撞生日悖论 FST 或者被别人 Hack 之类的，而多模哈希有太慢。今天逛 CF 评论区 看见了一种比较优秀的做法，再此 mark 一下。 ull mix(ull o) { ...

2020-03-09 lengyanze 阅读(43) 评论(0)

比赛地址 A. 代价 注意到除了有 1 的情况，相邻两个数乘起来都是要比三个数乘起来要好的。那么对于一个没有 1 的序列，可以从两端开始删数，最后会剩下来一个多加一次，我们当然是贪心地让这个多加的数最小了。有 1 的...

2020-03-07 lengyanze 阅读(41) 评论(0)

序列（sequence） 不妨把所有的 b_i 变成 b_i-a_i，这样所有 a_i 就变成 0 了。然后考虑建图。把 i 号点的权值设为 a_i 的值，对于每个 t_i=2 的操作，在图中连一条无向边 (u_i,...

2020-03-04 lengyanze 阅读(44) 评论(0)

这题也是一道指令集优化的练手 ao 题（ 因为点数和点权都是 5\cdot 10^4 的，可以使用 256 位指令集存储 short 类型做到常数除以 16。对每个节点预处理一个指令集 w_u 存储 u 的前 16 ...