M_sea

洛谷1950 长方形
Luogu分析我们只要处理出以每个点为右下角的矩形个数和即可。然后这个可以用单调栈搞。统计答案的方式有点奇怪。代码...
扫描右侧二维码阅读全文
08
2018/11

洛谷1950 长方形

Luogu

分析

我们只要处理出以每个点为右下角的矩形个数和即可。

然后这个可以用单调栈搞。

统计答案的方式有点奇怪。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
inline char gc() {
    char c=getchar();
    while (c!='.'&&c!='*') c=getchar();
    return c;
}

struct node { int h,pos; } sta[10010];
int top=0;
int h[1010],l[1010],r[1010];

mainint main() {
    int n=read(),m=read(),ans=0;
    for (re int i=1;i<=n;++i) { 
        sta[top=1]=(node){0,0};
        for (re int j=1;j<=m;++j) {
            char c=gc();
            if (c=='.') {
                ++h[j];
                while (sta[top].h>=h[j]) --top;
                l[j]=sta[top].pos; sta[++top]=(node){h[j],j};
                for (re int k=0;k<top;++k)
                    ans+=(sta[k+1].h-sta[k].h)*(j-sta[k].pos);
            }
            else h[j]=0,sta[top=1]=(node){0,j};
        }
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 53 PM

发表评论