题目链接

题目描述
平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。
给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。
输入描述:
两个整数，n, d.0 ≤ n, d ≤ 60
输出描述:
一个整数：所有高度为 n 的平衡树中不平衡度的最大值。
输入
4 1
输出
5
说明
下面这棵树在 d=1 的定义下高度是平衡的，其不平衡度为 5。
题意
在保证二叉树平衡的情况下，构造最大的不平衡度。
分析
首先贪心，最大的不平衡度应该在根节点，应该让它的一棵子树最大，另一棵最小。最大的子树显然是$$$2^{n-1}-1$$$；而最小的子树，首先想到的是用一条$$$n-d-1$$$的链代替，但是对于这条链而言，还应该为每一个节点添加一个小分支，才能使的它是平衡的。
具体的来说，如果用$$$f(n)$$$表示构造一棵高度为$$$n$$$且几乎是由链组成的平衡二叉树的节点数，那么可以让它的左子树和右子树一长一短，再加上它的根节点，就有$$$f(n)=1+f(n-1)+f(n-d-1)$$$，并且显然当$$$n\le 0$$$时$$$f(n)=0$$$，即$$$ f(n)= \begin{cases} 0,& n<=0\\ 1+f(n-1)+f(n-d-1),&n>0\\ \end{cases} $$$
因为f(n)是一个常数，可以开一个dp数组来对f(n)记录从而避免重复计算。
总结
似乎倒着推也行，似乎是有公式的，复杂度咋算啊。
代码
#include<stdio.h>
typedef long long LL;
LL dp[65] = { 0,1 };
int n, d;
LL build(int x) {
    if (x <= 0)return 0;
    if (dp[x]>0)return dp[x];
    dp[x] = 1+build(x - 1) + build(x - 1 - d);
    return dp[x];
}
 
int main() {
    while (~scanf("%d %d", &n, &d)) {
        LL left = (1LL << (n - 1)) - 1;
        LL right = build(n - 1 - d);
        printf("%lld\n", left - right);
    }
}

 

转载请注明出处:http://www.lishuoershouche.com/article/20230401/581674.html

随机推荐

  1. nowcoder 202F-平衡二叉树

    题目链接 题目描述 平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度...

  2. nowcoder 203J Graph Coloring I（dfs）

    题目链接 题目描述 修修在黑板上画了一些无向连通图，他发现他可以将这些图的结点用两种颜色染色，满足相邻点不同色。 澜澜不服气，在黑板上画了一个三个点的完全图。修修跟澜澜说，这个图我能找到一个简单奇环。 澜澜又在黑板上画了一个n个点m条边...

  3. [Nowcoder]牛客网周周练15

    Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。 原文链接：https://www.codein.icu/nowcoderweekly15/ 前言 A:乱搞 B:贪心 C:神仙题，贪心+图论？...

  4. Nowcoder | [题解-N210]牛客OI月赛2-提高组

    比赛连接戳这里_ 我才不会说这是我出的题(逃) 周赛题解\((2018.10.14)\) \(T1\) \(25\sim50\)分做法\(:\)直接爆搜 作为一个良心仁慈又可爱的出题人当然\(T1\)要送分啦\(qwq\) \(100\)...

  5. Nowcoder | [题解-N165]牛客网NOIP赛前集训营-普及组（第二场）

    啊...表示一大早还没睡醒就开始打比赛(开始前一分钟的我还在桌子上趴着休眠)...表示题目思路清奇(尤其C题)...但是我还是太蒻了...\(D\)题暴力都没打...题解正式开始之前先\(\%\)一下\(\color{#FF6161}{风...

  6. nowcoder 203A Knight（贪心+打表）

    题目链接 题目描述 有一张无限大的棋盘，你要将马从(0,0)移到(n,m)。 每一步中，如果马在(x,y)，你可以将它移动到(x+1,y+2),(x+1,y-2),(x-1,y+2),(x-1,y-2),(x+2,y+1),(x+2,y...

  7. nowcoder 202H-卡牌游戏

    题目链接 题目描述 小贝喜欢玩卡牌游戏。某个游戏体系中共有N种卡牌，其中M种是稀有的。小贝每次和电脑对决获胜之后都会有一个抽卡机会，这时系统会随机从N种卡中选择一张给小贝。普通卡可能多次出现，而稀有卡牌不会被重复抽到。小贝希望收集到K种...

  8. PAT乙级(Basic Level)练习题-NowCoder数列

    NowCoder最近在研究一个数列： * F(0) = 7 * F(1) = 11 * F(n) = F(n-1) + F(n-2) (n≥2) 他称之为NowCoder数列。请你帮忙确认一下数列中第n个数是否是3的...

  9. Nowcoder | [题解-N189]牛客OI赛制测试赛3

    这场说实话确实水(逃*1),表示差一点就AK了(逃*2),然而被卡两个特判的我\(ssfd\)...\(qwq\) 表示这是第一次发整场比赛的题解...还请各位大佬原谅我太蒻写的垃圾啊\(qwq\)... 难度:据出题人之一\(sqn\)...

  10. NowCoder BM1 反转链表

    描述 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。 NowCoder BM1 反转链表 import java.util.*; /* public class...