USACO - 3.1.5 - Contact

 

原创文章转载请注明出处

摘要：二叉树的应用 ，三星

一. 题目翻译

1. 描述：

奶牛们开始对用射电望远镜扫描牧场外的宇宙感兴趣。最近，他们注意到了一种非常奇怪的脉冲调制微波从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的，还是仅仅是普通的的星星发出的。

帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在A到B之间（含）在每天的数据文件中重复得最多的比特序列 (1 <= A <= B <= 12)。他们在找那些重复得最多的比特序列。一个输入限制告诉你应输出多少频率最多的序列。

符合的序列可能会重叠，并且至少出现一次的序列会被计数。

2. 格式：

          INPUT FORMAT:

          第一行： 三个用空格分隔的整数: A, B, N; (1 <= N < 50)

          第二行及以后: 一个最多200，000字符的序列，全是0或1; 每行字符数不大于80。

          OUTPUT FORMAT:

          输出N个频率最高的序列（按照频率由高到低的次序）。由短到长排列频率相同的这些序列，如果长短相同，按二进制大小排列。如果出现的序列个数小于N，输出存在的序列。

          对于每个存在的频率，先输出单独包含该频率的一行，再输出以空格分隔的这些频率。每行六个（除非少于六个剩下）。

3. SAMPLE：

          SAMPLE INPUT:

2 4 10

01010010010001000111101100001010011001111000010010011110010000000

在样例里，序列100出现了12次，而序列1000出现了5次。次数最多的序列是00，出现了23次。

          SAMPLE OUTPUT:

23

00

15

01 10

12

100

11

11 000 001

10

010

8

0100

7

0010 1001

6

111 0000

5

011 110 1000

4

0001 0011 1100

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

         看到这道题目其实应当可以想到一个最简单方法就是用一个hash表将所有出现过的字符串存储起来，如果查hash表里面有则将原来的值++，如果没有则在hash表中增加一个key为字符串，value为0的新节点（在网上看到有大牛用java写这种方法也过了，大家有兴趣的话可以尝试一下）。

          这道题目还有一个非常巧妙的解法，数据结构是一个满二叉树（大家可以先自己思考下为什么）。

(囧， 插图很复杂啊。。。就是一颗二叉树，类似于霍夫曼编码的二叉树)

参考上面的这幅图，大家可以看到。00字符串出现的次数=000字符串出现的次数+001字符串出现的次数。那么对应到我们的这一道题目，我们求出所有长度为B（题目中要求的最大长度）的字符串出现的次数就可以向上推出任意的长度大于等于A（最小长度）的字符串出现次数。 那么现在又出现了一个新的问题，就是如何表示这颗树 ？ 常用的树有两种表示方法：1. 用链表，左孩子，右孩子；2.用一个数组，这道题目我们使用数组的表示方法，数中节点与数组下标的对应我们可以参考满二叉树的编码（满二叉树中节点i的左孩子是2*i+1，右孩子是2*i+2）。

 

2. 具体实现（具体实现过程中出现的问题）：

在具体实现的过程中，出现了如下的一个问题。就是对于题目中给出的字符串最后的A位，由于他们之后没有节点了，所以在数中也无法递推产生他们的出现次数。

         举个例子：程序sample当中01010010010001000111101100001010011001111000010010011110010000000这个串的最后三位000，由于我们是通过长度为4的字符串递推产生长度小于4的字符串出现频率，那么000我们会少计算1次，00会少计算2次，0会少计算3次。

       所以在程序实现的过程中，除了需要将所有长度为A的字符串的出现次数统计出来外，还需要将字符串最后A-1当中各种长度的字符串统计一次。有了这个以后我们需要修改原来的方程如下 父节点出现的次数=左孩子出现的次数+右孩子出现的次数+父节点之前出现的次数（在输入字符串的后A位中）。

        算法的实现请参考代码注释。

4. 启示:

          非常有意思的一道题目，对于这类统计字符出现次数的题，这一道很不错，大家可以积累、参考。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:contact
