[牛客暑期多校第二场][单调栈+思维]H-Second Large Rectangle

好惨的一场。。。不过也是菜的真实 爆零了 这道题是签到题 我们都没签到。。。真的菜哭了。。。真的是很难受的感觉

求一个0 1矩阵中 第二大的矩形 1代表1*1的矩形 看别人题解看了好久才搞懂 真垃圾。。。

思路：首先需要一个dp数组 求出这个格子以上1的连续个数
之后开始扫描整个数组 从前到后一直扫 每一行对应一个单调栈 栈内元素单调递增
每次读完一个元素 将栈内所有元素算出对应的矩形大小并更新 如果遇到0 清空栈 就这样一个题。。。看起来复杂度有点凶 其实跑起来蛮快的

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int max1, max2, top;
struct fang {
int l, h;//高和最左延长到的格子号
fang(int _l = 0,int _h=0):l(_l),h(_h){}
}arr[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
void update(int x) {//更新mx1 mx2
if (x >= max1) {
max2 = max1;
max1 = x;
}
else if (x > max2) {
max2 = x;
}
}
int main() {
int n, m;
scanf(“%d%d”, &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf(“%1d”, &dp[i][j]);//一次读一个
s[i][j] = dp[i][j];
dp[i][j] += dp[i - 1][j] * dp[i][j];//向上最长连续1的个数
}
}
for (int i = 1; i <= n; i++) {
top = 0;
for (int j = 1; j <= m; j++) {
if (s[i][j] == 0) top = 0;
else {
int tmp = j;//最左能到的格子 默认为当前列
while (arr[top].h > dp[i][j] && top)//如果栈非空且当前元素的高小于栈顶矩形的高 pop
tmp = arr[top–].l;//最左能到的格子号更新
if (arr[top].h != dp[i][j]) {//当前格子的高与栈顶的高不同
arr[++top] = fang(tmp, dp[i][j]);//建立新的矩形并且入栈
}
for (int k = 1; k <= top; k++) {
update(arr[k].h * (j - arr[k].l + 1));//更新最大次大值 将栈中所有矩形的高*（当前列-最左延伸的格子号）
}
}
}
}
printf(“%d\n”, max2);
return 0;
}

uncategorized > 牛客竞赛
[牛客暑期多校第二场][单调栈+思维]H-Second Large Rectangle
https://47.97.0.163/2019/07/22/牛客暑期多校第二场单调栈思维h-second-large-rectangle/
作者
John Doe
发布于
2019年7月22日
许可协议