巧铺地板

mathe

转自:http://tieba.baidu.com/f?kz=369526531#Scene_1 我觉得这个题目做擂台赛不错，计算复杂度比较适合计算机解决: 长宽为2和1的瓷砖铺长宽为8和5的地板. 要求： ·把地板铺满. ·瓷砖不重叠. ·每个瓷砖可以横铺也可以竖铺 显然，一共需要20块瓷砖，方案数非常多. 问题1：20块瓷砖铺好地板的总方案是多少种？ 问题2：若事先把k块瓷砖铺好，使得剩下的地方就只有唯一一种铺法了,请问k的最小值是多少？ 砖１： 　■■ 砖２： 　■ 　■ 地板： □□□□□□□□ □□□□□□□□ □□□□□□□□ □□□□□□□□ □□□□□□□□

shshsh_0510

这个可能手数更方便 问题1：考虑清某一列的情况，再乘应该就可以了 □ □ □ □ □ 向两边伸出，必伸出奇数个，不算左右上下对称，伸出一个的只有 □□ □ □ □ □ □□ □ □ □ □ 这两种，伸出3个的多一些（也不太多），5个的只有32/2/2=8种 应该不是难题 问题2：沾极值感觉就比较复杂了，需要想一下

无心人

问题一就是问8X5方阵铺2X1的块，总共多少方案 估计数值很大 按块数分类吧

shshsh_0510

数目应该不大，先算有长方的（应该可以推出通项公式），然后再按我上面的方法数互相咬合的。 我数了一下，一列，并且向旁边伸出3个块好像只有12种，其中3个块在同侧的3种 □□ □□ □ □□ □□ □□ □□ □ □□ □ □ □ □ □□ □□ 加上伸出1个块的，一面平齐的情况只有5种，一个个去推，肯定可以求出。 5*n矩阵的应该都可以求，但对于n*m的矩阵，还不知道如何搞

medie2005

计算机求解也不会困难吧.dancing links.

mathe

第一问应该不难，甚至用dancing links也应该可以解决，但是有更好的方法。 第二问感觉上应该能够用计算机解决，但是我没有完全的把握，这个依赖于实际上k有多大

shshsh_0510

dancing links是什么?如何解？ 对n*m的我又想了一下，如果将每个小竖条向上连，小横条向左连，好像等价于2分图的支撑森林，大家想想是不，如果真是就可以用caylay定理什么的了。 第二问，感觉应该先研究什么样的图可被覆盖，如果一个可覆盖的图加上一个圈，则覆盖方案不唯一

mathe

dancing links其实还是遍历，只是遍历过程中对链表的访问使用了些技巧，使得速度可以快一些，但是没有时间复杂度上的改善。

shshsh_0510

不是支撑树，是一些2叉树，感觉把长方形割成一个个杨表类似的东西，需要回家查查书了

mathe

计算了一下，8*5总共才14824种铺地方案，太少了，加大到16*5如何？