• 填矩阵 码蹄集


    题目说明

    有一个 1 × n 的矩阵,现在往里面填方块,一共有三种方块:1 × 1 的白块,1 × 1 的黑块,1 × k 的黑块,方块放置时必须是黑白交替的,矩阵不用填满,但要求最下面的块和最上面的块必须是黑色的,问有多少种放置方法。

    格式

    输入格式: 输入两个整数n,k代表矩阵的高度和黑块的高度

    输出格式:输出一个整数代表放置方法

    样例

    输入:5    3

    输出:6

    数据范围

    2 ≤ k ≤ 10, 1 ≤ n ≤ 100

    代码

    C++

    Python

    知识准备   

    Python map() 函数

    Python map() 函数 (w3school.com.cn)https://www.w3school.com.cn/python/ref_func_map.aspPython中“//”是一个算术运算符,表示整数除法,它可以返回商的整数部分(向下取整)

    Python range() 函数 返回一个左闭右开的区间,如 range(3) 返回,0,1,2

    1. def factorial(n):
    2. if n < 1:
    3. return 1
    4. else:
    5. ans = 1
    6. for i in range(1,n+1):
    7. ans *= i
    8. return ans
    9. def main():
    10. n, k = map(int, input().split(" ")) #设置输入数据的格式
    11. # 把白块和黑块看成一个整体
    12. num1 = (n-1)//(2) #当最底端为黑块时,其余位置最多可存放的黑块数
    13. num2 = (n-1)//(k+1) #当最底端为黑块时,其余位置最多可存的1×k的黑块数
    14. num = 0
    15. sum = 0
    16. for i in range(num1+1):
    17. for j in range(num2+1):
    18. # 当底端为1×1的黑块时
    19. if 1 + i*2 + j*(k+1) <= n: #判断总数不超过可填入的矩形块数
    20. # 排列组合,i和j整体的排列组合方式,除去i和j自身的排列组合
    21. num = factorial(i+j) // (factorial(i) * factorial(j))
    22. sum += num
    23. # 当底端为1×k的黑块时
    24. if k + i*2 + j*(k+1) <= n:
    25. sum += num
    26. print(sum)
    27. if __name__ == '__main__':
    28. main()

    思路说明

    这道题的主要思路在于对于几个规定方块的排列组合,对于1×1的黑块和1×1的白块可以看作是一组,这样在排列时更加方便;

    同时进行分类讨论,规定,当1×1的黑块为底时,(注意题目要求,开头和结尾均为黑块)剩余空缺的可能存在情况,剩余的空缺中可填充的方块有两种,一种是1×1的黑块,一种是1×k的黑块,不论哪种,都把它和它下方的唯一的一块白块看作一个整体;

    具体计算可参考下方代码, (n-1) 是代表除去最底端的一块

    1. num1 = (n-1)//(2) #当最底端为黑块时,其余位置最多可存放的黑块数
    2. num2 = (n-1)//(k+1) #当最底端为黑块时,其余位置最多可存的1×k的黑块数

    那么当1×k的黑块为底时又该如何处理

    1. for i in range(num1+1):
    2. for j in range(num2+1):
    3. # 当底端为1×1的黑块时
    4. if 1 + i*2 + j*(k+1) <= n: #判断总数不超过可填入的矩形块数
    5. # 排列组合,i和j整体的排列组合方式,除去i和j自身的排列组合
    6. num = factorial(i+j) // (factorial(i) * factorial(j))
    7. sum += num
    8. # 当底端为1×k的黑块时
    9. if k + i*2 + j*(k+1) <= n:
    10. sum += num

    当最低端是 1×k 的黑块时,只需要在总数上在加一次该轮的排列组合所得的num数即可。

    此处是分层思想,只管排列,对所有层进行排列,而不关心层内的组合方式,能不能排列,或者怎么排列是由判定条件决定的,需要注意,满足条件后的排列,不考虑最底层,因为它已经固定了。所以可以直接加num,只要它可以满足条件就可以,只要有空间可以塞进去,就可以将该方块看作一层。

  • 相关阅读:
    阿里一面,说说你知道消息中间件的应用场景有哪些?
    4款让人骄傲的国产软件,功能过于强大,却被误认为是外国佬研发
    行业“卷不动”、市场“换不动”,家电赛道又跑回“老路”
    web网页设计期末课程大作业——汉中印象旅游景点介绍网页设计与实现19页面HTML+CSS+JavaScript
    面向产品的新一代端到端唤醒框架 wekws 正式发布
    基于 JMeter API 开发性能测试平台
    CSS-表格独有属性
    Real Time Linux简介
    会员营销中,数字会员模式如何打造差异化会员服务
    如何高效解决 C++内存问题,Apache Doris 实践之路|技术解析
  • 原文地址:https://blog.csdn.net/m0_51787573/article/details/126536334