結題報告--P5551洛谷--Chino的樹學-有解無憂

題目：點此

題目描述

Chino樹是一棵具有某種性質的滿二叉樹，具體來說，對于這棵樹的每一個非葉子節點，它的左子節點(A)(A)(A)的右子節點(C)(C)(C)與它的右子節點(B)(B)(B)的左子節點(D)(D)(D)的值相同，且CCC與DDD下方的子樹也完全相同，現在，Chino想知道，要如何從根節點走到其中任意葉節點使路上經過的節點的權值之和最大，

思路

先分析一下Chino樹（滿二叉樹）的性質（節點編號），

k層的滿二叉樹的最后一個結點的編號是2^k-1，第一個葉子結點的編號是2^k-1，由此可知，判斷節點是否為葉子：if(i>=pow(2,k-1)//i為結點編號判斷此編號是否有對應節點：if(i>=0&&i<=pow(2,k)-1)//i為編號

定義一個變數n_1存盤2^k-1,再定義一個變數x=n_1*2-1(就是2^k-1)，

本題難點之一就是把以深搜序列輸入的樹變成在陣列里存盤的樹（陣列存盤是廣搜序列），這個問題的解決方法是：在遞回建樹的函式里加一個引數now_number，表示現在是陣列下標幾了，因為陣列下標是可以計算的：左子樹下標：now_number*2，右子樹下標：now_number*2+1，再加一個max_node_number,表示最大的結點編號，判斷是否有左子樹或右子樹，

接下來就是判斷最大值了，使用先根遍歷遍歷二叉樹，由于這棵樹是用陣列存盤的，所以這篇博客里的in_oder函式的引數可以變為now_number，再加一個now_weight，表示現在的結點權值和，

這個函式里執行：先更新now_weight，把此節點權值加進去，然后判斷此節點是否為葉子，若是則判斷是否為最大值，若是則更新最大值，結束，不是葉子則按照先根遍歷的方法繼續遍歷，

最后主函式就是這些函式的結合，

（犯的錯誤和識訓全部丟失，無法敘述）

代碼：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int tree[17000000];
 5 int read()
 6 {
 7     int s=0,w=1;
 8     char ch=getchar();
 9     while(ch<'0'||ch>'9')
10     {
11         if(ch=='-')
12             w=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16         s=s*10+ch-'0',ch=getchar();
17     return s*w;
18 }
19 
20 void maketree(int now_number,int max_node_number){
21     int now_node;
22     now_node=read();
23     tree[now_number]=now_node;
24     if(now_number*2>max_node_number){
25         return ;
26     }
27     maketree(now_number*2,max_node_number);
28     maketree(now_number*2+1,max_node_number);
29 }
30 int pow(int r){
31     if(r==1){
32         return 2;
33     }
34     int data=https://www.cnblogs.com/eason66-blog/p/1;
35     if(r%2==1){
36         data=https://www.cnblogs.com/eason66-blog/p/2;
37     }
38     int index=pow(r/2);
39     return index*index*data;
40 }
41 int maxx,n_1;
42 void pre_oder(int now_weight,int now_number){
43     now_weight+=tree[now_number];
44     if(now_number>=n_1){
45         if(now_weight>maxx){
46             maxx=now_weight;
47         }
48         return ;
49     }
50     pre_oder(now_weight,now_number*2);
51     pre_oder(now_weight,now_number*2+1);
52 }
53 int main(){
54     int n;
55     n=read();
56     n_1=pow(n-1);
57     int x=n_1*2-1;
58     maketree(1,x);
59     pre_oder(0,1);
60     cout << maxx;
61     return 0;
62 }

代碼

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56842.html

標籤：C++

上一篇：結題報告--洛谷P3915

下一篇：CodeForces 1324 - Codeforces Round #627 (Div. 3)