Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:哪位高手帮忙看一下啊,都wa到无语了……

Posted by xuanximei1212 at 2008-11-18 19:12:54 on Problem 3690
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator