USACO Training Section 3.1 Contact

英文原题  中文题译

大意：在长01串中找长度在A,B之间的子串的重复次数，按顺序输出最大的N个重复次数，且输出相应的子串，要求相同的子串按二进制大小排列输出（每行6个）。

数据限制：1 <= A <= B <= 12，1 <= N < 50，字符串最大长度200，000

例子：
2 4 2
01010010010001000111101100001010011001111000010010011110010000000
输出：
23
00
15
01 10
表示，00出现23次最多，其次01,10各出现15次。

很显然用tries来做是最合适的，长度最大为12，tries的每个节点含2个子节点，构成一个完全树，节点数为2^13-1个。

思路很顺，写的也很顺，不过还是提交了好多次，在格式上犯了N次错，sigh。之后看了看标程的代码，它不是用tries做的，而是用位操作，恩，充分的利用了01的特点，也很快，编程上比tries还简单，特别是在计数的时候不需要遍历，输出时也更简单。的确比用tries高明。再次体现了：什么是最合适的。受教了。

/*
ID: blackco3
TASK: contact
LANG: C++
*/
#include <iostream>
#include <memory.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define _max_pattern_ 13
#define _max_seq_len_ 200001

char sequence[_max_seq_len_] ;
int seq_size, low, up, n_th ;

struct t_tries {
	int count ;
	t_tries *next[2] ;
} tries_buf[(1<<_max_pattern_)+1] ;
void build_tries( int height ){
	for( int pos=1; pos<(1<<(height+1)); pos++ ){
		tries_buf[pos].count=0;
		if( (pos<<1)>=(1<<(height+1)) )
			tries_buf[pos].next[0] = tries_buf[pos].next[1] = 0 ;
		else 
			tries_buf[pos].next[0] = tries_buf+(pos<<1), tries_buf[pos].next[1] = tries_buf+(pos<<1)+1 ; 
	}
}

struct t_pattern {
	int times, len ;
	char str[_max_pattern_+1];
} patterns[(1<<_max_pattern_)+1], *p_patterns[(1<<_max_pattern_)+1];
typedef t_pattern *tp_pattern ;
int p_pattern_comp( const void * pt1, const void * pt2){
	tp_pattern p1=*(tp_pattern*)pt1, p2=*(tp_pattern*)pt2;
	if( p1->times != p2->times )
		return p1->times - p2->times ;
	if( p1->len != p2->len )
		return p2->len - p1->len ;
	return -strcmp(p1->str, p2->str);
}
int n_pattern=0;
char cur_pattern[_max_pattern_+1];
void get_count( t_tries *pc, int height) {
	if( height>up )
		return ;
	if( height>=low && pc->count ){
		patterns[n_pattern].times = pc->count, patterns[n_pattern].len = height;
		memcpy( patterns[n_pattern].str, cur_pattern, height );
		patterns[n_pattern++].str[height] = '\0' ;
	}
	cur_pattern[height]='0';
	get_count( pc->next[0], height+1 );
	cur_pattern[height]='1';
	get_count( pc->next[1], height+1 );
}

int main() {
	freopen("contact.in", "r", stdin);
	freopen("contact.out", "w", stdout);
	cin >> low >> up >> n_th ;
	char *p_seq=sequence ;
	while (	cin >> p_seq )
		p_seq += strlen( p_seq );
	seq_size = p_seq-sequence ;
	for( p_seq=sequence; *p_seq!='\0'; p_seq++ )
		*p_seq -= '0' ;
	*p_seq = -1 ;
	
	build_tries(up) ;
	char *p_end=p_seq+seq_size-low ;
	for( p_seq=sequence; p_seq<p_end && *p_seq!=-1; p_seq++ ) {
		register t_tries *p_trie=tries_buf+1 ;
		for( register char *pc=p_seq; pc<p_seq+up && *pc!=-1; pc++ )
			p_trie=p_trie->next[*pc], p_trie->count++ ;
	}

	get_count(tries_buf+1,0);
	for( int i=0; i<n_pattern; i++){
		p_patterns[i] = patterns+i ;
	}
	qsort( p_patterns, n_pattern, sizeof(tp_pattern), p_pattern_comp );

	for( int i=n_pattern-1, pre_times=0, pc=0, tc=0; i>=0; i-- ){
		if( pre_times != p_patterns[i]->times ) {
			if( pc && tc ) 
				cout << endl ;
			if( pc==n_th )
				break ;
			cout << p_patterns[i]->times << endl ;
			pre_times=p_patterns[i]->times, pc++, tc=0 ;	
		} 
		if( tc )
			cout << " " ;
		cout << p_patterns[i]->str , tc++;
		if( tc==6 || !i )
			cout << endl , tc=0 ;
	}
	return 0;
}