刚开始做这题的时候思路错了, 把他想成字符串模式匹配题了。通过构建长度在[A,B]之间的字符串,然后再对主字符串进行模式匹配,想想要用kmp算法,对于这个我还不是很懂.... 打算好好学习一下kmp,后来估计了一下时间,发现必须超时。
转而一想:
其实需要的只是在主字符串中的一些子集,通过直接遍历主字符串长度为len(A<=len<=B),把这个数读出来,相应的+1就好。通过这种思路,写完代码。后发现,对于len=2,选项='00'和len=1,选项='0',都会被归为一类,明显这样不符合题意。
怎么解决呢?
可以通过添加前导'1',区别开来。再在输出的时候忽略前导'1'。
另外用到了排序,将出现频率分别开来。
输出的code写得不是很好;
/* ID:sevenst4 LANG:C++ PROG:contact */ #include<stdio.h> #include<algorithm> using 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++; if( outnum!=1 ) printf( " " );//不是第一个有前导空格 print( i ); if( outnum==6 )//第六个有回车 { outnum=0; printf( "\n" ); } index++; } if( outnum!=0 ) printf( "\n" ); } return 0; }