2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵 [2020/05/16 22:44] yuki |
2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵 [2020/06/01 19:32] (当前版本) admin ↷ 页面technique:max_matrix被移动并更名为2020-2021:teams:famerwzyyuki:求01矩阵中最大的全为0或1的矩阵 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | **格式**： | ||
| + | - 请注意使用数学公式，如复杂度：$O(MN)$，递推公式：$\text{Up}[i][j] = \text{Up}[i-1][j] + 1$。变量如 $n$，$i$。 | ||
| + | - 公式中不要使用全角括号。 | ||
| + | - 代码现在可以放到 wiki 上啦（并使用 ''<hidden></hidden>'' 隐藏），麻烦搬迁一下。 | ||
| + | - 中文请使用全角逗号“，” | ||
| + | |||
| + | **内容**：讲解比较清晰。可否多找几道例题？ | ||
| + | |||
| ====== 求01矩阵中最大的全为0或1的矩形&正方形 ====== | ====== 求01矩阵中最大的全为0或1的矩形&正方形 ====== | ||
| ===== 悬线法dp ===== | ===== 悬线法dp ===== | ||
| ==== 悬线法的用途 ==== | ==== 悬线法的用途 ==== | ||
| - | 针对求给定矩阵中满足某条件的极大矩阵，比如“面积最大的长方形、正方形”“周长最长的矩形等等”。可以满足在时间复杂度为O（M*N）的要求，比一般的枚举高效的多，也易于理解。 | + | 针对求给定矩阵中满足某条件的极大矩阵，比如“面积最大的长方形、正方形”“周长最长的矩形等等”。可以满足在时间复杂度为 O(MN) 的要求，比一般的枚举高效的多，也易于理解。 |
| ==== 悬线法的思路 ==== | ==== 悬线法的思路 ==== | ||
| 悬线法，悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。也就是说，我们要针对矩阵中每个点进行求极大矩阵的操作，所以我们需要Left[]数组存每个点能到达的最右位置，Right[]数组存放每个点能到达的最左位置，Up[]数组位置。设置好这些数组之后，我们开始遍历矩阵中的每个点ves[i,j]，把每个点和上一个点（ves[i-1][j]）的Left和Right进行比较，分别取最大和最小，Up则是上一个点的Up+1，进而求出面积进行比较。所以我们可以得到相关的递推公式。\\ | 悬线法，悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。也就是说，我们要针对矩阵中每个点进行求极大矩阵的操作，所以我们需要Left[]数组存每个点能到达的最右位置，Right[]数组存放每个点能到达的最左位置，Up[]数组位置。设置好这些数组之后，我们开始遍历矩阵中的每个点ves[i,j]，把每个点和上一个点（ves[i-1][j]）的Left和Right进行比较，分别取最大和最小，Up则是上一个点的Up+1，进而求出面积进行比较。所以我们可以得到相关的递推公式。\\ | ||
| 行 23: | 行 31: | ||
| ===== 笛卡尔树法 ===== | ===== 笛卡尔树法 ===== | ||
| - | 与单调栈法的思路相同，考虑笛卡尔树的每个节点对应的区间就是该节点作为最小值的区间，那么这个节点对应矩形面积为：h[x]*siz[x]。而使用笛卡尔树的优点在于：计算完一行的答案，继续计算下一行时，无需重新建树，只需对于所有节点高度加1，对于新出现的0节点修改其高度为0。时间复杂度更小为O(R*logN)，R为矩阵高度，N为0的个数,可以完成更大的数据范围。\\ | + | 与单调栈法的思路相同，考虑笛卡尔树的每个节点对应的区间就是该节点作为最小值的区间，那么这个节点对应矩形面积为：h[x]*siz[x]。\\ |
| + | |||
| + | **P.S：求01矩阵中只有1的矩阵数量**\\ | ||
| + | 而使用笛卡尔树的优点在于：假设树上第i个节点的子树大小是siz[i]，高度是h[i]，那么这个点对答案的贡献就是siz×(siz+1)/2×(h[i]−h[fa])。计算完一行的答案，继续计算下一行时，无需重新建树，只需对于所有节点高度加1，对于新出现的0节点修改其高度为0。动态维护答案。时间复杂度更小为O(R*logN)，R为矩阵高度，N为0的个数,可以完成更大的数据范围。（该算法需要数据具有随机性）\\ | ||
| 如：[ZJOI2012]小蓝的好友链接：[[https://www.luogu.com.cn/problem/P2611]]\\ | 如：[ZJOI2012]小蓝的好友链接：[[https://www.luogu.com.cn/problem/P2611]]\\ | ||
| 数据范围：$1\le R,C\le 4\times 10^4，1≤R,C≤4×10^4，1\le N\le 10^51≤N≤10^5$\\ | 数据范围：$1\le R,C\le 4\times 10^4，1≤R,C≤4×10^4，1\le N\le 10^51≤N≤10^5$\\ | ||
| - | **代码：** | + | **代码：**[[https://paste.ubuntu.com/p/s8BnsWjHz5/]] （代码还有点问题没有调出来） |
2020-2021/teams/famerwzyyuki/求01矩阵中最大的全为0或1的矩阵.1589640269.txt.gz · 最后更改: 2020/05/16 22:44 由 yuki
