网站被抄袭怎么办/网上兼职外宣推广怎么做

题目描述

Orez很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez又得到了一些数据，并已经把它们排成了一个n行m列的矩阵。通过观察，Orez发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这个数。
输入输出格式
输入格式：

文件的第一行为两个整数n和m。接下来n行每行包含m个正整数，表示Orez得到的矩阵。

输出格式：

文件中仅包含一个整数answer，表示矩阵中有answer个上下左右对称的正方形子矩阵。

分析：
1.按照一般思路，先预处理出left[][],right[][],up[][],down[][]，表示在四个方向上最多可以延伸的长度，易知f[i][j] = min{left[i][j], right[i][j], up[i][j], down[i][j]}；
2.但在这里，我们还要记录两个辅助数组，设lx[i][j]为以i，j为中心的，水平方向上的最长回文串长度的一半，ly[][]定义类似，并且我们设f[i][j] 为以(i,j)为中心的正方形的个数；
3.left[i][j]=max{k|min{ly[i][j-k…j]}>=j-k};
4.i 一定时，j - left[i][j]随j增加不减，right[][]，up[][]，down[][]性质类似；
5.最后统计答案的时候，行号和列号同偶时，贡献为(f[i][j]>>1)+1,同奇时贡献为(f[i][j]+1)>>1。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=2510;
int A[maxn][maxn];
int lx[maxn][maxn],ly[maxn][maxn];
int n,m;
int v[maxn];
int Log[maxn];
void Manacher(int *len,int tot){int k=0;for(int i=1;i<=tot;i++){int p=k+len[k];if(i<p && len[2*k-i]<p-i) len[i]=len[2*k-i];else{if(i<p) len[i]=p-i;while(i+len[i]<tot && i-len[i]>1 && v[i-len[i]-1]==v[i+len[i]+1]) len[i]++;k=i;}}
}
int Min[maxn][12];
void RMQ(int t[maxn][maxn],int k,int tot){memset(Min,0x3f3f3f3f,sizeof(Min));for(int i=1;i<=tot;i++) Min[i][0]=t[i][k];for(int j=1;j<=11;j++){for(int i=1;i<=tot-(1<<j)+1;i++){Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);}}
}
int query(int x,int y){int p=Log[y-x+1];return min(Min[x][p],Min[y-(1<<p)+1][p]);
}
int f[maxn][maxn];
int main(){for(int i=2;i<maxn;i++) Log[i]=Log[i>>1]+1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&A[i*2-1][j*2-1]);n=n*2-1;m=m*2-1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) v[j]=A[i][j];Manacher(lx[i],m);}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++) v[j]=A[j][i];Manacher(ly[i],n);}int v;memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++){RMQ(ly,i,m);v=1;for(int j=1;j<=m;j++){while(v<j && query(v,j)<j-v) v++;f[i][j]=min(f[i][j],j-v);}v=m;for(int j=m;j>=1;j--){while(v>j && query(j,v)<v-j) v--;f[i][j]=min(f[i][j],v-j);}}for(int i=1;i<=m;i++){RMQ(lx,i,n);v=1;for(int j=1;j<=n;j++){while(v<j && query(v,j)<j-v) v++;f[j][i]=min(f[j][i],j-v);}v=n;for(int j=n;j>=1;j--){while(v>j && query(j,v)<v-j) v--;f[j][i]=min(f[j][i],v-j);}}int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if((i&1) && (j&1)) ans+=(f[i][j]>>1)+1;else if(!(i&1) && !(j&1)) ans+=(f[i][j]+1)>>1;}printf("%d",ans);return 0;
}

^_^