题意

输入一个\(n\times m\)的矩阵，每个格子可能是空地，也可能是沼泽。对于每个空地格子，求出以它为右下角的空矩形的最大周长，然后统计每个周长出现了多少次。

思路

对于 每一行 每两个沼泽之间的连续部分 维护一个单调栈，维护对于当前位置（右下角位置）可取的前面的一系列的左上角位置。

因为向右移动时新加进来一个较低的会将之前高的削低，即会修改之前栈中可行的点的高度，所以本题中仅维护位置是不够的，需要维护位置\(c\)和高度\(h\)两个属性。

注意到，\(c\)显然是单调增的，单调栈维护的单调的属性是\(c-h\)单调增（即周长单调增），故\(h\)也是单调增的。

向右移动时，考虑新加进来的一个造成的影响，将前面一整段高度\(\geq h\)的削成\(h\)，这就导致只有最前面的一个可能有用，至于究竟有没有用呢，和它前面一个比一比就行，毕竟要维护的是单调增的属性。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 1010

char str[maxn];

int h[maxn], cnt[maxn<<2];

using namespace std;

typedef long long LL;

struct node { int h, c; }s[maxn];

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

        int n, m;

        scanf("%d%d", &n, &m);

        memset(h, 0, sizeof h);

        memset(cnt, 0, sizeof cnt);

        F2(i, 1, n) {

            scanf("%s", str+1);

            int top = 0;

            F2(j, 1, m) {

                if (str[j]=='#') { h[j] = top = 0; continue; }

                ++h[j];

                node temp;

                if (!top || s[top-1].h < h[j]) temp = {h[j], j};

                else {

                    while (top && s[top-1].h>=h[j]) --top;

                    temp = {h[j], s[top].c};

                }

                if (!top || temp.h-temp.c > s[top-1].h-s[top-1].c) s[top++] = temp;

                int area = (s[top-1].h+j-s[top-1].c+1) << 1;

                ++cnt[area];

            }

        }

        F2(i, 1, (m+n)<<1) if (cnt[i]) printf("%d x %d\n", cnt[i], i);

    }

    return 0;

}

巴特西

UVa 12265 贩卖土地单调栈

题意

思路

Code

最新文章

热门文章

巴特西

UVa 12265 贩卖土地 单调栈

题意

思路

Code

最新文章

热门文章

UVa 12265 贩卖土地单调栈