[U]3.1.5 Contact 小技巧题

刚开始做这题的时候思路错了， 把他想成字符串模式匹配题了。通过构建长度在[A,B]之间的字符串，然后再对主字符串进行模式匹配，想想要用kmp算法，对于这个我还不是很懂…. 打算好好学习一下kmp,后来估计了一下时间，发现必须超时。 转而一想： 其实需要的

刚开始做这题的时候思路错了， 把他想成字符串模式匹配题了。通过构建长度在[A,B]之间的字符串，然后再对主字符串进行模式匹配，想想要用kmp算法，对于这个我还不是很懂…. 打算好好学习一下kmp,后来估计了一下时间，发现必须超时。

转而一想：

其实需要的只是在主字符串中的一些子集，通过直接遍历主字符串长度为len(A<=len<=B),把这个数读出来，相应的+1就好。通过这种思路，写完代码。后发现，对于len=2,选项='00'和len=1,选项='0',都会被归为一类，明显这样不符合题意。

怎么解决呢？

可以通过添加前导’1’，区别开来。再在输出的时候忽略前导’1’。

另外用到了排序，将出现频率分别开来。

输出的code写得不是很好;

/*ID:sevenst4LANG:C++PROG:contact*/#include#includeusing namespace std;int cnt[10000];int cp[10000];char line[222222];bool cmp( int a,int b ){ return a>b; };void print( int num ){ 	 int l=0; 	 int k[15]={0}; 	 while( num ) 	 {	  		k[l++]=num&1;			num=num>>1;	 	 } 	 for( int i=l-2;i>=0;i-- ) 	 	  printf( "%d",k[i] );}int getnum( int s,int e ){ 	int ret=0; 	for( int i=s;i<e;i++ ) 		 if( line[i]=='1' ) 		 	 ret=ret<<1|1; 		 else 		 	 ret=ret<<1;	return ret;}int main(){ 	freopen( "contact.in","r",stdin ); 	freopen( "contact.out","w",stdout ); 	int A,B,N; 	 	for( int i=0;i<(1<<13);i++ ) cnt[i]=0; 		  	scanf( "%d %d %d",&A,&B,&N ); 	 	char data[80]; 	int len=0; 	while( scanf( "%s",&data )!=EOF ) 	{	 	   for( int i=0;data[i]!='\0';i++ )	 	   		line[len++]=data[i];    }     	for( int i=A;i<=B;i++ ) 	{	 	 for( int j=0;j+i<=len;j++ )	 	 	  cnt[(1<<i)+getnum(j,j+i)]++;	}		for( int i=0;i<(1<<(B+1));i++ )		 cp[i]=cnt[i];		 	sort( cp,cp+(1<<(B+1)),cmp );		int index=0;	while( N-- )	{	 	   int top=cp[index];	 	   if( top==0 )	 	   	   break;  	       int outnum=0;	 	   printf( "%d\n",top );	 	   bool flag=false;	 	   for( int i=0;i<(1<<(B+1));i++ )	 	   		if( cnt[i]==top )	 	   		{	 	   			outnum++;	 	   	<div style="color:transparent">本文来源gaodai^.ma#com搞#代!码网</div>		if( outnum!=1 )	 	   				printf( " " );//不是第一个有前导空格 	 	   			print( i ); 	   				if( outnum==6 )//第六个有回车					{					 	outnum=0; 	 	   				printf( "\n" );					}	 	   			index++;				}		   if( outnum!=0 )		   	   printf( "\n" );    } 	return 0;}

喜欢 (0)赏

[搞代码]

分享 (0)