Blue Bridge Cup practice 014

FBI Trees

Problem description

We can turn the “0” and “1” There are three types of strings ： whole “0” The string is called B strand , whole “1” The string is called I strand , Both contain “0” It also includes “1” The string of is called F strand .
　　FBI A tree is a binary tree , Its node types also include F node ,B Node sum I There are three kinds of nodes . By a length of 2^n Of “01” strand S You can build a tree FBI Trees T, The construction of recursion is as follows ：
　　1)T The root node of is R, Its type and string S Same type of ;
　　2) Ruoshan S Is longer than 1, String S Separate from the middle , It is divided into equal length left and right substrings S1 and S2; From left sub string S1 structure R The left subtree T1, From the right sub string S2 structure R The right subtree T2.
　　 Now let's give a length of 2^n Of “01” strand , Please construct a FBI Trees , And output its post order traversal sequence .

Input format

The first line is an integer N（0 <= N <= 10）, The second line is a length of 2N Of “01” strand .

Output format

Including a line , This line contains only one string , namely FBI The subsequent traversal sequence of the tree .

The sample input

3
10001011

Sample output

IBFBBBFIBFIIIFF

Data size and engagement

about 40% The data of ,N <= 2;
　　 For all the data ,N <= 10.

Their thinking

 Dichotomy problem solving 
 Using recursion 
 Deal with the left first , And then on the right 
 Count separately 
 Process the results and output the results 

Code example

#include <iostream>
#include<string>
using namespace std;

string str;

void fun(int left,int right){
    
  if(left>right)return;
  int CntB=0,CntI=0;// Record B and I The number of 
  int mid=(left+right)/2;// Find the middle position 
  if(left!=right){
    
    fun(left,mid);// Recursively handle the left part 
    fun(mid+1,right);// Deal with the part on the right 
  }
  while(left<=right){
    
    if(str[left++]=='0')// by 0 when B Add one to the number of 
      CntB++;
    else 
      CntI++;//I Increase in the number of 1
  }
  if(CntB!=0&&CntI!=0)cout<<"F";//0 1  There are , Output F
  else if(CntB!=0&&CntI==0)cout<<"B";// Only 0
  else cout<<"I";// Only 1

}
int main()
{
    
  int n;
  cin>>n;
  cin>>str;
  fun(0,str.length()-1);
  cout<<endl;
  return 0;
}

The weight of a complete binary tree （2019 The annual provincial competition ）

Title Description

Given a tree containing N A complete binary tree of nodes , Every node in the tree has a weight , Press from Up and down 、 The order from left to right is A1,A2,⋅⋅⋅A**N*, As shown in the figure below ：

Now Xiaoming will add the weights of nodes of the same depth together , He wants to know which depth node Maximum sum of weights ？ If there are multiple depth weights and the same is the maximum , Please output the minimum depth .

notes ： The depth of the root is 1.

Input description

The first line contains an integer N*（1≤*N≤10^5）.

The second line contains N It's an integer A1,A2,⋅⋅⋅AN (−10^5 ≤Ai≤10^5).

Output description

Output an integer to represent the answer .

I/o sample

Example

Input

7
1 6 5 4 3 2 1

Output

2

Operation limit

• Maximum operation time ：1s
• Maximum running memory : 256M

Code example

#include <iostream>
#include<cmath>
using namespace std;

typedef long long ll;
ll n,i,j;
ll maxx=-100000;
ll a[100010];

void fun(ll n)
{
    
  ll m=n;
  ll k=0;// The layer number 
  ll flag;// Mark 
  while(m){
    
    m/=2;
    k++;
  }// At the end of the cycle k Is the number of layers of the binary tree 
  ll sum;// The sum of the 
  for(i=1;i<k;i++){
    // Go through each layer 
    sum=0;
    ll t1=pow(2,i-1);// front i-1 Number of layers 
    ll t2=pow(2,i);// front i Number of layers 
    for(j=t1;j<=t2-1;j++){
    
      sum+=a[j];// Will be the first i The data of the layer is added up 
    }
    if(sum>maxx){
    
      maxx=sum;// If the maximum value is exceeded , Update and mark the location 
      flag=i;
    }
  }
  sum=0;
  for(i=pow(2,k-1);i<=n;i++){
    //k-1 Layer to n layer 
    sum+=a[i];
  }
  if(sum>maxx){
    
    maxx=sum;
    flag=k;
  }
  cout<<flag<<endl;
}

int main()
{
    
  //  Please enter your code here 
  cin>>n;
  for(i=1;i<=n;i++)
    cin>>a[i];// Read in the data 
  fun(n);// Handle 
  return 0;
}