牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共4篇）

模拟94 题解

A. 凉宫春日的忧郁数据范围就长得很可写高精度的样子。可以维护高精度的高位，舍弃低位信息。正解是取对数。 $x^y=y*log\ x$ $y!=\sum \limits_{i=1}^{y}log\ i$ 然后可以直接比较两个取对之后的$double$类型。 B....

启发式合并分治虚树 dp 差分

2019-10-30

0 343

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟33 题解

A. 盗梦空间考虑首先构建一棵虚树，然后跑一遍多源点最短路，求出每个虚树上的点到达最近的关键点的距离。分类讨论最终的答案 $u$ 的出现位置。 1.出现在虚树节点的一个满足子树不含虚树节点的儿子子树中。一个很好的性质是我们只关注最大值。所以考虑对每个节点维护一个 multiset ...

容斥莫比乌斯函数二项式反演倍增数学虚树树剖

2020-02-28

0 346

省选模拟74 题解

A. 签到如果权值在边上，那么问题就简单了，弄一棵生成树，然后对每个环权值塞线性基里就完事了。但是如果权值在点上，这个结论就并不成立了。所以可以联想+手玩发现，如果走一条路径然后回来，造成的贡献是两个端点分别状态取反，中间路径不变。然后可以得到一种构造方法，首先从起点走到终点，然后从...

分块点分治 ST表 bitset 线段树虚树线性基

2020-04-18

0 401