蓝桥杯国赛 矩阵计数 详细注释
时间: 2023-09-22 11:05:08 浏览: 52
题目描述
给出一个 $n$ 行 $m$ 列的 $01$ 矩阵,求有多少个 $2$ 行 $2$ 列的全为 $1$ 的子矩阵。
样例输入
```
3 4
1 1 0 1
0 1 1 0
1 0 1 1
```
样例输出
```
4
```
解题思路
这是一道典型的计数问题。可以通过枚举的方式解决。
首先,我们可以枚举全体 $2 \times 2$ 的子矩阵,然后计算子矩阵中元素全为 $1$ 的个数。
接下来,考虑如何计算子矩阵中元素全为 $1$ 的个数。对于一个 $2 \times 2$ 的子矩阵,共有 $4$ 个位置,记为 $(i, j), (i, j+1), (i+1, j), (i+1, j+1)$。我们可以枚举这 $4$ 个位置,判断是否均为 $1$,如果是,则计数器 $+1$。
最后,我们将所有计数器值加起来即为答案。
时间复杂度
枚举 $2 \times 2$ 的子矩阵需要 $\mathcal{O}(nm)$ 的时间。计算子矩阵中元素全为 $1$ 的个数需要 $\mathcal{O}(1)$ 的时间。因此总时间复杂度为 $\mathcal{O}(nm)$。
参考代码
C++ 代码
相关问题
蓝桥杯国赛 矩阵计数(python-状压DP)
矩阵计数是一道经典的组合数学问题,可以用状压DP来解决。以下是一份Python代码的参考实现。
首先,我们需要输入矩阵的行数和列数,以及每行和每列的限制数。然后,我们可以使用二进制数来表示每行和每列的状态,其中1表示该行或该列已经有了一个矩阵,0表示该行或该列还可以放置一个矩阵。
接下来,我们可以使用状压DP来计算矩阵的数量。我们可以定义一个三维数组dp,其中dp[i][j][s]表示在第i行,第j列,状态为s时的矩阵数量。可以通过枚举上一个状态s',来更新dp[i][j][s]。具体来说,如果s'与s在第i行和第j列上的状态都是0,则可以从dp[i][j-1][s']或dp[i-1][j][s']转移而来。如果s'与s在第i行或第j列上的状态不同,则不能转移。最后,dp[m][n][0]就是最终的答案。
下面是完整的代码实现:
```python
n, m, k1, k2 = map(int, input().split())
# 行状态用二进制数表示
row_mask = [0] * n
for i in range(n):
row_mask[i] = int(''.join(input().split()), 2)
# 列状态用二进制数表示
col_mask = [0] * m
for j in range(m):
col_mask[j] = int(''.join(input().split()), 2)
# 初始化dp数组
dp = [[[0 for _ in range(1 << m)] for _ in range(m + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
# 状压DP
for i in range(1, n + 1):
for j in range(m + 1):
for s in range(1 << m):
for sp in range(1 << m):
# 如果s'与s在第i行和第j列上的状态都是0,则可以从dp[i][j-1][s']或dp[i-1][j][s']转移而来
if (sp & s) == 0 and (row_mask[i - 1] & sp) == 0 and (col_mask[j - 1] & sp) == 0:
if j == 0:
dp[i][1][sp] += dp[i - 1][m][s]
else:
dp[i][j + 1][sp] += dp[i][j][s] + dp[i - 1][j][s]
# 如果s'与s在第i行或第j列上的状态不同,则不能转移
else:
continue
# 计算答案
ans = 0
for s in range(1 << m):
if bin(s).count('1') == k2:
ans += dp[n][m][s]
print(ans % 998244353)
```
其中,我们使用了Python内置的bin函数来将一个整数转换为二进制字符串,并使用count方法来计算其中1的个数。
蓝桥杯国赛压轴题(插头dp)
蓝桥杯国赛压轴题是指蓝桥杯国赛中最难的题目,也是插头dp的经典题目。插头dp是动态规划的一种,主要用于解决排列组合问题,如求解最长公共子序列、最长上升子序列等。
在蓝桥杯国赛压轴题中,给定一个n*m的矩阵,矩阵中每个元素都是一个由0和1组成的串。要求选出一些行和一些列,使得选出的行和列的交集中的元素全为1,并且选出的行和列数最小。该问题可以使用插头dp来解决。
插头dp的核心思想是将问题转化为图论问题,将行和列分别看作图中的节点,若行i和列j的交集中的元素全为1,则在节点i和节点j之间连一条边。在此基础上,使用动态规划求解最小的节点覆盖数,即最小的选出的行和列数。
具体地,设f[S]表示覆盖集合S中的节点的最小行列数。则有状态转移方程:
f[S] = min(f[S-T]+|T|),其中T是S的一个子集,且T中的节点必须能够被T中的其它节点覆盖。
最终的答案为f[{1,2,...,n},{1,2,...,m}]。该算法时间复杂度为O(3^n)。