Ten common sky-level exercises in the Blue Bridge Cup – Breath of Sound. Type of Four. Simulation

Huajie quartet meets Xiaomei brothers and sisters

Hello friends (^-^)🌹🌹🌹, I am Yang Zhi , a cute blogger who is striving in the field of algorithms . I am
still a pure vegetable Wang🐢. The typical cuddly and troublesome kind πŸ‘€, can’t do a lot of things well, can’t speak a lot of words well, still doesn’t get Ac πŸ˜… in writing questions, still working hard and moving forward πŸ‘£.
Because, you are all unique to meπŸ’“ . The moment I opened this article, I believed that we need each other 🌹🌹
Always remember: write algorithms carefully and share them with heart. Live up to the algorithm, don’t make mistakes. Thank you for meeting me (^㉨^).
The ten breathing methods of the Blue Bridge Cup are the ten knowledge points selected by the author based on his own learning. In order to understand the principle of the algorithm like reading a comic. Later that day, I did encounter relevant exercises, and I can go back and combine my problem solution report to deepen my understanding.


Wonderful
past πŸ”–Blue Bridge Cup Ten Common Heavenly Exercises – Breath of Water. One Type. RecursionπŸ”–Blue

Bridge Cup Ten Common Celestial Exercises – Insect Breath.

πŸ’“About the blue bridge, about the column, about the suggestion, about you🌹

Recently, I ran the Blue Bridge Cup 31st sprint punch-in group together with the main blogger (because it is inconvenient to manage one after another, the group is now closed, hh~).
Tell me about your subjective feelings. From the questions asked by the small partners in the group, you can feel that there are some small partners about the Blue Bridge competition, how to systematically learn algorithms, the concepts of some basic algorithms, and how oj is evaluated, etc. Wait, it’s not very clear.
Because I am still a rookie dog myself, my way of thinking about problems may not be comprehensive, and my thinking is still gradually improving. Here, let’s talk about my humble opinion based on my own situation 🌹🌹🌹

Here is a small part of the phenomenon I have seen, as a support for me not to talk nonsense~

1. About Blue Bridge

Blue Bridge is a lovely OI competition system. Fill-in-the-blank questions only require one answer, and the local compiler can run the result, and then output the result directly.
For programming questions, it is a passing sample. According to the score of the sample, if the sample set by the question maker has passed, then it will be a full score. It should be noted that: you can submit it repeatedly, and the result of the judgment is based on the result of the last submission.

I think these are the more important ones, and the others can be found in the precautions for the competition, so I won’t go into details.

2. About the column

This breathing method column I am writing is to take advantage of the strength of reading Ghost Slayer manga, and summarize the common knowledge points I have seen in acwing learning algorithms and preparing for the blue bridge.
The plan is:
Breath of Water – Type One – Recursive;
Breath of Insect – Type II – Two Points;
Breath of Fire – Type Three – Dynamic Programming;
Breath of Sound – Type of Four – Simulation;
Breath of Xia – Wu The type – number theory;
the breath of love – the type of land – double pointer;
the breath of thunder – the type of Qi – search;
the breath of the wind – the type of the eight – graph theory;
the breath of the rock – the type of nine – greed;
the god of fire Music – Pickup – Advanced Data Structures.
Initially, it was finalized in this way, and there may be fine-tuning. In recent years, Blue Bridge is no longer so simple and violent, and the number of things to be mastered has gradually increased.
As for the writing style, it is similar to the recursion of the one type; the dichotomy of the two type is similar, and the knowledge points are representative of the previous Zhenti. The number of real questions in the article depends on the comics. For example, Guo You has 11 episodes, and I put 11 here.
It is more lively, with many pictures, and I am still optimizing the typesetting. The most basic and most basic, after I read it, I know why I need to record this real question, and I can quickly get what the test center is and the skills I need to master. which are.
At the same time, my friends and myself who want to read my article are comfortable to watch, and there is no visual fatigue.

3. About the suggestion

If you have a general knowledge framework for the algorithm to be tested by Lanqiao, and you have practiced the real questions yourself, then I recommend that you subscribe to my good brother’s article. Each of his articles is a set of blue bridge real questions, which is more helpful to you.

I put it home page here:

[Steering – personal profile: Sheng and Yasha, loyal to Kikyo, meaning sticking. Record the learning process and share what you love]

If you are not familiar with the blue bridge and the general test site of the algorithm competition, you can follow my blog to learn. I will summarize the knowledge points in easy-to-understand words, and put a series of very representative example questions at the same time.
My own suggestion is to read the article in general first, just have an impression in my heart, and know in my heart: there is a blog that talked about this knowledge point, and there are many real questions. I just encountered this real question today, and I will understand this knowledge point in combination with the blogger’s solution and summary.

4. About you

If you are in the sprint group and hope to check in with your friends, the discussion atmosphere inside is really good. If you should have extra practice, then you should have 150+ questions this month. As far as I know, there is no problem with winning provincial awards~
If you have your own training team, this is the best way. Alright~, just follow the training 😜
If you don’t have any, then you have to be stricter with yourself, remember to progress for the school day, I believe that the future is uncertain 🌹🌹🌹

Okay~ I officially entered Huajie and began to experience Guo Pian.

πŸ’“ Knowledge of mocks and enumerations

Simulation is actually a relatively broad concept. Generally speaking, it is not a conventional shortest path problem. For example, when it is not the optimal solution solved by dynamic regression planning, it is not greedy, and it is not the shortest path problem, you can consider whether it can be solved. Use simulation combined with enumeration to solve problems.

The emergence of the concept of enumeration is relatively straightforward. In cognition, it is a cycle.
Simply put, it is violence. Well, that’s exactly what happened.
Maybe everyone can write enumerations, but not necessarily written enumerations can be Ac. It is precisely because the idea of ​​enumeration is quite straightforward and simple, so the test point of enumeration is placed on the processing of details .
Later, on the real questions of the enumeration combined with the system, I will really feel its gameplay, and summarize some tips and thinking directions that are often used in the enumeration.

The first thing to consider in enumeration is how to find the answers we need during the traversal.
Since it is possible to obtain some points directly by violence, it can be optimized through the information hidden in the question.
Another important knowledge is how to determine the maximum number of loops you can perform with a given data range. This I summed up in One Type.

Because there is no template, the simulated questions will either be all, and the details need to be paid attention to at this time; or they will not.
Unlike other algorithms, for example, if I forget how to write the template of SPFA, and I remember it, then I don’t have this score. To put it bluntly, simulation is indeed a loop, but how to loop is also a knowledge, see if you can get the hidden information in the question, and deal with some small skills. Simulation questions, the details are really many.

πŸ’“ Ready to go

🌟The first chapter, the sum of the special numbers of the 10th Blue Bridge Cup Provincial C++ Group B

This question is a warm-up, there is no special point to pay attention to~

Go to topic description

🌱 Topic description

original title portal

🌴 Problem solving report

This question is quite a good question in enumeration. After reading the question, it is really difficult to summarize it into a certain type of special algorithm in my mind.

Problem solving ideas:

Enumerate each number in the input range, and then take this number, such as 39, and use the modulo operator and the integer division operator to take out each bit of 39.
Finally use the statement i f if i f to determine whether it contains 2, 0, 1, 9 2, 0, 1, 9 The numbers 2 , 0 , 1 , and 9 .

🌡 Reference code (C++ version)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = 0;
    for(int i = 1; i <= n;i++)
    {
        int x = i;
         while (x) // when the number still exists, keep taking it
        {
            int t = x % 10 ; //remove the ones digit 
            x /= 10 ;         //delete the ones digit of x 
            if (t == 2 || t == 0 || t == 1 || t == 9 )
            {
                //Add up the numbers that meet the conditions
                res += i;
                break;
            }
        }
    }
    //output result 
    cout << res << endl ;
     return  0 ;
}

Happy entering the second chapter

🌟 Chapter 2, 4th Blue Bridge Cup Provincial C++ Group A/B wrong ticket

The main idea of ​​this question is that for a string of data, it can be processed as a string first. Then we need to consider:
1. Reading of strings
2. How to process strings into other types of data

🌱 Topic description

original title portal

🌴 Problem solving report

