3235: [Ahoi2013]好方的蛇

3235: [Ahoi2013]好方的蛇

链接

分析:

  可以求出以每个点为顶点的满足条件的矩形有多少个,单调栈求。设为sum。

  然后对这个数组进行二维前缀和,可以求出每个矩阵内,以右下角、左下角为端点的矩形有多少个,分别设为f,g。

  然后可以枚举一个点(x,y),计算有多少个矩形的左上角是这个点,然后分别计算x上面的矩形,和y左面的矩形,与它不相交。此时一个每个矩形都和它左上角右上角的矩形计算了两次,减去即可。

  调来调去,最后发现模数多写了个0。。。

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int mod = , N = ;
int a[N][N], f[N][N], g[N][N], u[N];
struct Node{ int x, sum, len; } sk[N];
char s[N]; int main() {
int n = read();
for (int i = ; i <= n; ++i) {
scanf("%s", s + );
for (int j = ; j <= n; ++j) a[i][j] = s[j] == 'B';
}
int top = , sum = , ans = ;
memset(u, , sizeof(u));
for (int k, i = ; i <= n; ++i) {
for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] + : ;
top = sum = ;
for (int j = ; j <= n; ++j) {
k = ;
while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;
sk[++top] = (Node){u[j], u[j] * k, k};
sum += sk[top].sum - a[i][j];
f[i][j] = f[i - ][j] + f[i][j - ] - f[i - ][j - ] + sum; f[i][j] %= mod;
sum += a[i][j];
}
} memset(u, , sizeof(u));
for (int k, i = ; i <= n; ++i) {
for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] + : ;
top = sum = ;
for (int j = n; j; --j) {
k = ;
while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;
sk[++top] = (Node){u[j], u[j] * k, k};
sum += sk[top].sum - a[i][j];
g[i][j] = g[i - ][j] + g[i][j + ] - g[i - ][j + ] + sum; g[i][j] %= mod;
sum += a[i][j];
}
} memset(u, , sizeof(u));
for (int k, i = n; i; --i) {
for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] + : ;
top = sum = ;
for (int j = n; j; --j) {
k = ;
while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;
sk[++top] = (Node){u[j], u[j] * k, k};
sum += sk[top].sum - a[i][j];
ans += sum * f[n][j - ] + sum * f[i - ][n] - sum * f[i - ][j - ]; ans %= mod;
sum += a[i][j];
}
} memset(u, , sizeof(u));
for (int k, i = n; i; --i) {
for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] + : ;
top = sum = ;
for (int j = ; j <= n; ++j) {
k = ;
while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;
sk[++top] = (Node){u[j], u[j] * k, k};
sum += sk[top].sum - a[i][j];
ans = (ans - sum * g[i - ][j + ] % mod + mod) % mod;
sum += a[i][j];
}
}
cout << (ans + mod) % mod;
return ;
}
上一篇:chpasswd命令


下一篇:JS解析JSON 注意事项总结