#洛谷 P1120 小木棍

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。

现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

先写一个暴力……

暴力最好写了,然后再考虑剪枝

这是暴力:记录一下当前那根大木棍已经接了多长,已经接了多少根大木棍和一根大木棍应该有多长。

当然暴力也可以加一个简单的剪枝:记录一下总长度,如果当前枚举的一根大木棍的应有长度不能整除总长度那就不搜。

然后剪枝:

1.我们按长度排序,如果当前正在拼一根新的木棍,而且最大的一根小木棍加上当前的长度(应该是0)都不能满足枚举到的当前大木棍长度那就剪掉。

2.还是上述操作,不过是剪掉:整整一根小木棍都比当前枚举到的大木棍的长度长的情况(那样显然无解)

3.还是排序之后,记录一下上次尝试了哪一根小木棍(也就是长度)如果这次枚举到的小木棍的长度和上次相等那么也剪掉。

4.如果搜的目标是拼最后一根大木棍了,而且最后还无解,回溯回来了,那这组直接放弃。

就这些?

对,一共就这么六个剪枝 (排序&暴力的剪枝&1234)

试试刚刚才意识到的高亮操作

#洛谷P1312 Mayan游戏

大模拟+搜索

写了一个下午 这么弱也是没谁了。

题目描述

Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个 7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:

1 、每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图6 到图7 );如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图1 和图2);

2 、任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参见图1 到图3)。

注意:

a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图4 ,三个颜色为1 的方块和三个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块)。

b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除(例如下面图5 所示的情形,5 个方块会同时被消除)。

3 、方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。

上面图1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0, 0 ),将位于(3, 3 )的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态,此时在一竖列上有连续三块颜色为4 的方块,满足消除条件,消除连续3 块颜色为4 的方块后,上方的颜色为3 的方块掉落,形成图 3 所示的局面。

说明

【输入输出样例说明】

按箭头方向的顺序分别为图6 到图11

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是:(2 ,1 )处的方格向右移动,(3,1 )处的方格向右移动,(3 ,0)处的方格向右移动,最后可以将棋盘上所有方块消除。

【数据范围】

对于30% 的数据,初始棋盘上的方块都在棋盘的最下面一行;

对于100%的数据,0 < n≤5 。

注意剪枝:

1.向左面换的话只有左面是空才换(要不然等价于左面那块向右,而且解不比那样优)

2.剩下不足三个剪掉

3.走了n+1步没搞完剪掉

4.同样色块没必要换

注意处理消除:

1.超过三个都能消掉

2.注意共用一块,最好解决方案是复制下来判断

3.注意消完之后要处理下落,还有可能能继续消,开一个flag判断。