蓝桥杯19国赛-矩阵计数

简介: 蓝桥杯19国赛-矩阵计数

题目

一个N×M 的方格矩阵,每一个方格中包含一个字符 O 或者字符 X。

要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。

问这样的矩阵一共有多少种?


输入描述


输入一行包含两个整数 N, M (1≤N,M≤5)。


输出描述


输出一个整数代表答案。


输入输出样例

示例

输入

2 3

输出

49

运行限制


  • 最大运行时间:1s
  • 最大运行内存: 256M


思路:


大佬的思路:(1条消息) 蓝桥杯系列 - 2019国赛 - 矩阵计数_notmuch的博客-CSDN博客_矩阵计数蓝桥杯

首先,把方格中的字符 ‘0’ 看成数字 0,字符 ‘X’ 看成数字 11。把每一行看成一个 m 位的二进制数,例如一行字符 “00X0X00X0X” 对应二进制数 “0010100101”。那么一行数字就有 2^m 种情况。

我们设计一个列表stateAllowed,用来存储”合法的”行,所谓合法的行就是指这一行中不存在一行连续的 3 个 X。

定义状态:

dp[i][j][k],表示第i行的合法状态时j,它前一行的合法状态是k时,符合状态的矩阵有多少个。

状态转移方程:

我们考虑当前行和之前两行的状态,如果 j & k & p = 0,说明这 3 行没有一列上是3个 1,即这 3行是一种合法状态。符合当前行的合法状态的矩阵数就等于符合之前一行的所有合法状态(p)的和,如此递推到最后一行。

1. if j&k&p==0:
2.                     dp[i][j][k]+=dp[i-1][k][p]


计算结果:

倒数第三行和前面的多种组合情况已经计算过了,所以我们只需要累加倒数最后两行的所有合法状态即可


1. ans=0
2. for i in stateAllowed:
3.     ans+=sum(dp[N-1][i])

代码:


1. N,M=map(int,input().split())
2. numState=2**M
3. 
4. stateAllowed=[]
5. for i in range(numState):
6.     cnt,flag=0,False
7.     temp=i
8.     while temp:
9. if temp&1:
10.             cnt+=1
11. else:
12.             cnt=0
13. if cnt>=3:
14.             flag=True
15.             break
16.         temp>>=1
17. if not flag:
18.         stateAllowed.append(i)
19. 
20. dp=[[[0 for _ in range(numState)] for _ in range(numState)] for _ in range(N)]
21. for i in stateAllowed:
22.     dp[0][i][0]=1
23. for i in range(N):
24. for j in stateAllowed:
25. for k in stateAllowed:
26. for p in stateAllowed:
27. if j&k&p==0:
28.                     dp[i][j][k]+=dp[i-1][k][p]
29. ans=0
30. for i in stateAllowed:
31.     ans+=sum(dp[N-1][i])
32. 
33. print(ans)
目录
相关文章
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-48 算法训练 关联矩阵
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-48 算法训练 关联矩阵
70 0
|
6月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
68 3
|
6月前
|
存储 算法 测试技术
第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用
第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用
42 1
|
6月前
|
Java
2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
55 4
|
6月前
|
Java
2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
49 3
|
6月前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
54 2
|
6月前
|
Java
2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
40 1
|
6月前
|
存储 索引
6/1 第十五届蓝桥杯国赛pb组 真题本人答案 仅供参考
6/1 第十五届蓝桥杯国赛pb组 真题本人答案 仅供参考
88 4
|
6月前
|
存储 前端开发 算法
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
39 0
|
6月前
2022蓝桥杯大赛软件类国赛真题 卡牌
2022蓝桥杯大赛软件类国赛真题 卡牌
30 0