- 博客(475)
- 收藏
- 关注
RSS订阅原创 WSPD：平面最近邻+t-spanner+近似欧氏距离MST（程设实习）
哎呀打字麻烦死了还是贴PPT吧前言感觉这个东西还是有点厉害的。定义构造可以证明这样构造的WSPD大小为 O(nϵ−dlog△)O(n\epsilon^{-d}\log\triangle)O(nϵ−dlog△)，△\triangle△ 为值域。平面最近邻构造 ϵ=1\epsilon=1ϵ=1 的WASD，只需对于所有 ∣Ai∣=∣Bi∣=1|A_i|=|B_i|=1∣Ai∣=∣Bi∣=1 的里面的两个点的距离向答案贡献一次即可。代码#include<bits/stdc++.h
2023-03-29 12:46:02
607
2
原创 P5327 [ZJOI2019]语言（线段树合并、生成树）
解析只会扫描线树剖的三只log（悲考虑对每个 uuu 考虑合法的 vvv 的集合，必然是一个联通块。进一步的，观察到这个联通块就是由所有经过 uuu 的路径的端点形成的最小生成树。我们有一个最小生成树的经典结论：最小生成树边权和等于按dfs序排列成圆后邻项距离和除以二，不难发现可以线段树维护。把所有路径做一个树上差分，再结合线段树合并，即可进行求解了。用欧拉序 st 表 O(1)O(1)O(1)求LCA，总复杂度 O((n+m)logn)O((n+m)\log n)O((n+m)logn)代
2022-05-27 11:38:56
119
3
原创 SP422 TRANSP2 - Transposing is Even More Fun（Burnside引理，莫比乌斯反演）
巧妙的Burnside应用
2022-05-19 22:52:06
135
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人