xuxuxuxuxu

题解

未归档(20)

/ 注册

全部文章 / 题解（共24篇）

一只log的神仙做法来自专栏

经过同学的指点，发现F题有一只log的做法——点分树。首先两个点在点分树上的lca一定在原树上这两个点的路径上。所以我们把x-y的路径分成x-点分树上的lca 和点分树上的lca-y的两条路径。用树链剖分的方法维护一下点分树上的点到其他点的信息即可。

2019-09-14

2 712

洪水来自专栏

题目：给你一棵树，节点从到编号，每个节点有一个权值，有若干次操作，操作有以下两种：  ：将编号为的点的权值改为 :询问将号节点为根的子树中的所有叶子结点与子树外的其他所有叶子节点分离的最小代价，分离可以通过删除节点实现，删除一个节点的对应代价为该点的权值 ...

动态DP

2019-07-19

0 730

[SDOI2018]旧试题来自专栏

题目：其中表示的约数个数。题解：首先有具体证明我不会，见他人博客设发现了什么，这个式子是不是就是 #2476. 「2018 集训队互测 Day 3」蒜头的奖杯中的然后，我们来推一下这个式子，感觉这个式子还是蛮重要的。首先: 常规莫比乌斯反演, 令这一步我不是很看得懂...

莫比乌斯反演

2019-07-19

0 758

甲苯先生和大中锋的字符串来自专栏

题目：[TJOI2019]甲苯先生和大中锋的字符串大中锋有一个长度为 n 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是...

后缀数组

2019-07-19

1 682