SYZOJ 156 [FZU] 别踩黑块！

题目描述

　　最近，chenyao迷上了一款叫做“别踩白块”的游戏，但是手残的他每次都撑不过10s，这使他非常自卑，于是决定出一道题来报复所有游戏玩得比他好的人，题目如下：
　　在“别踩白块”游戏中，黑白块交替出现，每一个单位只能是黑块或者白块，chenyao把整张游戏图上黑白块顺序打乱，并重新生成在一张n行，m列的图上。规定在区域(a, b) ~ (c, d)(c>=a & d>=b)内所有的颜色一样的方块组成一个矩形(一个大矩形可能包含多个小矩形)，为了避免点击这些矩形，你需要在规定时间内将所有矩形统计出来(包括相互包含的矩形)

输入格式

每组数据包含多组测试
每组测试第一行两个整数，为n,m
接下来n行，每行m个字符，包含且仅限于'B'与'W'，分别表示黑块与白块

输出格式

一行一个整数为所有的黑色矩形个数

测试样例

样例输入

2 2
WB
BW
3 4
WBBW
WBWB
WBBW

样例输出

2
11

数据范围与提示

样例解释

对于第一组测试，仅有(1,1)~(1,1) 与(2,1)~(2,1)两个矩形 对于第二组测试，
第一行有3个矩形，第二行有2个矩形，第三行有3个矩形
第二列有6个矩形，第三列有2个矩形，第四列有1个矩形
根据容斥原理，共有11个矩形(自己数去..我懒得列出来了..)

数据范围

1 <= m , n <= 1e3

题目改编，数据自造并削弱，侵删-by_XTT。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

数论+单调栈+pair~

终于学会了STL里面pair的用法……相当于是包含有两个变量的struct，同样类型的pair变量可以直接赋值，这里比struct要方便，写的时候也很简单，确实很好用，而且first和second可以用代码补全，不用每次都自己打~

至于这道题，维护一个pair模拟的单调栈，first和second分别记录最大长和最大宽，每次对比，如果该点是W，就直接清空栈（因为不连续了嘛），如果是B，就不断与栈内pair对比，增加tmp的值，相当于前后两个长方形不断合并，最后把合并后的值入栈。

ans用long long（其实我也不知道会不会爆int，反正long long肯定没错就是了~）

#include
#include
#include
using namespace std;
#define ll long longint n,m,tot[1001],num;
char s[1001][1001];
ll ans,cnt;
pair sta[1001];int main()
{while(scanf("%d%d",&n,&m)==2){memset(tot,0,sizeof(tot));ans=0;for(int i=1;i<=n;i++) scanf("%s",s[i]+1);for(int i=1;i<=n;i++){pair tmp;num=cnt=0;for(int j=1;j<=m;j++){if(s[i][j]=='W'){num=cnt=0;tot[j]=0;continue;}tmp.first=++tot[j];tmp.second=1;while(num && sta[num].first>=tmp.first){tmp.second+=sta[num].second;cnt-=sta[num].first*sta[num].second;num--;}sta[++num]=tmp;cnt+=tmp.first*tmp.second;ans+=cnt;} }printf("%lld\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！