蓝桥杯国赛 矩阵计数 详细注释

题目描述

给出一个 $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++ 代码

相关问题

蓝桥杯国赛压轴题（插头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)。