之所以两道题放在一起,就是因为他们很相似。
本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。
题目一:Count
大项堆是具有如下性质的二叉树:
1.它的任意一个父亲节点的权值总是比孩子的权值要大
2.它是一颗完全二叉树
先给定这个堆的节点个数N,假如每个节点的权值都为在1—N之间的整数且各不相同,求可能的大项堆的个数。当然,这个个数可能很多,这里只要求这个个数模K即可。
输入:
两个用空格隔开的整数N和Q(N<30,Q<10^9)
输出:
可能的大项堆的个数模Q
输入样例:
3 1000
输出样例:
2

题目二:树的同构
本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。
排序二叉树是我们熟悉的一种数据结构,这里提到的排序二叉树都是指根的关键字比左
子树上的所有点都大,比右子树上的都小(假定不存在相同的关键字)的排序二叉树。如果
给定一个输入序列,按照这个序列依次将各个结点插入,我们就得到了一棵排序二叉树。比
如输入序列 4 2 1 3 5,对应如下排序二叉树:
2
4
5
1 3
而输入序列4 5 2 1 3 以及4 2 5 1 3都对应同样的树,我们说这三个序列同构。现在给定
一个长度为N的输入序列,求与之同构的序列有多少个(包括这个序列本身)。由于问题的
答案可能比较大,只要求输出答案 mod 10,007的结果。
Input
第1行:一个正整数N,即输入序列长度。
第2行:N个1—N之间的正整数,数字相互之间不重复。
Output
仅有一行,即同构序列数 mod 10,007的长度。
Sample Input
5
4 2 1 3 5
Sample Output
8
样例解释:

4 2 1 3 5
4 2 1 5 3
4 2 3 1 5
4 2 3 5 1
4 2 5 1 3
4 2 5 3 1
4 5 2 1 3
4 5 2 3 1
这八组输入顺序。
数据范围:
对于100%的数据, N<=1,000 ,每组数据10分
对于120%的数据, N<=100,000,每组数据20分

思路分析
本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。
这两个题目主要在于初始化的不同。Count 可以自己虚拟建树,而 树的同构 则必须按要求建树。建过树之后,这两个题目是完全相同的,都是树形动态规划。用DP[r]表示节点r为根的树所能产生的种类或其mod后的数值。
动态转移方程为:

 
   dp[r] = dp[r.左树] * dp[r.右树] * 求组合数(左右子树的节点数之和, 左/右子树的节点数(用数学可轻易证明左/右子树的节点数的结果相同)) 


其实质是,对于一个父亲,如何安排它的孩子的情况呢?那就要挑选出一部分数字(对于题目count)(对于树的同构是位置)安排给左子树使用,其余的数字(或位置)自然就分给右子树了。用组合而不是排列,原因是对于每一个组合,具体如何排列这些数字或位置,已经由子树DP的数值所包括题目容易被误解为使用排列。

完整代码:Count
本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。

 
//By Ceeji 
//Date: 2009-4-9 
//HAOI test 6 - Problem 1 : count 
//Type : Tree DP 
//State: Accepted 
Program count; 
Const 
   fin='count.in'; 
   fou='count.out'Var 
   n,q,c,ci,i:longint; 
   comb:array[0..31,0..31]of longint; 
   dp:array[0..100,1..2]of int64; 
   tree:array[0..100]of booleanFunction GetComb(m,n:longint):longintbegin 
   if m=n then exit(1); 
   if n=0 then exit(1); 
   if n=1 then exit(m); 
   if comb[m,n]<>0 then exit(comb[m,n]); 
   comb[m,n]:=((getComb(m-1,n) mod q)+(getComb(m-1,n-1mod q)) mod q; 
   exit(comb[m,n]); 
endProcedure dpit(p:longint); 
begin 
   if not tree[p] then begin dp[p,1]:=1 mod q; dp[p,2]:=0exitend; 
   dpit(p<<1); 
   dpit(p<<1+1); 
   dp[p,2]:=dp[p<<1,2]+dp[p<<1+1,2]+1; 
   dp[p,1]:=getComb(dp[p,2]-1,dp[p<<1,2]); 
   dp[p,1]:=(dp[p,1]*dp[p<<1,1])mod q; 
   dp[p,1]:=(dp[p,1]*dp[p<<1+1,1])mod q; 
endbegin 
   assign(input,fin);  reset(input); 
   assign(output,fou); rewrite(output); 
   readln(n,q); 
   close(input); 
   fillchar(comb,sizeof(comb),0); 
   fillchar(tree,sizeof(tree),0); 
   c:=1; ci:=1; 
   for i:=1 to n do 
   begin 
      if c=1 then 
      begin 
        tree[ci]:=true; 
        ci:=1; inc(c); 
      end 
      else begin 
        tree[2<<(c-2)+ci-1]:=true; 
        if ci=2<<(c-2then begin ci:=1; inc(c); end else inc(ci); 
      end; 
   end; 
   fillchar(dp,sizeof(dp),0); 
   dpit(1); 
   writeln(dp[1,1mod q); 
   close(output); 
end

完整代码:树的同构
本解题报告版权归 Ceeji 所有,转载请注名出处并保留本注释。

 
//By Ceeji 
//HAOI test 5 - Problem 2 : Tree 
//Date: 2009-3-31 
//Type : Tree DP 
//State: Accepted 
Program tree; 
Const  
   inf='tree.in'; 
   ouf='tree.out'Type  
   node=record 
          v,l,r:longint; 
        endVar  
   n,i,j,m:longint; 
   t:array[1..1000]of node; 
   comb:array[0..1000,0..1000]of longint; 
   dp:array[0..1000,1..2]of longintProcedure add(j,i:longint); 
begin 
   if j<t[i].v then 
   begin 
      if t[i].l=0 then begin inc(m); t[i].l:=m; t[m].v:=j; end 
      else begin add(j,t[i].l); end; 
   end 
   else 
   begin 
      if t[i].r=0 then begin inc(m); t[i].r:=m; t[m].v:=j; end 
      else begin add(j,t[i].r); end; 
   endendFunction getcomb(n,m:longint):longintbegin 
   if comb[n,m]<>0 then exit(comb[n,m]); 
   if m=1 then exit(n); 
   if (n=m)or(m=0then exit(1); 
   comb[n,m]:=(getcomb(n-1,m)+getcomb(n-1,m-1))mod 10007; 
   exit(comb[n,m]); 
endProcedure dpit(p:longint); 
begin 
   if dp[t[p].l,1]=0 then dpit(t[p].l); 
   if dp[t[p].r,1]=0 then dpit(t[p].r); 
   dp[p,1]:=(((dp[t[p].l,1]*dp[t[p].r,1])mod 10007)*getcomb(dp[t[p].l,2]+dp[t[p].r,2],dp[t[p].l,2]))mod 10007; 
   dp[p,2]:=1+dp[t[p].l,2]+dp[t[p].r,2]; 
endbegin 
   assign(input,inf);  reset(input); 
   assign(output,ouf); rewrite(output); 
   readln(n); 
   fillchar(t,sizeof(t),0); m:=1; 
   read(j); t[1].v:=j; 
   for i:=2 to n do 
   begin 
      read(j); 
      add(j,1); 
   end; 
   close(input); 
   fillchar(dp,sizeof(dp),0); 
   fillchar(comb,sizeof(comb),0); 
   dp[0,1]:=1; 
   dp[0,2]:=0; 
   dpit(1); 
   writeln(dp[1,1]); 
   close(output); 
end.