传送门（校内）

题目大意

一个有n∗m 个格子的矩阵，每个格子用“.”或“#”表示，“.”表示这个格子可以放东西，“#”则表示这个格子不能放东西。现在有一条 1∗2 大小的木棒，给定q个子矩阵，求对于给定的每个子矩阵，有多少种放木棒的方案。 q≤10⁵, $1\le n,m\le 500$

解析

考场上我能切的题怕都是水题

实际上我一开始的思路是差分，直到我打了半个小时，统计出了每一个（1,1，x，y）矩阵的答案，发现这东西不能差分……

然后冷静下来一想：emm？这前缀和就完了啊？

具体来讲，我们用四个数组$b[i][j]，c[i][j]，sumb[i][j]，sumc[i][j]$’

由于摆放的方式只有横着和竖着，所以：

$b[i][j]$表示第$i$行的前$j$个格子横着放的方案数

$c[i][j]$表示第$j$列的前$i$个格子竖着放的方案数

$sumb[i][j]$表示在矩阵$（1，1，i，j）$中横着放的方案数

$sumc[i][j]$表示在矩阵$（1，1，i，j）$中竖着放的方案数

考虑能不能循环利用一下，发现可以，所以可以节约空间

不过代码里还是开了四个，实际上把sumb改成b，sumc改成c一样可以

然后对于每个询问$（x1，y1，x2，y2）$

$ans=$ $（sumb[x2][y2]+sumc[x2][x2]）$ $-（sumb[x2][y1]+sumc[x2][y1-1]）$ $-（sumb[x1-1][y2]+sumc[x1][y2]）$ $+（sumb[x1-1][y1]+sumc[x1][y1-1]）$

结果最后还是归结到容斥上来了~~

上代码：

#include<bits/stdc++.h> #define rint register int #define ivoid inline void #define iint inline int #define endll '\n' #define ll long long using namespace std; const int N=1e6+5; const int M=505; const int inf=0x3f3f3f3f; int n,m,u,v,w,x,y,z; char a[M][M]; int b[M][M],c[M][M],sum,tot,res,l,r,mx,my,num; iint rad() { int x=0,f=1;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x*f; } int main() { // freopen("matrix.in","r",stdin); // freopen("matrix.out","w",stdout); n=rad();m=rad(); for(rint i=1;i<=n;i++)scanf("%s",a[i]+1); //b 横向 c 竖向 for(rint i=1;i<=n;i++){ for(rint j=1;j<=m;j++){ b[i][j]=b[i][j-1]; c[i][j]=c[i-1][j]; if(a[i][j]=='.'&&a[i][j-1]=='.')b[i][j]++; if(a[i][j]=='.'&&a[i-1][j]=='.')c[i][j]++; } } for(rint i=1;i<=n;i++){ for(rint j=1;j<=m;j++){ b[i][j]=b[i-1][j]+b[i][j]; c[i][j]=c[i][j-1]+c[i][j]; } } int T=rad(),x1,y1,x2,y2; for(rint i=1;i<=T;i++){ x1=rad();y1=rad();x2=rad();y2=rad(); sum=0; sum+=sumb[x2][y2]+sumc[x2][y2]; sum-=sumb[x2][y1]+sumc[x2][y1-1]; sum-=sumb[x1-1][y2]+sumc[x1][y2]; sum+=sumb[x1-1][y1]+sumc[x1][y1-1]; cout<<sum<<endll; } fclose(stdin); fclose(stdout); }

总结

最后能想出正解是因为我想到了理想的正方形 以及他的小伙伴修筑绿化带 这种前缀和の前缀和总感觉很好玩2333~