Shape 题解

· · 题解

题意简述

给定一个 n\times m 的 0-1 矩阵，定义一个 H 形为一个长得像 H （感性理解，具体见题目描述）的图形，求有几个由 0 组成的 H 形。

例如下图图示（白色为 0，黑色为 1），一共有 6 个 H 形，这也告诉我们 H 形是可以互相有重叠甚至有包含关系的（但不同的 H 形不会完全恰好重合）。

题目分析

考虑到 n,m\leqslant 2\times 10^3。需要设计一个 n\times m （或带一个 log ）的算法，直接暴力枚举四元组中的任意两个都无法完成，需要找到 H 形中的一个特性。

首先考虑是否可以枚举 H 的竖线（每个 H 有两个竖线，这里考虑左侧）。考场上糊了一个想法：记录每一条竖着的白线，以及每一个点往右可以到达的最近的点，图示情况可以后续推乘法原理加法原理的式子做到 \operatorname{O}{(1)}。随后很快发现了不可行，因为即使我记录了每一个点向右最多可以到达哪些点，整体判断一个 H 的两条竖线是否一一对应还是 \operatorname{O}{(n)} 的。

除此之外，即使两个 H 竖线部分是包含关系，也不一定代表横线部分重合，例如：

这两种情况都无法简单地区分，例如左侧这种，高度为 3 的 H 和高度为 9 的 H 竖线部分共线但是横线部分不共线。右侧这种情况说明不能只记录每一个白格子右侧第一个白格子，因为两个 H 可能只有一个竖线共线。

因此考虑竖线的情况比较难处理，又因为 H 里面只有一条横线，来考虑横线的情况。

对于任何一个 H，显然横线的两端刚好是竖线的中点。因此选择一个横线的两个端点，向上和向下延伸同样的高度（且都是白格子），就一定可以得出一个 H。

基于这种思想我们记录每一个格子向上最多可以延伸多少个格子，向下最多可以延伸多少个格子。

而显然一个横线两端的点向上和向下延伸的白格子应该是相同的，因此对于某一个格子而言，向上延伸和向下延伸的格子数取最小值，才会是以它为横线的一个端点，可能形成的高度最大的 H 的高度的一半。

（也就是 H 的最大高度为 \min{(up,dn)}\times 2+1）。

// a 数组为输入的 0-1 矩阵
for(register int j=1;j<=m;++j){
    for(register int i=1;i<=n;++i){
        if(a[i][j]) up[i][j]=0;
        else up[i][j]=up[i-1][j]+1;
    }// 向上
    for(register int i=n;i>=1;--i){
        if(a[i][j]) dn[i][j]=0;
        else dn[i][j]=dn[i+1][j]+1;
    }// 向下
for(register int i=1;i<=n;++i)
    for(register int j=1;j<=m;++j)
        s[i][j]=min(up[i][j],dn[i][j]);
// 取 min
// 注意 H 的真正高度为 s[i][j]*2-1
// 因为中间那一个白格子在这里也算进去了
}

通过放在最前面的第一张图，我们知道同一个横线上可能出现多个大小不同的 H。假设每个横线上有若干白格子。我们发现……

（注：下图的白格子高度指的是最底下一行的横线的 s ）

第 3 个可以和第 1,4,7,8,11,12,13 个匹配出一个 H，第 4 个可以和第 1,7,8,12,13 个匹配成一个 H……

发现高度小的一定可以和高度大于等于它的匹配。且按照这种方法匹配得出的 H 不重不漏。

因此可以每次取出一段白色的横线（设长度为 k），取出横线上每个点的 s 值，如果我们从小到大排个序，就会发现第 i 个一定可以和第 i+1,i+2,\dots,k 个匹配，一共有 k-i 个 H。

每一段白色的横线取出并逐个计算，累加答案。由于有一个排序，最多有 n 个长度为 m 的横线，因此总的复杂度为 \operatorname{O}{(n\times m\log m)} 的，可过。且只要有黑色的格子这东西就不会卡满。因此效率是非常可观的。

主要处理的部分：

    int i=1;j=1;
    while(i<n){
        while(a[i][j] && j<=m) ++j;

        if(j>m){ // 避免 j 越界
            ++i,j=1;
            continue;
        }

        tot=0;
        while(!a[i][j] && j<=m){ // 不要忘记 j<=m，会越界
            p[++tot]=s[i][j]-1; // 这里要-1（参见上面预处理代码注释）
            ++j;
        }

        std::sort(p+1,p+1+tot); // 小到大排序

        for(register int k=1;k<=tot;++k) ans+=p[k]*(tot-k);
        // 对于每一个 k 一共 tot-k 个 H 可以匹配

        if(j>m){ // 越界判断
            ++i,j=1;
            continue;
        }
    }

告诫后人

考场上本来用的优先队列 priority_queue，惨遭 TLE，个人觉得可能是因为其每次插入和删除都是 \log n，也就是两个 n\log n，因此整体带了一个常数（再加上 STL 可能还有常数）。而 sort 是一个 n\log n，后续处理是 n 的。整体常数小一些。

如果用优先队列 TLE 的话，如果算法没有错误可以改成直接存数组里再排序，说不定就 A 了呢~