This question is not too difficult, the input n n After sorting the n rows of data, enumerate the n n n numbers.
If the value of two adjacent numbers is the same, it is a double sign; if the value of two adjacent numbers is greater than or equal to 2, such as 3 3 3 and 5 5 5 . Then it’s a break

The tricky part and what needs to be mastered is the input skills of this question. 【Key points】

1. Master the reading principle of cin:

When cin reads data, it passes and ignores any leading white space characters (spaces, tabs, or newlines).
It starts reading as soon as it touches the first non-whitespace character, and stops when it reaches the next whitespace character.

Because there are too many spaces in the string of data we want to read, and the number is unknown, both cin and scanf are discouraged

2. getline function

To solve this problem, you can use the getline function. It reads the entire line, including leading and embedded whitespace, and stores it in a string object.

The syntax used is as follows:

getline( cin , inputLine); //where cin is the input stream being read, and inputLine is a variable of type string, used to receive the input string 
// use code in the title 
 getline( cin ,line);

3, stringstream quickly realizes the conversion between string type and int type

defines three classes: istringstream, ostringstream and stringstream, which are used for stream input, stream output and stream input and output operations respectively.

🌡 Reference code (C++ version)

#include <iostream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 10010;
int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;

    string line;

    //The first pit 
    getline( cin ,line); //Attention! This is used to ignore the carriage return on the first line. After the input cnt is introduced, there is a carriage return. to fix it

    while(cnt--)
    {
        //normally use the getline function to read in 
        getline( cin ,line);

        //Load the information in the string of line into ssin through stringstream 
        stringstream  ssin (line) ;

        //Because stringstream is an input and output stream, Ssin can, like cin, input the information stored in ssin into array a 
        while (ssin >> a[n]) n++;
    }

    sort(a,a+n);

    // for(int i = 0;i < n;i++) printf("%d",a[i]); 
    //The output effect is as shown in the figure, you can see that the spaces in the input data are now gone: 568991011127

    int res1,res2;
    for(int i =1;i < n;i++)

    cout <<  res1 << ' ' << res2 << endl;

    return 0;
}

🌟 Chapter 3, the moving distance of Group C++B of the 6th Blue Bridge Cup Provincial Tournament

The moving distance is mainly to let everyone understand the Manhattan distance, and the second is to get familiar with the idea of ​​mapping again.

🌱 Topic description

original title portal

🌴 Problem solving report

This question should be able to be solved with wide search, and one question can be solved more than once, but when playing a game, if you find an algorithm that is easy to write and not easy to make mistakes, it is good to find an algorithm for yourself.

For polylines to find the shortest path, you can use the Manhattan distance in geometry to solve. Combined with the formula, the distance can be quickly calculated as long as the coordinates of the two positions are known.

Manhattan Distance Overview:

The Manhattan distance is named because it is the shortest driving path between cities that are planned as square building blocks, such as Manhattan.

Calculation of Manhattan distance:

On the plane, coordinates ( x 1 , y 1 ) (x_1, y_1) (x1​,y1​) point P 1 P_1 P1​with coordinates ( x 2 , y 2 ) (x_2, y_2) (x2​,y2​) point P 2 P_2 P2​The Manhattan distance is:
d ( x , y ) d(x,y) d(x,y) = | x 1 βˆ’ x 2 x_1-x_2 x1β€‹βˆ’x2​| + | y 1 βˆ’ y 2 y_1-y_2 y1β€‹βˆ’y2​|

There are other definitions of distance scattered in our lives. Interested friends can learn about it~
The expansion of other distances

Mapping idea:

Now our goal is to get out of the building m m m and building number n n The coordinates of n , and then brought into the formula can be solved smoothly

Through mapping, we reduce all numbers by 1. Under the condition that the total number remains unchanged, when the row number and column number start from 0, and return to the form of two-dimensional array that we are familiar with, then it may be better to find the law , look at the picture, it is true

From general to special thinking direction:
Well, the most important thing in this question is to grasp the idea of ​​Manhattan distance and mapping. What we should learn is thinking.

🌡 Reference code (C++ report)

//The investigation is Manhattan distance plus some mapping ideas 
# include  <cstring>
 # include  <iostream>
 # include  <algorithm>

using namespace std;