*/
package session_3_1_5;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class contact {

	public static void main(String[] args) throws Exception {

		PrintWriter pw = new PrintWriter(System.out);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
//		BufferedReader br = new BufferedReader(new FileReader("contact.in"));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
//		"contact.out")));
		
		StringTokenizer tokens = new StringTokenizer(br.readLine());
		
		int A = Integer.parseInt(tokens.nextToken());
		int B = Integer.parseInt(tokens.nextToken());
		int N = Integer.parseInt(tokens.nextToken());

		int[] tree = new int[16384];//存储完全二叉树的数组，由于题目当中要求最大的子串长度为12，所以树的最大深度应当为12层。但是在题目当中字符串可以以1开始，所以我们加入一层。数的深度为13，节点总和为2^14
		ArrayList<Node> al = new ArrayList<Node>();//存储结果

		StringBuilder sb = new StringBuilder();
		String readLine = br.readLine();
		while(readLine!=null){
			sb.append(readLine);
			readLine = br.readLine();
		}

		for (int i=0;i+B<=sb.length();i++){//将长度为B的所有字符串出现次数存储在树中
			String line = sb.substring(i, i+B);
			add(line ,tree ,B);
		}
		
		for (int i=B-1;i>=1;i--){//统计给定字符串最后B-1位各长度字符串出现的次数
			for (int j=sb.length()-i;j>=0&&i+j<=sb.length();j++){
				String line = sb.substring(j, j+i);
				add(line, tree, i);
			}
		}
		
		caculate(tree , A, B, al);//根据解题报告当中给出的公式推算各种长度字符串出现的频率
		print(al, pw ,N);
	}

	//更新line描述字符串出现次数
	public static void add(String line ,int[] tree ,int B) {
		int index = 0;
		for (int i=0;i<B;i++){
			char temp = line.charAt(i);
			if (temp=='0'){
				index = 2*index + 1;
			} else if (temp=='1'){
				index = 2*index + 2;
			}
		}
		tree[index]++;
	}
	
	//根据解题报告当中给出的公式结算各长度字符串出现的频率
	public static void caculate(int[] tree ,int A ,int B ,ArrayList<Node> al) {
		int start = 0;
		int end = 0;
		for (int i=0;i<A;i++){
			start = 2*start + 1;
		}
		for (int i=0;i<B;i++){
			end = 2 * end + 2; 
		}
		for (int i=end;i>=start;i--){
			tree[i] = tree[i] + tree[2*i+1] + tree[2*i+2];//当前节点表示的字符串出现次数=左孩子+右孩子+字符串后B-1位中的次数
			if (tree[i]!=0)
				al.add(new Node(i,tree[i]));//如果字符串出现次数大于1，则加入结果集中排序，结果用Node类封装。
		}
		Collections.sort(al);
	}
	
	//输出，我写的有点复杂，大家掌握思路以后可以自己写个。
	public static void print(ArrayList<Node> al ,PrintWriter pw ,int N){
		int tempTimes = 0;
		int tempCnt = 1;
		int count = 0;
		StringBuilder output = new StringBuilder();
		for (int i=0;i<al.size();i++){
			Node node = al.get(i);
			if (i==0){
				tempTimes = node.times;
				tempCnt =1 ;
				output.append(tempTimes+"\n");
				output.append(node.binary+" ");
			} else {
				if (node.times == tempTimes){
					if (tempCnt <= 5){
						output.append(node.binary+" ");
						tempCnt++;
					} else {
						output.deleteCharAt(output.length()-1);
						output.append("\n");
						output.append(node.binary+" ");
						tempCnt = 1;
					}
				} else {
					output.deleteCharAt(output.length()-1);
					count ++;
					if (count==N){
						break;
					} else {
						output.append("\n");
						output.append(node.times+"\n");
						output.append(node.binary+" ");
						tempCnt = 1;
						tempTimes = node.times;
					}
				}
			}		
		}
		if (output.charAt(output.length()-1)==' '){
			output.deleteCharAt(output.length()-1);
		}
		pw.println(output);
		pw.close();
	}
}

//记录结果用的，大家可以不用参考
class Node implements Comparable<Node>{
	int posistion;
	int times;
	String binary;
	int value;
	int length;
	
	public Node(int position ,int times) {
		this.posistion = position;
		this.times = times;
		binary = getBinary();
		value = getValue();
	}
	
	private String getBinary(){
		StringBuilder result = new StringBuilder("");
		int temp = posistion;
		while (temp!=0){
			if (temp%2 == 1){
				result.append(0);
			} else {
				result.append(1);
			}
			length++;
			temp = (temp-1)/2;
		}
		result.reverse();
		return result.toString();
	}
	
	private int getValue(){
		int result = 0;
		for (int i=0;i<binary.length();i++){
			char temp = binary.charAt(i);
			if (temp == '1'){
				result = 2*result + 1;
			} else {
				result = 2*result;
			}
		}
		return result;
	}
	
	@Override
	public int compareTo(Node o) {
		if (times>o.times){
			return -1;
		} else if (times == o.times){
			if (length > o.length){
				return 1;
			} else if (length == o.length){
				if (value > o.value){
					return 1;
				} else if (value == o.value){
					return 0;
				} else {
					return -1;
				}
			} else 
				return -1;
			
		} else {
			return 1;
		}
	}
}