题目大意

求给定高度为 n 的 AVL 树最少的结点数模$1e9+7$的值.

Hint: $(a+b)%p = (a%p) + (b%p)$

难点和解题思路

原题目给出了关于 AVL 树的相关定义,帮助我们理解题目的相关概念. AVL树就是平衡的二叉排序树, 能够保证这棵树在满足二叉排序树基本特性的同时, 每一个非叶子节点的左右子树节点数之差不大于1.

关于高度为$h$的 AVL 树的最少节点数,其实是有递推公式的, 就是$h[n] = h[n-1]+h[n-2]+1, n>2$

根据这个递推公式, 就可以将问题从看似复杂的树问题转化为类似求解斐波那契数列的简单问题了.

还有一个坑点, 就是题目给出的AVL树的高度可能会很高, 从数据规模上看, 斐波那契型的数列通项都是指数型增长的, “正常"的数据类型分分钟存不下这么大的数据.

再仔细看题目, 要求的只是结果模$1e9+7$然后输出, 还给出了余数相关的定理来"暗示”, 不由得想到这样的思路, 首先建一个 long long 类型的大数组h[MAX_N], 高度为i 的 AVL 树的节点数对1e9+7取模的结果储存在 h[i]中, 然后用相同的递推关系计算数组的每一个元素. 而且, 还可以将取余操作简化为减法操作, 大大的降低算法的运行时间.

代码

因为题目的原题和测试数据在考试结束之后就及时关闭了, 所以只能凭借记忆写下来.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstring>
using namespace std;
long long w = 1000000007;
long long res[100050];
int main(){
  int T;
  cin>>T;
  memset(res,0,sizeof(res));
  res[1] = 1;
  res[2] = 2;
  for(int i=3;i<100050;i++){
    res[i] = res[i-1]+res[i-2];
    if(res[i]>w) res[i]-=w;
  }
  while(T--){
    int h;
    cin>>h;
    cout<<res[h]<<endl;
  }
}

注意事项

long long 类型最好还是使用 cout 来处理读写, 在本机调试时发现,用 printf("%lld")处理出现了奇奇怪怪的 bug, 用 cout 就没事了.
数组预处理放在循环以外进行, 否则很有可能超时.
上面的示例代码, 在 BOJ 测试时时间性能是59ms( 上限是1000ms)