2021.11.16-测试
前言
哎,不会,就只有T1打了个暴力就不会了,太蒟蒻了
T1\(\color{red}{30}\)
T1就只会暴力,正解是前缀和加后缀和再来一个树状数组维护(压根不知道有后缀和这个东西)
题描
在一个\(n\times m\)的字符矩阵中找到包含\(k\)个'&'字符的十字形状
思路
因为直接枚举会超时,所以考虑另外的做法:
先做一遍前缀和,在做一遍后缀和,那么十字形的字符总数就可以表示为:
B的前缀和减A的前缀和,再加上A的后缀和减去B的后缀和,注意到题目中说两条的贡献都要算,故不需要减去中间多加的部分
for (int i=0;i<=n;++i) for (int j=0;j<=m;++j)
a[i][j]=f[i][j]-g[i+1][j+1];//得到该点(f:前缀和 g:后缀和)
这样做就只需要找到A和B两个点,那么我们枚举其中一个点,在加一个树状数组寻找另一个点即可
代码:
#include<bits/stdc++.h>
#define N 100005
#define M 105
#define K 100005
using namespace std;
int g[N][M],f[N][M],a[N][M],n,m,k,cnt;
long long ans;
//========================================
struct BTF{//树状数组
int v[M];
void modify(int x){
if(!x)++v[0];
for(;x<M&&x;x+=x&-x)++v[x];
}
int query(int x){
int res=0;
for(;x;x-=x&-x)res+=v[x];
return res+v[0];
}
}s[K*3];
//============================================
int main(){
scanf("%d%d%d\n",&n,&m,&k);
for(int i=1;i<=n;i++,scanf("\n"))
for(int j=1;j<=m;j++)
if(getchar()=='$')
f[i][j]++,g[i][j]++,cnt++;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];//前缀和
for(int i=n;i;i--)for(int j=m;j;j--)
g[i][j]+=g[i+1][j]+g[i][j+1]-g[i+1][j+1];//后缀和
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)
a[i][j]=f[i][j]-g[i+1][j+1];
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++)
s[a[i-1][j]+2*cnt].modify(j);
for(int j=1;j<=m;j++)
ans+=s[a[i][j]-k+2*cnt].query(j-1);
}
cout<<ans<<'\n';
return 0;
}