int main()
{
    int w,m,n;

    cin >> w >>m >> n;
    m--,n--;

    //Through own simulation, realize line number conversion 
    int x1 = m/w, x2 = n/w;
     // find column number 
    int y1 = m % w, y2 = n % w;
     //because it is serpentine , the column number is different in the odd column 
    if (x1 % 2 ) y1 = w -1 -y1; //Set the law of flip 
    if (x2 % 2 ) y2 = w -1 -y2;

    //Bring in the Manhattan distance formula, output the answer 
    cout << abs (x1-x2) + abs (y1-y2) << endl ;

    return 0;
}

Take a break and move on to the tougher time and date questions

🌟 Chapter 4, Date of the 8th Blue Bridge Cup Provincial C++ Group B

In the issue of dates, in my current understanding, the most important thing is to know how to interpret whether a date is legal or not.
For example, how to quickly know the number of days corresponding to a month; for example, how to judge the normal year of a leap year; for example, the processing of February in a normal year of a leap year.

🌱 Topic description

original title portal

🌴 Problem solving report

For me,
this question has finalized two thinking directions:

1. Starting directly from the answer, verify that the solution is in the range
from January 1, 1960 to December 31, 2059 2. Honestly enumerate from January 1, 1960 to December 31, 2059, Filter out those that meet the conditions

But because I added a lot of judgment conditions in the first method, the implementation of the code is a headache

Two tips for dealing with date issues:

1. After digitizing the date, take out the year, month and day

// Take out the year, month and day 
int year = date / 10000 , month = date% 10000 / 100 , day = date % 100 ;

2. Check whether the year, month, and day of the date are legal
. The specific implementation will be very clear when combined with the code. Here I will explain this operation of storing the number of days in each month.
By saving the number of days from January to December in advance, you can quickly query when needed

int days[ 13 ] = { 0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 }; //Set the number of days from January to December and check the month When the number of days is reached, check the table directly. Then 0 is 0

Tip: Padding with leading zeros – use %02d

printf("%d-%02d-%02d\n",year,month,day);

🌡 Reference code (C++ version)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int days[ 13 ] = { 0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 }; //Set the number of days from January to December first, then 0 month is 0

//Core: A function that checks whether the input year meets the conditions 
bool  check_vails ( int year, int month, int day)
 {
     if (month == 0 || month > 13 ) return  false ;
     if (day == 0 ) return  false ;
     if (month != 2 ) // first deal with the case where it is not February
    {
        if(day > days[month]) return false;
    } else  // handle February
    {
        //Determine whether it is a normal year or a leap year. It is a normal year, leap is 0, is a leap year, leap is 1 
        int leap = year % 100 &&year % 4 == 0 || year % 400 == 0 ;
         if (day > 28 + leap) return  false ;
    }

    return true;
}

int main()
{
    int a,b,c;
    scanf("%d/%d/%d",&a,&b,&c);

    // enumerate all the dates it gives 
    for ( int date = 19600101 ; date<= 20591231 ; date++)
    {
        // Take out the year, month and day 
        int year = date / 10000 , month = date% 10000 / 100 , day = date % 100 ;
         // Judge whether it is legal 
        if (check_vails(year,month,day))
        {
            if (year % 100 == a && month == b && day == c || //year/month/day 
                month == a && day == b &&year % 100 == c || //month/day/ Year 
                day == a && month == b && year % 100 == c) //day/month/year 
                //output, here you can use 02 in the formatted output, which means zero-padded if there are less than two 
                digits printf ( "% d-%02d-%02d\n" ,year,month,day);
        }
    }
    return 0;
}

Feeling this question, it is more troublesome to judge the output in the end, because the three situations are very similar, it may feel unclear.

Increase the difficulty~ 😜

🌟 Chapter 5, the date of the palindrome of the 11th Blue Bridge Cup Provincial C++A\B group

In the provincial competition, I have passed a palindrome date question, but the difficulty is low and not representative. I found a more typical and general problem of dealing with time on the lovely acwing of y. Let’s focus on fighting it.
I put the reference code of the blue bridge question in the last link, and you can get it from gitee after clicking it 🌺🌺🌺

🌱 Topic description

original title portal

🌴 Problem solving report

This question has two ideas that are very important in processing time:

1. Multiply a number by itself by 10 + the one digit of the original data to turn a date into a palindrome date

date = date * 10 + tmp % 10;

2. Check whether a date is legal.
It includes taking out the year, month, and day of a date separately;
and how to use the form of a table to determine whether the number of days in a month meets the requirements, and the treatment of February in normal years and leap years

bool check_vaild(int date);

🌡 Reference code (C++ version)

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

//The core function for judging whether a date is legal 
bool  check_vaild ( int date)
 {
     //Remove the year, month, and day in the date ===> Remember the best, if you can't remember, just take the sample and simulate it 
    int year = date / 10000 ;
     int month = date % 10000 / 100 ;
     int day = date % 100 ;

    //Determine whether the month is legal 
    if (month < 0 || month > 13 ) return  false ;
     //Determine whether each day of the month is legal 
    //First deal with the non-February case 
    if (day == 0 || month ! = 2 && day> days[month]) return  false ;
     else
    {
        //Ask whether the current year is a normal year or a leap year 
        //Think about a special case, such as 2020, 1900 is not a leap year 
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0 ;
         if (day % 400 == 0 ; > days[month]+leap) return  false ;
    }
    return true;
}

int main()
{
    int date1,date2;
    cin >> date1 >>date2;

    //Enumerate the year, process the year into a palindrome while enumerating 
    //Then check whether the year is legal

    int res = 0;
    for(int i = 1000; i <= 9999;i++)
    {
        int date = i , tmp = i;
         // Process the current date as a palindrome 
        for ( int j = 0 ; j < 4 ;j++)
        {
            //Reassign the number after the palindrome to date 
            date = date * 10 + tmp % 10 ; //Put out the ones digit, and realize the palindrome splicing 
            tmp /= 10 by expanding the number of digits ;
        }

        //Determine whether this date is within the given range and whether it is legal, the statistical result 
        if (date1 <= date && date <= date2 && check_vaild(date)) res ++;
    }
    //output result 
    cout << res << endl ;
}

🌟 Chapter 6, flight time of the 9th Blue Bridge Cup Provincial C++ Group A

The question of flight time is mainly to introduce the idea of ​​calculating the time difference.
Calculating jet lag can be compared to a common practice in junior high school physics. How to deal with the problem of water speed when the boat is going downstream, and how to deal with the upstream.

🌱 Topic description

original title portal

🌴 Problem solving report

1. Navigation time under jet lag

Outbound departure time + flight time + jet difference = outbound landing time (formula 1)
return departure time + sailing time – jet difference = return landing time (formula 2)

Known: Outbound departure time, Return departure time, Outbound landing time, Return landing time

According to formula 1 + formula 2:
outbound departure time + return departure time + 2 * sailing time = outbound landing time + return landing time
Then : sailing time = (outbound landing time – outbound takeoff time + return landing time – return takeoff time)/2

2. Process strings into integer data

Step 1: Read the entire string in via the getline function.
Step 2: Input the time, minute and second information in the string into the integer variable for storage through sscanf, combined with the c_str method

Similar to scanf, sscanf is used for input, but the latter uses the keyboard (stdin) as the input source, and the former uses the fixed string as the input source.

If you don’t have this C++ API, you can download it from the link below

3. Take out the hours, minutes and seconds of the digitized time

int hour = myTime /3600,minute = myTime%3600/60,second = myTime % 60;

Also remember that when comparing the time, it is calculated as the number of seconds that are different from 0:00:00 of the current day.

4, broken thoughts

Some friends may think, God, I have to remember a lot~ Is this a learning algorithm? It feels like learning a language.
When I was studying in acwing, y always said something like this (can’t remember the original, damn it) ): All things with time constraints, such as exams, are not for us to create, but to recall what we have learned, and then by analogy to the current problem. Including learning is the same thing, we understand and remember the knowledge left by our predecessors.
My high school math teacher, I usually call him Brother Yang. He likes to complain that we don’t remember the type of questions. One thing he often says is that I clearly remember this question, and which year is the first question of the real question. If you don’t believe me, go and read it, if you don’t , I am running luo ben in the playground today. This may be the confidence of the members of the Chinese Mathematical Association~
So don’t be so resistant to memory~

