xuxuxuxuxu

题解

未归档(20)

/ 注册

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

[51Nod1681]公共祖先来自专栏

题意：给出个点的树，对于所有点对求它们在两棵树中公共的公共祖先数量之和。题解：不考虑求点对的贡献，考虑求祖先的贡献。枚举一个祖先，假设两棵树上点的公共子孙个数为，那么这个点的贡献就是难点就在如何求两棵树上点的公共子孙个数。解法一：求出两棵树的，发现就是求满足和的的个数。这里就是的，就...

莫队线段树合并树套树分块

2020-07-27

0 702

题解 P3242 【[HNOI2015]接水果】来自专栏

题解 P3242 【[HNOI2015]接水果】题意：给你一棵个点的树和条路径，每条路径都有一个权值。有k组询问，每次询问给你一条路径和一个值。问你被这条路径包含的所有路径中的第K小的路径的值题解：我用的是树上莫队+平衡树(或分块)的方法平衡树的话是,分块的话就是稍微口胡一下树上莫队...

莫队分块

2020-01-17

0 689

题解 P5471 【[NOI2019]弹跳】来自专栏

题解 P5471 【[NOI2019]弹跳】做法：思维+动态开点线段树+分块首先我们考虑最短路做法，发现边数是级别的。一维的情况我们能用线段树优化建边，但二维呢？反正我不会。我们想到Dijkstra的思想，每次找到dis最小的点，并用这个点去更新其他点。我们把矩形看成点，相当于每次找出dis...

线段树分块

2020-01-17

0 791