浅谈树分治算法


一句话讲,把分治做到树上。 树分治首先要把无根树转成有根树(如果是无根树,当然有根树就直接分治),即找一个点$Root$作为根。 <h3>如何找根?</h3> 为了分治的时效,我们需要分治的层数越少越好,于是想让[......]

[点分治]POJ1741 Tree


<h3>题目大意</h3> 给一颗$n$个节点的树,每条边上有一个距离$v$。定义$d(u,v)$为$u$到$v$的最小距离。给定$k$值,求有多少点对$(u,v)$使$u$到$v$的距离小于等于$k$。 <h3>题解</h3>[......]

[并查集]POJ1988 Cube Stacking


<h3>题目大意</h3> 有$N$个方块,$P$个操作。一种操作是$M\ x\ y$表示把含$x$的方块堆移动到含$y$的方块堆顶部,另一种操作$C\ x$询问在含$x$方块的方块堆中,在$x$方块下面的方块数,然[......]

[递推]bzoj1088: [SCOI2005]扫雷Mine


<h3>题目描述</h3>   相信大家都玩过扫雷的游戏。那是在一个$n*m$的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格[......]

[DP]bzoj1079: [SCOI2008]着色方案


<h3>题目描述</h3>   有$n$个木块排成一行,从左到右依次编号为$1$~$n$。你有$k$种颜色的油漆,其中第$i$种颜色的油漆足够涂$c_i$个木块。所有油漆刚好足够涂满所有木块,即$c_1+c_2+..[......]

欢迎来到我的博客!


博客转移到此站,原来的<a href="https://blog.csdn.net/CHAOS_VOID">博客</a>作废,以后不再更新。