题目链接：
http://codeforces.com/contest/628/problem/E
题意：
问n*m （1<=n,m<=3000) 的矩阵中有多少个由z组成的Z。
做法：
先求出每个z向左，向右，向做下延伸的最大距离。
然后就是以每个z为右上角，设当前的z的坐标是(X,Y),设len=min(l[X][Y],ld[X][Y]),那么就是要查询从(X,Y)到(X+len-1,Y-len+1)的路径上有多少个坐标(x',y')满足y'+r[x'][y']-1>=Y。
思路其实很简单，暴力找的话总复杂度是O（n^3）。我们可以用树状数组优化查询的部分。
设路径上的z坐标为(x',y')，我们在(x',y'+r[x'][y']-1)这个位置涂上颜色，那么其实会发现满足条件的z对应的涂色的地方都在一个矩阵里。这个矩阵的x坐标属于【X，X+len-1】,矩阵里被涂色的方块个数就是我们要查询的答案。
可以用二维树状数组来求矩阵里的和。不过发现如果从左下角开始一直往右上角依次查询的话，当前点左下部分那些涂色的地方之后就不会用到了，所以建立x坐标的树状数组，把那些没用的点去掉，就可以了。
cf的题目质量真的高。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h>using namespace std;const int N=3005;int n,m;long long ans;int l[N][N],r[N][N],ld[N][N];//左，右，左下延伸的距离int c[N];//x坐标的树状数组char s[N][N];vector<int>vec[N]; //用来去掉已经没用的涂色方块void add(int x,int y){ for (int i=x;i<N;i+=i&-i) c[i]+=y;}int get(int x){ int tmp=0; for (int i=x;i;i-=i&-i) tmp+=c[i]; return tmp;}void cal(int x,int y){ for (int i=0;i<N;i++) c[i]=0,vec[i].clear(); for (;x>=1&&y<=m;x--,y++) { if (s[x][y]=='z') { add(x,1);//(x,y+r[x][y]-1)的位置被涂色 vec[y+r[x][y]-1].push_back(x);// 在涂色的那一列存下x坐标，等待删除 ans+=get(x+min(l[x][y],ld[x][y])-1)-get(x-1);//统计查询的矩阵里的涂色块 } for (int i=0;i<vec[y].size();i++) add(vec[y][i],-1); //去掉y所在那一列没用的涂色块 vec[y].clear(); }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%s",s[i]+1); for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) if (s[i][j]=='z') l[i][j]=l[i][j-1]+1; for (int j=m;j>=1;j--) if (s[i][j]=='z') r[i][j]=r[i][j+1]+1; } for (int i=n;i>=1;i--) for (int j=1;j<=m;j++) if (s[i][j]=='z') ld[i][j]=ld[i+1][j-1]+1; for (int i=1;i<=n;i++) cal(i,1); //从边界开始往右上角统计 for (int j=2;j<=m;j++) cal(n,j); //从边界开始往右上角统计 printf("%I64d\n",ans);} |
