Count & 树的同构 解题报告

之所以两道题放在一起,就是因为他们很相似。

题目一:Count

大项堆是具有如下性质的二叉树:

  1. 它的任意一个父亲节点的权值总是比孩子的权值要大
  2. 它是一颗完全二叉树

先给定这个堆的节点个数N,假如每个节点的权值都为在1—N之间的整数且各不相同,求可能的大项堆的个数。当然,这个个数可能很多,这里只要求这个个数模K即可。

输入: 两个用空格隔开的整数N和Q(N<30,Q<10^9) 输出: 可能的大项堆的个数模Q

输入样例: 3 1000 输出样例: 2

题目二:树的同构

排序二叉树是我们熟悉的一种数据结构,这里提到的排序二叉树都是指根的关键字比左子树上的所有点都大,比右子树上的都小(假定不存在相同的关键字)的排序二叉树。如果给定一个输入序列,按照这个序列依次将各个结点插入,我们就得到了一棵排序二叉树。例如,输入序列 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 5 2 1 3、4 5 2 3 1、4 5 3 1 2、4 5 3 2 1 这八组输入顺序。

数据范围: 对于 100% 的数据,N <= 1,000,每组数据 10 分。 对于 120% 的数据,N <= 100,000,每组数据 20 分。

思路分析

这两个题目主要在于初始化的不同。Count 可以自己虚拟建树,而 树的同构 则必须按要求建树。建过树之后,这两个题目是完全相同的,都是树形动态规划。用DP

\[r\]

表示节点r为根的树所能产生的种类或其mod后的数值。 动态转移方程为:

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

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

完整代码

//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 boolean; 

Function GetComb(m,n:longint):longint; 
begin 
   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-1) mod q)) mod q; 
   exit(comb[m,n]); 
end; 

Procedure dpit(p:longint); 
begin 
   if not tree[p] then begin dp[p,1]:=1 mod q; dp[p,2]:=0; exit; end; 
   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; 
end; 

begin 
   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-2) then begin ci:=1; inc(c); end else inc(ci); 
      end; 
   end; 
   fillchar(dp,sizeof(dp),0); 
   dpit(1); 
   writeln(dp[1,1] mod q); 
   close(output); 
end.

完整代码:树的同构

//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; 
        end; 
Var  
   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 longint; 

Procedure 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; 
   end; 
end; 

Function getcomb(n,m:longint):longint; 
begin 
   if comb[n,m]<>0 then exit(comb[n,m]); 
   if m=1 then exit(n); 
   if (n=m)or(m=0) then exit(1); 
   comb[n,m]:=(getcomb(n-1,m)+getcomb(n-1,m-1))mod 10007; 
   exit(comb[n,m]); 
end; 

Procedure 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]; 
end;` 

begin 
   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.

题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: