[SSLOJ1366 正方矩阵]二分答案+排序、利用RMQ思想达到比较的O(1)

【题目大意】
在一个N*M 的字母矩阵中寻找一个正方子矩阵, 该正方矩阵在原矩阵中重复出现至少K次. 这些正方子矩阵可以出现局部的重叠,但不能是完全的重叠.
输入给定N,M,K和这个矩阵。
输出满足条件的最大的正方子矩阵的边长, 如果没有正方子矩阵能满足条件,输出0.
【算法分析】
显然答案满足单调性。二分答案。
然后怎么判断呢？
我们可以通过预处理边长为2^i的正方形的排名，然后利用这个排名，四分需要的正方形空间。
然后利用n+1进制表示出来，作为他的权值。显然，对于同一个矩阵，权值是一定的。
而对于不同的矩阵，权值是一定不同的。于是达到的O(1)的比较。
所以最终算法复杂度O(N^2 lg^2 N)

然后听说还有另外一种方法是用hash的？
【其他】
跑得比较慢= =。。。
【CODE】
#include #include #include #include #define ra rank[lg[len]]
using namespace std;
const int N=505;
typedef long long lld;
struct PT{int x,y;}a[N*N];
int m,n,appear,len,ns,tx,ty;
char s[N][N];
int lg[N],rank[14][N][N];
lld lltmp,res;

inline void input(){
scanf("%d%d%d",&m,&n,&appear);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
char ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
s[i][j]=ch;
}
}

inline lld count (PT *TMP){
res=0;
int &x=TMP->x,&y=TMP->y;
ns=1< res=ra[x][y]*(n+1);
if (tx<=m) res+=ra[tx][y];
res*=n+1;
if (ty<=n) res+=ra[x][ty];
res*=n+1;
if (tx<=m && ty<=n) res+=ra[tx][ty];
return res;
}

inline int cmp0(const void *x,const void *y){
return s[((PT *)x)->x][((PT *)x)->y]-s[((PT *)y)->x][((PT *)y)->y];
}

inline int cmps(const void *X,const void *Y){
lltmp=count((PT *)X)-count((PT *)Y);
if (lltmp>0) return 1;
if (lltmp<0) return -1;
return 0;
}

inline void init(){
int i,j,tmp,step;
lg[1]=0;
for (i=2;i<=max(n,m);i++){
lg[i]=lg[i-1];
if (1<<(lg[i]+1)==i-1) lg[i]++;
}

for (tmp=0,i=1;i<=m;i++)
for (j=1;j<=n;j++){
a[++tmp].x=i;
a[tmp].y=j;
}
qsort(a+1,m*n,sizeof(PT),cmp0);
for (tmp=0,i=1;i<=m*n;i++){
if (i==1 || s[a[i].x][a[i].y]!=s[a[i-1].x][a[i-1].y]) tmp++;
rank[0][a[i].x][a[i].y]=tmp;
}

for (step=1;step<=lg[max(n,m)];step++){
len=1< for (tmp=0,i=1;i<=m;i++)
for (int j=1;j<=n;j++){
a[++tmp].x=i;
a[tmp].y=j;
}
qsort(a+1,m*n,sizeof(PT),cmps);
for (tmp=0,i=1;i<=m*n;i++){
if (i==1 || count(&a[i-1])!=count(&a[i])) tmp++;
rank[step][a[i].x][a[i].y]=tmp;
}
}
}

inline int cmp(const void *x,const void *y){
lltmp=count((PT *)x)-count((PT *)y);
if (lltmp>0) return 1;
if (lltmp<0) return -1;
return 0;
}

inline bool solve(int NowAns){
int i,j,tmp,nL;
len=NowAns;
for (tmp=0,i=1;i<=m;i++)
for (j=1;j<=n;j++){
a[++tmp].x=i;
a[tmp].y=j;
}
qsort(a+1,m*n,sizeof(PT),cmp);
for (nL=1,i=2;i<=m*n;i++){
if (count(&a[i])!=count(&a[i-1])) nL=1;
else nL++;
if (nL>=appear) return true;
}
return false;
}

int main(){
input();
init();
int l=0,r=min(n,m),mid;
while (l+1 mid=(l+r)/2;
if (solve(mid)) l=mid;
else r=mid-1;
}
if (solve(r)) l=r;
printf("%dn",l);
}