2021“MINIEYE杯”中国大学生算法设计超级联赛（7）Fall with Trees 等比数列

😊 | Powered By HeartFireY

Problem Analysis

根据二叉树本身性质以及题目给出的条件限制，我们发现整棵树倾向于三角形的组合。那么我们不妨设第二层两个节点间的距离为 l e n 2 = d len_2 = d len2​=d，那么我们不难发现，第 k k k层的宽度为 ∑ i = 2 k l e n 2 × 2 2 − i = d × ( 2 − 2 2 − k ) \sum ^k_{i = 2} len_2 \times2^{2 - i} = d \times (2 - 2^{2 - k}) ∑i=2k​len2​×22−i=d×(2−22−k)，那么我们可以求出 k k k与 k + 1 k + 1 k+1层之间的面积： S k   k + 1 = 1 2 × ( l e n k + l e n k + 1 ) × h S_{k\ k+1} =\frac{1}{2} \times (len_k + len_{k + 1}) \times h Sk k+1​=21​×(lenk​+lenk+1​)×h​。

那么只需要对每层面积求和即可。求和的过程可以使用等比数列求和完成。

Accepted Code

#include 
using namespace std;

signed main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        double x, y, xl, yl, xr, yr; cin >> x >> y >> xl >> yl >> xr >> yr;
        double h = abs(yl - y), a = xr - xl;
        double ans = a * h / 2 * (4 * (n - 2) + 3 * pow(0.5, n - 2) - 2);
        printf("%.3lf\n", ans);
    }

    return 0;
}