[分块]bzoj5168: [HAOI2014]贴海报

题目描述

Bytetown城市要进行市长竞选,所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理,城市委员会为选民准备了一个张贴海报的electoral墙。张贴规则如下:
1.elect[……]

浅谈树分治算法

一句话讲,把分治做到树上。

树分治首先要把无根树转成有根树(如果是无根树,当然有根树就直接分治),即找一个点Root作为根。

如何找根?

为了分治的时效,我们需要分治的层数越少越好,于是想让找到的根下最大子树[……]

[点分治]POJ1741 Tree

题目大意

给一颗n个节点的树,每条边上有一个距离v。定义d(u,v)uv的最小距离。给定k值,求有多少点对(u,v)使uv的距离小于等于k

题解

如果用暴力枚举,那么时间复杂度为O(N^3)
用DFS,时间复杂度为O(N^2)
暴力不可取。
那么我们重[……]

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

题目描述

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

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

题目描述

  有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂c_i个木块。所有油漆刚好足够涂满所有木块,即c_1+c_2+...+c_k=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相邻木块[……]