🌡 Reference code (C++ version)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

//Completion function 
int  get_seconds ( int h, int m, int s)
 {
     return h * 3600 + m * 60 + s;
}

int  get_time ()
 {
     //Use getline to read the entire line of data 
     string line;
     getline(cin,line);

     int len = line.length();

     char ch = line[len -1 ];
     //Manually add (0) to the first day of departure on the day of arrival 
// if(line.back() != ')') line += " (+0 )"; 
      if (ch != ')' ) line += " (+0)" ;

    int h1,m1,s1,h2,m2,s2,d;
    sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
    return get_seconds(h2,m2,s2) - get_seconds(h1,m1,s1) + d * 24 * 3600;

}


int main()
{
    int n;
    scanf("%d",&n);
    string line;
    getline( cin ,line); //Ignore the carriage return on the first line

    while(n--)
    {
        int myTime = (get_time() + get_time()) / 2;
        int hour = myTime /3600,minute = myTime%3600/60,second = myTime % 60;
        printf("%02d:%02d:%02d\n",hour,minute,second);
    }
    return 0;
}

Finally, solve a relatively simple date and time problem in the national competition as a harmonious ending~

🌟Chapter 7, The 11th Blue Bridge Cup Final C++A Team

As with the number of days in each month, use the idea of ​​a clock.
Just need to pay attention to the details, this table, where to start playing.

🌱 Topic description

original title portal

🌴 Problem solving report

At first impression, this question should be a standard punching question.

When the friends feel that the question has a taste of query in the future, if it is a number type, you can approach the hash and binary;
if it is a character type such as this question, you can consider creating a table to observe the rules. Inquire directly~

The pit of this question:

Maybe some friends are excited when they see the national competition. When they see the sign-in questions that can be directly enumerated, they can enumerate directly from the beginning of “jia” and “yi”. As soon as the sample runs, ah, no~

Because of the specific arrangement of the ten heavenly stems and twelve earthly branches, is A, B, C, and Ding released first? It is still undecided whether Gengxin Rengui was released first , so it needs to be determined in combination with the cases 1900, 1960, and 2020 given in the title.

🌡 Reference code (C++ version)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int main()
{
    int year;
    cin >> year;

    //First simulate through 2020, 1900, and 1960. They can be rounded to a whole modulo 10. At this time, it is geng. Modulo 12 is the remainder 4, which is zi in this case. 
    //First enumerate the ten heavenly stems and twelve earthly branches, just like typing a table, and check the 
    string directly later s[ 10 ] = { "geng" , "xin" , "ren" , "gui" , "jia" , "yi" , "bing" , "ding" , "wu" , "ji" };

    string e[12] = {"shen","you","xu","hai","zi","chou","yin","mao","chen","si","wu","wei"};

    //Directly take the modulo to see which zodiac the current year is 
    cout << s[year % 10 ] << e[year% 12 ] << endl ;


}

Now my friends should be able to clearly feel it. In most cases, it is not difficult to enumerate, but there are really a lot of details.

Date and time type problem, come to an end~

🌟 Chapter 8, Results Analysis of the 11th Blue Bridge Cup Provincial C++A/B Group

Details about rounding

🌱 Topic description

original title portal

🌴 Problem solving report

Just obediently use the loop to traverse the input data, compare them one by one to find the maximum and minimum values, and count the sum at the same time, because the answer requires a two-digit decimal, and finally remember to convert the result to double type. It is recommended to convert all games to double, and float may sometimes cause deviations in the results due to precision problems.

Also wanted to mention the rounding thing:

If similar to this question, rounding with a few decimal places can be implemented directly using floating-point type.
If the set rounds 1.5 to 2, then after importing the header file, use the round function in C++

🌡 Reference code (C++ version)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
const int N = 10010,INF = 999999999;
int a[N];
int n,sum;

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n;i++) scanf("%d",&a[i]);

    int minv = INF,maxv = -INF;
     //Go and traverse these input data honestly, which is the so-called enumeration 
    for ( int i = 0 ; i < n; i++)
    {
        minv = min(a[i],minv);
        maxv = max(a[i],maxv);
        sum += a[i];
    }

    //Output 
    printf ( "%d\n%d\n%.2lf\n" ,maxv,minv,( double )sum/n);
     return  0 ;


}

