作者存档：edward_mj

【题目大意】
在一个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);
}

【算法分析】
实际上是解这样一个方程：
A+C*x=B  (mod 2^k)
C*x=B-A   (mod 2^k)
C*x+(2^k)*y=B-A
注意如果B-A<0的话，要+2^k使之变回>=0。
现在引入小写的a,b,c，并令a=C,b=2^k,c=B-A。
然后求方程ax+bx=c的最小整数解。
于是用拓展欧几里得算法获得ax+bx=gcd(a,b)的解，然后弄到x的最小非负整数解出来即可。
【其他】
第一次深切了解了这个算法。
【CODE】
#include using namespace std;
typedef __int64 lld;
lld A,B,C,k,x,y,P,gcd;

lld exgcd(lld a,lld b){
if (!b){
x=1; y=0;
return a;
}
lld res=exgcd(b,a%b),tx=x,ty=y;
x=ty; y=tx-a/b*ty;
return res;
}

lld solve(lld a,lld b,lld c){
if (!c) return 0;
if (!a) return -1;
lld gcd=exgcd(a,b);
if (c%gcd) return -1;
a/=gcd; b/=gcd; c/=gcd;
x*=c; y*=c;
x=(x%b+b)%b;
return x;
}

int main(){
lld a,b,c;
while (cin >> A >> B >> C >> k){
if (!A && !B && !C && !k) break;
P=1;
for (int i=1;i<=k;i++) P*=2;
a=C; b=P; c=(((B-A)%P)+P)%P;
x=0; y=0;
lld ans=solve(a,b,c);
if (ans==-1) cout << "FOREVER" << endl;
else cout << ans << endl;
}
}

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1316
【解题经历】
其实我做这题是有一段曲折的经历的。。。
第一次见面是由于师傅在ACM_DIY群里说在衡阳八中的OJ上见到了ACRush。。。于是果断跑过去围观。
一看~晕，用PASCAL的ACRush。。。假。。。
然后围观他做的那题——就是本题了。。。
于是我苦思冥想~最终没有任何想法，果断GG。。。
然后后来由于我想做男人…于是围观了漆大神的论文,YY了一下,把树上基于点的分治领悟了一下.
然后就把男人八题里相关的那题AC了.今日突然想起这题.再次来围观,额,终于有想法了.
然后一开始WA到SB。
写了个朴素来随机对拍。没错啊~= =
然后猛然发现如果他给出的长度是0，是必须Yes的。而我的是No。
改完一交，TLE。。。万念俱灭啊。。。
然后回去做了一节晚修的作业，突然有灵感，上来一改，果然AC。还排第二，不错呢。
【算法分析】
先将树根据点的数量分割，分成很多份（有点像线段树），然后再从小份的到大份的弄回来处理。
分割复杂度：O(N lg N)
处理的话就直接枚举给出的LEN。一个一个分开判断，然后在判的时候排一下序，
排这个序的总复杂度变成O(N lg^2 N)。
利用单调性可以做到O(Qt) per 分割树节点的复杂度。其中Qt表示该分割树区间的点的数量。

然后我们来围观一下TLE的原因：
我把枚举给出的询问放在solve的外面，于是复杂度变成O(QN lg^2 N) 其中Q为询问个数。
于是，
我们把枚举给出的询问放在solve的排序后面，复杂度就变成O(N lg^2 N+QN lg N)。
于是终于AC!
【其他】
好弱啊。。。YM GP大神。
大家也可以去围观提交记录，确实是ACRush在提交。。。表示没有撒谎~
另外程序中的big是因为有一段时间WA到不行，全部改成long long了。
后来改回来就继续用big了~
【CODE】
#include #include #include #include #include using namespace std;
typedef int big;
const big N=10005;
const big INF=0x7FFFFFFF;
struct edge{big x,y;big c;edge *next;}g[2*N],*ls[N];
struct PobigType{big dep,l,r,root;}tr[N*20];
big n,Qn,e,PN,Qt,CT;
big pl[20][N],color[20][N],size[N],tot[20],Q[N];
big dis[N],Que[N];
bool result[N];

void add(big x,big y,big c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e];
}

void input(){
e=0;
for (big i=1;i<=n;i++) ls[i]=NULL;
scanf("%d%d",&n,&Qn);
big x,y,c;
for (big i=1;i scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,c);
}
memset(tot,0,sizeof(tot));
PN=1; CT=1;
for (big i=1;i<=n;i++) pl[1][i]=i;
}

void makelabel(big p,big fa,big &times,big *co){
size[p]=times++;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[t->y]==co[p]){
dis[t->y]=dis[p]+t->c;
makelabel(t->y,p,times,co);
}
size[p]=times-size[p];
}

void choose_root(big p,big fa,big *co,big &root,big &cost,big &total){
big NowCost=total-size[p];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[t->y]==co[p]) NowCost=max(NowCost,size[t->y]);
if (NowCost cost=NowCost;
root=p;
}
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[t->y]==co[p])
choose_root(t->y,p,co,root,cost,total);
}

void AddPoint(big p,big fa,big *PL,big &TOT,big *co){
PL[++TOT]=p;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[p]==co[t->y])
AddPoint(t->y,p,PL,TOT,co);
}

void Div(big pos,big l,big r,big dep){
PobigType *p=&tr[pos];
big times=0,cost=INF,i,*co=color[dep];
p->l=l; p->r=r; p->dep=dep;
for (i=l;i<=r;i++) co[pl[dep][i]]=CT;
if (l>=r){
PN–;
return;
}
dis[l]]=0;
makelabel(pl[dep][l],0,times,co);
choose_root(pl[dep][l],0,co,p->root,cost,size[l]]);
for (edge *t=ls[p->root];t;t=t->next)
if (co[t->y]==co[p->root]){
big L=tot[dep+1]+1;
AddPoint(t->y,p->root,pl[dep+1],tot[dep+1],co);
big R=tot[dep+1];
PN++; CT++;
Div(PN,L,R,dep+1);
}
}

inline bool Qcmp(int x,int y){
return dis[x]}

void solve(){
for (big pos=PN;pos>=1;pos–){
PobigType *p=&tr[pos];
big times=0;
dis[p->root]=0;
makelabel(p->root,0,times,color[p->dep]);
Qt=0;
for (big i=p->l;i<=p->r;i++)
Q[++Qt]=pl[p->dep][i];
sort(Q+1,Q+Qt+1,Qcmp);
for (big k=1;k<=Qn;k++) if (!result[k]){
big ans=Que[k],j=0;
for (big i=1;i<=Qt;i++){
if (dis[Q[i]]>ans) break;
while (j+1 while (j && dis[Q[j]]+dis[Q[i]]>ans) j–;
while (j && color[p->dep+1][Q[j]]==color[p->dep+1][Q[i]]) j–;
if (j && dis[Q[j]]+dis[Q[i]]==ans){
result[k]=true;
break;
}
}
}
}
}

int main(){
input();
Div(1,1,n,1);
for (big i=1;i<=Qn;i++){
scanf("%d",&Que[i]);
if (!Que[i]) result[i]=true;
}
solve();
for (big i=1;i<=Qn;i++)
if (result[i]) printf("Yesn");
else printf("Non");
return 0;
}