This week’s learning summary 22.4.18-4.24 Binary tree, search and sorting

This week, due to two interviews, 12 class-hours of large-scale experiments for three weeks, two-sided qt program development learning in the [smart agriculture] laboratory, python training of Qihang company and school etiquette team training, and editing of artificial intelligence and mathematics major admissions videos , it took up a lot of study time, so my coding time was concentrated after eleven o’clock in the evening, and because there was still early self-study in the morning and I needed to get up early, there was very little time to really sit in front of the computer and type code, so This week, I mainly read blogs, materials and topics, and try to squeeze as much time as possible to do the questions. I usually spend trivial time outside to read blogs and materials.

[I learned about the binary tree] in the last class , and it is easy to understand, but when I am doing the problem, how to store the binary tree stumped me

P4715 [Shenji 16. Example 1] Knockout – Luogu | New Ecology of Computer Science Education (luogu.com.cn)

This question can be said to help me solve the problem of storing a binary tree. This question is a 1v1 competition for the final champion. Both sides used a binary tree. The two players in a game are sibling nodes, and the final champion is the root node. At first, all The player is a leaf node. At this time, the way to store the binary tree is to create an array, the first to store the root node, the second and third to store the two child nodes of the root node, until the last leaf node is stored in the array. Then start the game from the leaf node, and the winner is stored in the parent node until the root node is filled. This process can be realized by a recursive function.

#include<iostream>
#include<cmath>
using namespace std;
int a[100000000],n,num,win[100];
void dfs(int x){
    if(x>=num)return;
    else{
        dfs(2*x);
        dfs(2*x+1);
        int left=a[2*x],right=a[2*x+1];
        if(left>right){
            win[x]=win[2*x];
            a[x]=left;
        }else{
            win[x]=win[2*x+1];
            a[x]=right;
        }
    }
}
int main(){
    cin>>n;
    num=pow(2,n);
    for(int i=0;i<num;i++){
        cin>>a[i+num];
        win[i+num]=i+1;
    }
    dfs(1);
    if(a[2]>a[3])cout<<win[3];
    else cout<<win[2];
}

You are given a [grid] with nn rows and mm columns. Rows and columns are numbered from 11 to nn, and from 11 to mm. The intersection of the aa-th row and bb-th column is denoted by (a,b)(a,b).

Initially, you are standing in the top left corner (1,1)(1,1). Your goal is to reach the bottom right corner (n,m)(n,m).

You can move in four directions from (a,b)(a,b): up to (a−1,b)(a−1,b), down to (a+1,b)(a+1,b), left to (a,b−1)(a,b−1) or right to (a,b+1)(a,b+1).

You cannot move in the same direction in two consecutive moves, and you cannot leave the grid. What is the minimum number of moves to reach (n,m)(n,m)?

gives you a grid of n rows and m columns. Rows and columns are numbered from 1 to n and from 1 to m. The intersection of row a and column b is denoted as (a,b).

Initially, you are standing in the upper left corner (1,1). Your goal is to reach the bottom right corner (n,m)

You can move from (a,b) in four directions: up to (a−1,b), down to (a+1,b), left to (a,b−1) or right to (a,b+ 1).

You cannot move in the same direction twice in a row, and you cannot leave the grid. What is the minimum number of steps to get to (n,m)?

This is a question I encountered on codeforces. This question also stumped me for a long time, so I had no idea to do it. Then I drew a few tables on the scratch paper and found that as long as I walked along the diagonal to the edge, You can get the minimum number of steps by walking along the edge, that is, first to the right, then up, and then down to the right grid. The specific implementation is as follows:

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int k=1;k<=t;k++){
        int n,m,num=0;
        cin>>n>>m;
        if((n==1&&m>2)||(m==1&&n>2)){
            cout<<"-1"<<endl;
            continue;
        }
        if(n==1&&m==1){
            cout<<0<<endl;
            continue;
        }
        if(m>=n){
            num+= 2 *n -1 ;
        }else{
            num+= 2 *m -1 ;
        }
        int abc=abs(m-n);
        if(abc%2==0){
            num+=3*(abc/2)+abc/2;
        }else{
            num+=3*(abc/2)+abc/2+1;
        }
        cout<<num-1<<endl;
    }
}

For the competition, after so many competitions, I have found several shortcomings in myself. One is that it is too slow to find ideas , and it takes a long time to read each question. Moreover, since I am a Japanese student and cannot speak English, I need to use translation software. , Sometimes the inaccuracy of translation software translation affects the thinking of reading questions. Every time my classmates make the first question, I just finished reading the question; there are always some small errors when typing the code , for example, I forgot to add after main ( ), this low-level error appeared in question C of the last competition, resulting in a waste of at least 20 minutes of time, and in the end it was only a few minutes away from the question; the third point is the problem of energy , maybe the competition In the first hour, the brain can still run at full capacity, but after that, the brain starts to stop moving. Sometimes a very simple algorithm takes a long time to conceive, and lack of energy is also a major reason for affecting the game.

Leave a Comment

Your email address will not be published. Required fields are marked *