Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:哪位高手帮忙看一下啊,都wa到无语了……In Reply To:哪位高手帮忙看一下啊,都wa到无语了…… Posted by:sun3673181 at 2008-10-08 12:57:07 > #include<cstdio> > #include<iostream> > using namespace std; > > //把每行计算成一整数,用kmp算法让每个星座进行行比较 > > char data[1000][1001],cons[100][50][51]; > long long num,data2[1000],cons2[100][50]; > int N,M,T,P,Q; > int kmp[100][50]; > bool used[100]; > > int compute(){ > int ccount=0,i,j,k,l; > for(l=0;l<T;l++){ > for(k=j=0;k<N&&j<P;k++) > if(data2[k]==cons2[l][j]) > j++; > else if(j) > j=kmp[l][j-1]+1,k--; > if(j==P) used[l]=true; > } > > for(i=0;i<M-Q;i++){ > for(j=0;j<N;j++) > { > data2[j]<<=1; > data2[j]&=num; > if(data[j][i+Q]=='*') > data2[j]++; > } > > for(l=0;l<T;l++){ > if(used[l]) > continue; > for(k=j=0;k<N&&j<P;k++) > if(data2[k]==cons2[l][j]) > j++; > else if(j) > j=kmp[l][j-1]+1,k--; > if(j==P) used[l]=true; > } > } > for(i=0;i<T;i++) > if(used[i]) ccount++; > return ccount; > } > > int main(){ > int ccount=1; > while(scanf("%d%d%d%d%d",&N,&M,&T,&P,&Q)&&(N|M|T|P|Q)){ > int i,j,k; > for(i=0;i<N;i++) > for(scanf("%s",&data[i]),data2[i]=0,j=0;j<Q;j++) > { > data2[i]<<=1; > if(data[i][j]=='*') > data2[i]++; > } > for(i=0;i<T;i++){ > for(j=0;j<P;j++) > for(scanf("%s",&cons[i][j]),cons2[i][j]=0,k=0;k<Q;k++) > { > cons2[i][j]<<=1; > if(cons[i][j][k]=='*') > cons2[i][j]++; > } > for(kmp[i][0]=-1,j=1;j<P;kmp[i][j++]=0); > for(j=1;j<P;j++){ > for(k=kmp[i][j-1];k>=0&&!(cons2[i][k+1]==cons2[i][j]);k=kmp[i][k]); > kmp[i][j]=(cons2[i][k+1]==cons2[i][j]?k+1:-1); > } > } > if(P>N||Q>M){ > printf("Case %d: %d\n",ccount++,0); > continue; > } > (num=(1<<Q))--; > memset(used,0,sizeof(used)); > printf("Case %d: %d\n",ccount++,compute()); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator