
SPOJ QTREE5 Query on a tree V 题解《挑战程序设计竞赛》
SPOJ QTREE5 Query on a tree V 染色:给定一颗黑白树,请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。 4.6划分、解决、合并:分治法 树上的分治法 重心分解后...
SPOJ QTREE5 Query on a tree V 染色:给定一颗黑白树,请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。 4.6划分、解决、合并:分治法 树上的分治法 重心分解后...
UVa 12161 Ironman Race in Treeland 赛车:给定一颗树及各边长度及花费,请计算花费在m以内的最长路径。 4.6划分、解决、合并:分治法 树上的分治法 不断根据重心分割子树,...
POJ 2114 Boatherds 漂流:给定一颗树及各边长度,请快速查询是否有距离为k的顶点对。 4.6划分、解决、合并:分治法 树上的分治法 与POJ1741类似 只需将“不超过k”改为“不超过k减...
Codeforces 97B Superset 点集:给定n个点,请添加一些点,使任意两点满足①在同一条水平线或竖直线上②或构成一个矩形框住其他点。 4.6划分、解决、合并:分治法 平面上的分治法 从子问...
GCJ 2009 World Finals B : Min Perimeter 极小三角:从n个点中找出3个,使其形成的三角形周长最小。 4.6划分、解决、合并:分治法 平面上的分治法 不断地用垂直分割线...
POJ 1854 Evil Straw Warts Live 文字游戏:求通过交换相邻字符使某字符串成为回文的最小步数。 一个回文字符串被定义为等同于自己本身的反转。 给定一个字串,其不一定是个回文,计算最少的swa...
UVa 10181 15-Puzzle Problem 滑动拼图:给定拼图,求解决方案。 4.5开动脑筋智慧搜索 A*与IDA* 滑块拼图问题是否有解的判断方法是,先将表格平铺: 然后计算N=逆序数对之和...
POJ 2032 Square Carpets 铺地毯:用最少的正方形覆盖所有点。 4.5开动脑筋智慧搜索 A*与IDA* 大致思路是预处理出一个覆盖所有点的正方形集合,最优解下界为所有点恰好能被最大正方...
POJ 3523 The Morning after Halloween 万圣节惊魂夜:万圣节过后,鬼屋里的幽灵们到处乱窜!给定它们的位置和地图,按照如下规则移动: ①每个鬼都不重合 ②一回合任意两只鬼不能交换位置 求移动到指定...
POJ 3134 Power Calculus 幂运算:用最少的乘法和除法计算xn。 4.5开动脑筋智慧搜索 剪枝 算法主框架是DFS,同底数幂的乘除法分别视作指数的加减法。定义exp[i] = n表示某...