🌟The ninth chapter, the priority of the takeaway shop in the C++A/C group of the 10th Blue Bridge Cup Provincial Competition

The idea of ​​dealing with discrete data

🌱 Topic description

original title portal

🌴 Problem solving report

The idea of ​​dealing with discrete data – because for a store, there may be orders for a period of time, and there may be no orders for a period of time.
So the data is discrete. The processing method can ignore the moment when there is no order in a row, and put it into processing after there is an order.

Problem solving idea:

This simulation problem is a bit complicated. If your friends have the habit of writing pseudo-code, you can be more comfortable when solving more complex simulation problems.

1. Sort all orders by time

2. Then enumerate each order from front to back

Pure brute force is to enumerate every moment, time complexity is O ( N 2 ) O(N^2) O ( N2 ), it will time out.
In the loop, the same batch of orders is processed each time (it can be understood that as long as this time point and the corresponding store Id are the same, they are regarded as a whole, and a batch of orders can be processed each time)

Suppose the current order is the ith i , use the loop to judge whether there arethe same orders(that is, at the same order time t t t , the number id id of the storeid is the same).
When the j jth When there are j orders, the orders are different, then the quantity of this batch of orders should be c n t = j βˆ’ i cnt= j – i cnt=jβˆ’i
lower order f o r for The for loop starts from j to process the next batch of orders

Record t and id at this time, and calculate the priority of id. There are two parts to be processed.

Part 1:
Calculate the priority, if it is negative at this time, then Reset priority to 0.
If the priority is less than or equal to 3, remove the store from the priority cache, that is: s t [ i d ] = f a l s e st[id] = false st[id]=false**

Part II:
t t Get the order at time t , and the quantity is c n t cnt c n t , the priority of this store is to add 2 βˆ— c n t 2*cnt 2βˆ—c n t .
Calculate the priority, if it is greater than 5, put it into the priority cache, that is: s t [ i d ] = t r u e st[id] = true st[id]=true;

Because the same order has already been processed, there is no need to calculate it again, and a new cycle starts at the position j, where the next batch of orders appears.

for(int i = 0; i < m;)
......
i = j;

Loop to the end, the last time the order was received last [ d ] last[id] l a s t [ i d ] is updated to t t t

3. Final processing

If the time of the last order is T, then it does not need to be processed.
If it is not T, then the subtraction of the priority deduction from the last order to the time T needs to be supplemented.
That is, subtract the difference between the last order moment and T. Because there is no order at time T, there is no need to reduce it by one.
Judging the priority, if it is less than or equal to 3, clear it out of the priority cache. Finally, traverse the priority cache, and the number obtained is the answer to the question

🌡 Reference code (C++ version)

#include <iostream>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
const int N = 100010;

int n,m,T;
 int score[N]; //indicates the priority of the i-th store 
int last[N]; //indicates the last time the i-th store had no orders 
bool st[N]; // Indicates whether the i-th store is currently in the priority cache

PII order[N];

int  main ()
 {
     scanf ( "%d%d%d" ,&n,&m,&T);
     //Because the order information is a two-tuple, so use pair to read a two-tuple 
    for ( int i = 0 ; i < m; i++) scanf ( "%d %d" ,&order[i].x,&order[i].y);

    //One-step sorting: pair has its own comparison function, which is performed according to the first keyword first. If the first keyword is the same, the second keyword is considered
    sort(order,order+m);

    // enumerate each order 
    for ( int i = 0 ; i < m;)
    {
        int j = i;
         //find m orders, the same order 
        while (j < m && order[j] == order[i]) j++;
         int t = order[i].x; //get order time 
        int id = order[i].y; //get order id 
        int cnt = ji; //get quantity

        i = j; //Assign j to i, process the next batch of orders

        score[id] -= t - last[id] - 1 ; //Deduct the priority when there is no order at time t 
        if (score[id] < 0 ) score[id] = 0 ; //If the priority The deduction is negative, reset to 0 
        if (score[id] <= 3 ) st[id] = false ; // pull this store out of the priority cache

        //The above is the information before time t

        score[id] += cnt * 2;
        if(score[id] >  5) st[id] = true;

        //Update last[id]
        last[id] = t;
    }

    //Enumerate each store 
    for ( int i = 1 ; i <= n;i++)
         if (last[i] < T) //If there is no order in the last period of time, deduct the corresponding
        {
            score[i] -= T - last[i];
            if(score[i] <= 3) st[i] = false;
        }

    int res = 0 ;
     //Finally count how many stores are in the priority cache 
    for ( int i = 1 ;i <= n;i++) res += st[i];

    //output result 
    printf ( "%d\n" ,res);
     return  0 ;


}

