容斥 或者 单调栈 hihocoder #1476 : 矩形计数 和 G. Snake Rana 2017 ACM Arabella Collegiate Programming Contest

先说一个简单的题目(题目大意自己看去,反正中文):hihocoder上的:http://hihocoder.com/problemset/problem/1476

然后因为这个n和m的矩阵范围是1000,所以比较简单

然后我们说一下hihocoder上面的做法,首先,这题的做法是http://www.cnblogs.com/heimao5027/p/6738715.html的简化版本,因为颜色只有两种,所以和前面链接给的做法那样,用单调栈维护一下即可。

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ;
int n, m, k;
map<pair<int, int>, int> mp;
int color[maxn][maxn], h[maxn][maxn];
LL dp[maxn][maxn]; struct Point{
int high, col;
}; int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= k; i++){
int a, b; scanf("%d%d", &a, &b);
mp[mk(a, b)] = ;
color[a][b] = ;
}
for (int i = ; i <= n; i++){
for (int j = ; j <= m; j++){
dp[i][j] = ;
h[i][j] = ;
if (color[i][j]) continue;
h[i][j] = ;
if (color[i][j] == color[i - ][j])
h[i][j] += h[i - ][j];
}
}
LL ans = ;
for (int i = ; i <= n; i++){
stack<Point> stc;
for (int j = ; j <= m; j++){
if (color[i][j] == ){
while (!stc.empty()) stc.pop();
continue;
}
int lb = j;
while (!stc.empty()){
if (stc.top().high >= h[i][j]) {
lb = stc.top().col; stc.pop();
}
else break;
}
dp[i][j] += 1LL * h[i][j] * (j - lb + );
//printf("h[%d][%d] = %d lb = %d add = %lld\n", i, j, h[i][j], lb, 1LL*h[i][j] * (j - lb + 1));
stc.push(Point{h[i][j], lb});
if (color[i][lb - ] == ) dp[i][j] += dp[i][lb - ];
ans += dp[i][j];
}
}
cout << ans << endl;
return ;
}

对于GYM上的题目:http://codeforces.com/gym/101350/problem/G

这题的n和m的范围是10000,所以很难用这个方法,因为对于1e8,空间是绝对开不下的

上一篇:OD常用断点


下一篇:docker学习------docker login Harbor失败,需添加http允许权限