题意：
一棵K叉哈弗曼树，只有中间节点（满儿子）和叶节点两种。给出1-k的连续编码，求出哈弗曼树的结构。
解法：
首先要清楚，哈弗曼编码是一种没有公共前缀的编码，这提供了很重要的剪枝条件
另外，由于树中只含有满节点和空节点（叶子节点），故每分出一个枝条（从叶节点变为一棵子树）至少增加n-1个叶子节点。
利用以上两点，就可以很好的剪枝了。
剪枝判断还是通过字典树（额，这题中似乎叫哈弗曼树比较合适- -）。详细看程序吧。
代码：
1
# include <cstdio>
2 # include <cstring>
3 # include <vector>
4 using namespace std;
5 struct node
6
{
7
node *nxt[20];
8 int count;
9 bool end;
10 node()
11
{
12 memset(nxt,NULL,sizeof(nxt));
13 count=0;
14 end=0;
15
}
16
};
17 int z,n,count,len,c;
18 node buffer[100000];
19 node *head;
20 char str[250];
21 int ans[21];
22 void clear(node *p)
23 {
24 memset(p->nxt,NULL,sizeof(p->nxt));
25 p->end=false;
26 p->count=0;
27 }
28 bool solve(int s,int left,node *p)
29 {
30 if(count>z||p->end) return false;
31 if(s==len&&left==0) return true;
32 else if(left<=0) return false;
33 p->count++;
34 if(p->count==1)
35 {
36 p->end=true;
37 if(solve(s,left-1,head))
38 {
39 ans[z-left+1]=s;
40 return true;
41 }
42 p->end=false;
43 }
44 if(s==len)
45 {
46 p->count--;
47 return false;
48 }
49 if(p->count==1) count+=n-1;
50 if(p->nxt[str[s]-48]==NULL)
51 {
52 p->nxt[str[s]-48]=&buffer[c++];
53 clear(p->nxt[str[s]-48]);
54 }
55 if(solve(s+1,left,p->nxt[str[s]-48])) return true;
56 if(p->count==1) count-=n-1;
57 p->count--;
58 return false;
59 }
60 int main()
61 {
62 int test;
63 scanf("%d",&test);
64 while(test--)
65 {
66 c=1;
67 count=1;
68 head=&buffer[0];
69 clear(head);
70 scanf("%d%d%s",&z,&n,str);
71 len=strlen(str);
72 solve(0,z,head);
73 ans[0]=0;
74 for(int i=0;i<z;i++)
75 {
76 printf("%d->",i);
77 for(int j=ans[i];j<ans[i+1];j++)
78 printf("%c",str[j]);
79 printf("\n");
80 }
81 }
82 return 0;
83 }