🌟 Chapter 10, 2021 Mock Irrigation

A variety of solutions, mainly want to introduce: a little trick to use offset to handle orientation + recursive review

🌱 Topic description

original title portal

🌴 Problem solving report


1. Analysis of topic samples

Set the position of the garden and the water pipe according to the position of the question, and simulate it, you can clearly know why there are 9 squares

2. Solve how to change the state of the four positions of up, down, left and right

The conventional way of playing may be to judge by four ifs. This is also possible, but it is a little more troublesome. So here is a way to solve it by using the offset.

int new_x = x + dx[i] , new_y = y + dy[i];

At this time, only four enumerations are required for the four directions of up, down, left, and right, and their coordinates are not obtained.
For example, if i is 2 now, then new_x = x + 1, new_y = y + 0. If x = 3, y = 3. Then the new coordinates are (4,3). Similarly, the coordinates of other locations can also be represented in this way.

If the topic becomes complicated, there are eight directions, which can also be expressed in a similar way.

Third, the enumeration of this topic

Then this question only needs to simply enumerate the garden of the initial situation. If there is a water pipe, enter the recursive d f s dfs df s function to irrigate the squares around it. Finally, traversing the number of squares that are irrigated is the answer.

The only thing to note is when using recursion, don’t forget to set the condition for the end of the recursion.

🌡 Reference code (C++ version)

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int g[N][N];
int re[N][N];
int n,m,k;
int dx[] = {-1,0,1,0} , dy[] = {0,-1,0,1};

//Complete dfs function 
void  dfs ( int x, int y, int lim)  //irrigated position, and current minute
 {
     //recursive boundary condition 
    if (lim >= k) return ;

    //Using offsets, enumerate four directions 
    for ( int i = 0 ; i < 4 ;i++)
    {
        int a = x + dx[i] , b = y + dy[i];
         //judgment boundary + update state 
        if ((a >= 1 && a <= n) && (b >= 1 && b <= m )) re[a][b] ++;
         // recurse to next position 
        dfs(a,b,lim+ 1 );
    }
}


int  main ()
 {
     cin >> n >> m;
     int t;
     cin >> t;
     //Enter the position of t water pipes 
    while (t--)
    {
        int a,b;
        cin >> a >> b;
        g[a][b] = 1;
        re[a][b] = 1 ; // used to record the results after irrigation
    }
    cin >>k;

    //Enumerate each location, find where there is a water pipe, and recurse in to process 
    for ( int i = 1 ; i <= n;i++)
    {
        for(int j = 1; j <= m;j++ )
            if(g[i][j] == 1) dfs(i,j,0);
    }

    int res = 0;
    for(int i = 1;i <= n;i++)
        for(int j = 1; j <= m;j++)
            {
                if(re[i][j] >= 1) res++;
            }

    cout << res << endl;
    return 0;
}

Seems like I haven’t played enough chapter eleven…

I haven’t found any simulation questions that are more bright and suitable for explanation. Let’s set 11 words. If I find a good real question in the future, I will add it~
The typesetting of one type and two type I recently I will also readjust it, including the entire column, I will always maintain, optimize and correct it🌹🌹🌹.

πŸ’“ Summary

The tour of Huajie comes to an end here, there are hard moments and relaxing moments~.
Make a short summary, simulated questions, and pay attention to details. In the question of time and date, pay attention to whether the date is legal, and whether the question of statistical quantity has less consideration equal to this situation. Accumulate a little more tricks and routines from time to time. I am very happy in the exam room~

Ready to set off for the forging knife village, unlock the new charcoal equipment – Mr. Yuanyi’s He knife

Leave a Comment

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