平衡二叉树 (牛客国庆day2)解锁二叉树打表姿势&&找规律套路

链接：https://www.nowcoder.com/acm/contest/202/F
来源：牛客网

平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。
给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。
链接：https://www.nowcoder.com/acm/contest/202/F
来源：牛客网

输入描述:

两个整数，n, d.

输出描述:

一个整数：所有高度为 n 的平衡树中不平衡度的最大值。

示例1

输入

复制

4 1

输出

复制

说明

下面这棵树在 d=1 的定义下高度是平衡的，其不平衡度为 5。

备注:

0≤ m ≤ n ≤ 60

很容易想到思路从根节点开始一边为满二叉树，另外一边为满足题目平衡条件的树的最少节点数
我和队友手推的这一题结果手算出表了但是规律找不到 难受的一批 经验严重不足

然后仔细看可以慢慢看出规律 ans表示

另外一边为满足题目平衡条件的树的最少节点数

然后仔细观察可以看到这个
ans[i] = ans[i-1] + ans[i - d - 1] + 1
附上打表代码

 1 int d, sum;
 2 struct node {
 3     int num;
 4     node *lson, *rson;
 5     node () {
 6         num = 1;
 7         lson = rson = NULL;
 8     }
 9 };
10 void del ( node* root ) {
11     if ( !root ) return ;
12     del ( root->lson );
13     del ( root->rson );
14     delete ( root );
15 }
16 int dfs ( int dep, node* root ) {
17     if ( dep <= 0 ) return 0;
18     root->lson = new node();
19     root->num += dfs ( dep - 1, root->lson );
20     sum++;
21     if ( root->num - 1 > d ) {
22         root->rson = new node();
23         dfs ( root->num - 1 - d, root->rson );
24     }
25     return root->num;
26 }
27 int main() {
28     for ( int n = 1 ; n <= 20 ; n++ ) {
29         d = 1, sum = 0;
30         node* root = new node();
31         dfs ( n - 1 - d, root );
32         printf ( "n=%d sum=%d
", n, sum );
33         del ( root );
34     }
35     return 0;
36 }

正解代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <iostream>
 8 #include <map>
 9 #include <stack>
10 #include <string>
11 #include <vector>
12 #define  pi acos(-1.0)
13 #define  eps 1e-6
14 #define  fi first
15 #define  se second
16 #define  rtl   rt<<1
17 #define  rtr   rt<<1|1
18 #define  bug         printf("******
")
19 #define  mem(a,b)    memset(a,b,sizeof(a))
20 #define  name2str(x) #x
21 #define  fuck(x)     cout<<#x" = "<<x<<endl
22 #define  f(a)        a*a
23 #define  sf(n)       scanf("%d", &n)
24 #define  sff(a,b)    scanf("%d %d", &a, &b)
25 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
26 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
27 #define  pf          printf
28 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
29 #define  FREE(i,a,b) for(i = a; i >= b; i--)
30 #define  FRL(i,a,b)  for(i = a; i < b; i++)+
31 #define  FRLL(i,a,b) for(i = a; i > b; i--)
32 #define  FIN         freopen("in.txt","r",stdin)
33 #define  gcd(a,b)    __gcd(a,b)
34 #define  lowbit(x)   x&-x
35 using namespace std;
36 typedef long long  LL;
37 typedef unsigned long long ULL;
38 const int mod = 1e9 + 7;
39 const int maxn = 1e5 + 10;
40 const int INF = 0x3f3f3f3f;
41 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
42 int n, d;
43 LL  ans[105];
44 LL expmod ( LL a, LL b ) {
45     LL ret = 1;
46     while ( b ) {
47         if ( b & 1 ) ret = ret * a;
48         a = a * a;
49         b = b >> 1;
50     }
51     return ret;
52 }
53 int main() {
54     while ( ~sff ( n, d ) ) {
55         mem ( ans, 0 );
56         for ( int i = d + 1; i <= 2 * d + 2 ; i++ ) ans[i] = i - d - 1;
57         for ( int i = 2 * d + 3; i <= n ; i++ ) ans[i] = ans[i-1] + ans[i - d - 1] + 1;
58        // fuck(ans[n]);
59         printf ( "%lld
", expmod ( 2, n - 1 ) - 1 - ans[n] );
60     }
61     return 0;
62 }