P7306 题解
YYJ23
·
·
题解
题意
见 link
分析
最后统计面积时，实现上各种加加减减，绕晕了。
做这题之前，建议先完成 P6404，参考 P6404题解。
以下这种代码实现步骤最清晰。按列或按行分别统计均可，此处按列统计。
-
- 先预处理出每个点往左能延伸的宽度 le[i][j] 。
-
- 按列遍历每个点。
- 2.1. 保证递增的单调栈，否则出栈操作；
- 2.2. 入栈
- 2.3. 统计面积：见例子。
样例
以第 4 列第 6 行作为矩形右下角为例：
1. 栈初始状态：
### 2. 循环遍历栈，统计面积：
#### 2.1 遍历第一步
当前行 $i = 6$ ，遍历行 $pre = 6$ ，宽最大值 $Wmax = 3$ ，比遍历行宽度小的前一行下标为 $next=3$ 。
所以宽 $= [1,Wmax] = [1,3]$ ，高 $= (i-pre, i-next] = (0,3]$ 。
因为当高为 $1$ ，宽的范围为 $[1, Wmax]$ 时，面积和 $= ($ 首项 $1+$ 尾项 $Wmax) \times ($ 项数 $Wmax) \div 2$ ，
所以高 $= (i-pre, i-next] = (0,3]$ 时，即高 $= 1,2,3$ ，当前行增加面积和 $add= (1+3) \times 3 \div 2 \times [(3+1) \times 3 \div 2 - (0+1) \times 0 \div 2] = 36$ 。
#### 2.2 遍历第二步
同理，当前行 $i = 6$ ，遍历行 $pre = 3$ ，宽最大值 $Wmax = 2$ ，比遍历行宽度小的前一行下标 $next = 2$ 。
宽 $=[1,2]$ , 高 $=(i-pre, i-next]=(3,4]$ , 当前行面积和 $add=(1+2) \times 2 \div 2 \times [(4+1) \times 4 \div 2 - (3+1) \times 3 \div 2]=12$ 。
# 代码
```
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, m;
char a[N][N];
int le[N][N];
long long sum = 0;
int cal(int l, int r){
return r*(r+1)/2 - l*(l+1)/2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
//1. 输入并预处理出每个点往左能延伸的宽度le[i][j]
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
le[i][j] = a[i][j] == '.' ? le[i][j-1] + 1 : 0;
}
}
//2. 按列遍历
vector<int> stk;
for(int j = 1; j <= m; j++){
stk.clear();
stk.push_back(0);
for(int i = 1; i <= n; i++){
//2.1 保证递增的单调栈，否则出栈操作
while(stk.size() > 1 && le[stk.back()][j] >= le[i][j]) stk.pop_back();
//2.2 入栈
stk.push_back(i);
//2.3 统计
for(int k = stk.size() - 1; k >= 1; k--){
int pre = stk[k];
long long add = 1ll * le[pre][j] * (le[pre][j] + 1) / 2 * cal(i - pre, i - stk[k - 1]);
sum += add;
}
}
}
cout << sum << endl;
return 0;
}
```