2017年01月的文章

2017-01-31阅读(3054)评论(0)

POJ 2114 Boatherds  漂流：给定一颗树及各边长度，请快速查询是否有距离为k的顶点对。 4.6划分、解决、合并：分治法  树上的分治法  与POJ1741类似 只需将“不超过k”改为“不超过k减...

2017-01-29阅读(3073)评论(0)

Codeforces 97B Superset  点集：给定n个点，请添加一些点，使任意两点满足①在同一条水平线或竖直线上②或构成一个矩形框住其他点。 4.6划分、解决、合并：分治法  平面上的分治法  从子问...

2017-01-28阅读(3700)评论(1)

GCJ 2009 World Finals B : Min Perimeter  极小三角：从n个点中找出3个，使其形成的三角形周长最小。 4.6划分、解决、合并：分治法  平面上的分治法  不断地用垂直分割线...

2017-01-27阅读(3695)评论(0)

POJ 1854 Evil Straw Warts Live  文字游戏：求通过交换相邻字符使某字符串成为回文的最小步数。 一个回文字符串被定义为等同于自己本身的反转。  给定一个字串，其不一定是个回文，计算最少的swa...

2017-01-26阅读(5150)评论(0)

UVa 10181 15-Puzzle Problem  滑动拼图：给定拼图，求解决方案。 4.5开动脑筋智慧搜索  A*与IDA*  滑块拼图问题是否有解的判断方法是，先将表格平铺： 然后计算N=逆序数对之和...

2017-01-25阅读(2934)评论(0)

POJ 2032 Square Carpets  铺地毯：用最少的正方形覆盖所有点。 4.5开动脑筋智慧搜索  A*与IDA*  大致思路是预处理出一个覆盖所有点的正方形集合，最优解下界为所有点恰好能被最大正方...

2017-01-24阅读(2830)评论(0)

POJ 3523 The Morning after Halloween  万圣节惊魂夜：万圣节过后，鬼屋里的幽灵们到处乱窜！给定它们的位置和地图，按照如下规则移动： ①每个鬼都不重合 ②一回合任意两只鬼不能交换位置 求移动到指定...

2017-01-23阅读(3172)评论(0)

POJ 3134 Power Calculus  幂运算：用最少的乘法和除法计算xn。 4.5开动脑筋智慧搜索  剪枝  算法主框架是DFS，同底数幂的乘除法分别视作指数的加减法。定义exp[i] = n表示某...

2017-01-22阅读(2951)评论(0)

POJ 2046 Gap  滑动拼图：也许你玩过15拼图： 可你玩过28拼图吗？给定4*8的表格 首先把11、21、31、41这四个数字提到第一列空白处： 然后按如下规则移动数字，定义某个空白处的左邻居+1为魔法数字，如果魔法数字...

2017-01-21阅读(5811)评论(0)

POJ 1011 Sticks  棒语十级：请将切成不同长度的棒子拚接起来，做出长度相同的棒子，但是要考虑拚接起来的度必须是最短的。换句话说，就是尽量做出更多长度相同的棒子。 举例来说： 4.5开动脑筋智慧搜索  剪枝&...