The experiment in this section is mainly to integrate and run through the knowledge points we have learned before, and explain the actual combat through four real blue bridge cup questions, so as to lead you to apply what you have learned.
One of the best lectures on the real topic of the Blue Bridge Cup
Real question of 2020 Blue Bridge Cup - Q & A
Meaning:
have n Two students asked the teacher to answer questions at the same time. Each student has estimated the time of answering questions in advance.
The teacher can arrange the order of answering questions, and the students should enter the teacher's office to answer questions in turn. A student's Q & a process is as follows:
First enter the office, No i Students need si Milliseconds.
Then the students ask questions and the teacher answers them. The number is i Students need ai Milliseconds.
After answering the questions, the students are very happy and will send a message in the course group. The time needed can be ignored.
Finally, the students pack up and leave the office. They need to ei Milliseconds. It usually takes 10 seconds, 20 seconds or 30 seconds, i.e ei The value is 100020000 or 30000.
After one student leaves the office, the next student can enter the office.
Q & A starts from time 0. The teacher wants to reasonably arrange the order of Q & a so that the sum of messages sent by students in the course group is the smallest.
Input / output:
Enter description: The first line of input contains an integer n，Indicates the number of students. next n OK, describe each student's time. Among them i The row contains three integers si, ai, ei，The meaning is described above. Among them, 1≤n≤1000，1≤si≤60000，1≤ai≤106，ei∈10000,20000,30000. Namely ei It must be one of 10000, 20000, 30000. sample input : 3 10000 10000 10000 20000 50000 20000 30000 20000 30000 Output description: Output an integer indicating the minimum sum of the time when students send messages in the course group. sample output : 280000
Topic analysis
This question is a greedy question. In order to minimize the sum of all moments, we must make every moment as few as possible. According to the question, we can get the moment of each student = waiting time of each student + entrance time + question answering time.
Since the question answering time is known, to minimize the time of each student, it is necessary to minimize the waiting time of each student. How to minimize the waiting time?
If we think about this problem in this way, we can't do it. What we should consider is to minimize the waiting time and time of each student.
Every student's moment = Waiting time for each student + Entrance time + Office Hours
= Waiting time of the previous student + The entrance time of the previous student + Q & a time of the former student + The former classmate's time to pack up + Entrance time + Office Hours
Each student's waiting time + the time before answering questions can be the minimum, and we can use the first student's waiting time + the time after answering questions.
But if they are the same, what is the relationship between them?
- Because the message is sent after the Q & A, rather than after going out, there is a relationship between the two. Whoever answers the Q & a first will execute it first.
- We need to further consider that if the entry time + Q & a time are the same, that is, the Q & A ends at the same time. Since the Q & A ends at the same time, the result of who comes first is the same, so we don't need to continue to consider. Here, the greedy strategy is completely generated.
That is, we choose the person with the smallest sum of the minimum entry time + Q & a time + packing time, and when the sum of the entry time + Q & a time + packing time is the same, we choose the minimum entry time + Q & a time.
code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
struct Stu
{
int inD;
//Time required to enter the door
int answQ;
//Time required for answering questions
int outD;
//Time required to pack up
int sum1;
//Greedy criterion 1 = entry time + Q & a time + packing time
int sum2;
//Greedy criterion 2 = entry time + Q & a time + packing time
} stu[N];
//greedy criterion
bool cmp(Stu st1, Stu st2)
{
if(st1.sum1 != st2.sum1) return st1.sum1 < st2.sum1;
else return st1.sum2 < st2.sum2;
}
int main()
{
//input data
scanf("%d", &n);
for(int i = 0; i < n; i ++ )
{
scanf("%d%d%d", &stu[i].inD, &stu[i].answQ, &stu[i].outD);
//Standard generation
stu[i].sum1= stu[i].inD + stu[i].answQ+stu[i].outD;
stu[i].sum2 = stu[i].inD + stu[i].answQ;
}
//Greedy process and result calculation
sort(stu, stu + n, cmp);
long long res = 0, t = 0;
for(int i = 0; i < n; i ++ )
{
t += stu[i].sum2;
res += t;
t += stu[i].outD;
}
cout << res << endl;
return 0;
}
Real title of 2012 Blue Bridge Cup provincial competition - Lucas queue
This problem is a simulation problem based on prefix and. We can simulate it as required.
Meaning:
This question is a blank filling question. You only need to calculate the result and use the output statement in the code to output the filled result. Golden section number 0.618 It has an important relationship with aesthetics. The position where the announcer stands on the stage is about 0.5 of the width of the stage.618 At the same time, the portraits on the wall are generally hung at 0.5 of the height of the room.618 Even stock fluctuations are said to find 0.618 Shadow of.... The golden section number is an irrational number, that is, it cannot be expressed as the ratio of two integers. 0.618 Only its approximate value. Its true value can be obtained by subtracting 1 from the square of 5 and dividing by 2. We take a more accurate approximate value: 0.618034 . Interestingly, some simple sequences also contain this irrational number, which shocked mathematicians! 1 3 4 7 11 18 29 47.... It's called the Lucas queue. Each item after it is the sum of the first two items. If the ratio of the two items is observed, i.e. 1\3 3\4 4\7 7\11 11\18...You will find it closer and closer to the golden section number! Your task is to figure out which item to start with, and the ratio has reached and 0 after rounding.618034 Consistent accuracy. Please write the ratio. The format is: molecule/denominator. For example: 29/47.
Enter description: nothing sample input : nothing
Output description: Output an integer representing the ratio. The format is: molecule/denominator. For example: 29/4729/4729/47. sample output : nothing
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
double a[51] = { 1,3 };
void init()
{
for (int i = 2; i < 50; i++)
{
a[i] = a[i - 1] + a[i - 2];
}
}
string comp()
{
for (int i = 0; i < 50; i++)
{
double b = a[i] / a[i + 1];
if (abs(b - 0.618034) <= 0.000001)
{
stringstream s1;
s1 << a[i] << "/" << a[i + 1];
string s;
s1>>s;
return s;
}
}
}
int main()
{
init();
string ans=comp();
cout<<ans<<endl;
return 0;
}
stringstream class:
The C + + code description given here will be relatively cumbersome. The purpose is to tell you a new string usage skill. C++ stringstream class is a very useful class, especially when we need to use string and digital data to convert each other in the program.
To use the stringstream class in the program, we need to include the header file include in the source program file.
The use method of stringstream object is basically the same as that of cout object and cin. > > This symbol is very vivid, for example:
CIN > > a can be understood as flowing data into a
Cout < < a flows data into cout. In the final analysis, it is data flow
The description of the underlying layer may not be appropriate, but remember that > > to whom you point is to whom you give the data. Stringstream can be used as cin cout. In the code I gave above, you can see that I also transformed the data. It is also a good choice to use stringstream for data type transformation in C + +.
2015 Blue Bridge Cup simulation real topic - gold coins
This problem is a variant of prefix and. The variant method can be solved by simulation. The time complexity is O(N2), but the scope of the problem is 1e4, and the method of no timeout is feasible.
Meaning:
The king paid the loyal knights with gold coins as wages. On the first day, the knight received a gold coin; Two gold coins were received every day for the next two days (the second and third days); In the next three days (the fourth, fifth and sixth days), three gold coins were received every day; In the next four days (the seventh, eighth, ninth and tenth days), four gold coins were received every day......； This wage payment model will continue like this: when continuous N Received every day N After a gold coin, the knight will be in a row N+1 Days, every day N+1 A gold coin. Please count first K How many gold coins did the knight get in one day.
Enter description: The input has only 1 line and contains a positive integer K (1≤K≤104)，Indicates the number of days to issue gold coins. sample input : 6
Output description: The output has only one line and contains a positive integer, that is, the number of gold coins received by the knight. sample output : 1000
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
int comp(int n)
{
int sum = 0;
int day = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
sum += i;
day += 1;
if (day == n)
return sum;
}
}
return sum;
}
int main()
{
int n;
cin>>n;
int ans=comp(n);
cout<<ans;
}
Maximize the profit of stock trading
The way to maximize the profit of this topic is to have a and B for two days. A is the day before B, making the value of B-A the largest.
Meaning:
Implement an algorithm to find the strategy to maximize the profit of stock trading. The introduction is as follows: - The stock price changes every day. The index of the array represents the trading day, and the element of the array represents the stock price every day. - You can make a profit by buying and selling. You can only buy or sell once a day. One buy plus sell operation is called one transaction. - You can only trade once and seek a trading strategy that maximizes profits.
Enter description: First line number N，Indicates common ownership N Oh, my God. Second behavior N Number Ai，Represents the daily stock price. Of which, 1≤N,Ai≤1e4. sample input : 8 2 5 6 1 4 3 1 3
Output description: Output one line, which is the maximum profit of one transaction (the profit may be negative). sample output : 4
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a[100005];
int n;
cin>>n;
int mini=-0x3f3f3f3f;//A commonly used minimum
for(int i=0; i<n; i++)
{
cin>>a[i];
}
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
int t=a[j]-a[i];
if(mini<t)
{
mini=t;
}
}
}
cout<<mini;
return 0;
}
The second part of the true topic of the Blue Bridge Cup
Real topic of 2021 Blue Bridge Cup simulation - negotiation
Meaning:
Title Description A long time ago, there was n Tribes live on the plain, numbered 1 to n. The first i The number of tribes is ti. One year there was a famine. The young politician Xiao Lan wants to persuade all tribes to deal with the famine together. He can persuade the tribes to unite through negotiation. Xiaolan can only invite two tribes to participate in each negotiation. The amount of gold coins spent is the sum of the number of the two tribes. The effect of the negotiation is that the two tribes unite into one tribe (the number is the sum of the number of the original two tribes).
The first line of input contains an integer nnn，Indicates the number of tribes. The second line contains nnn A positive integer representing the number of people in each tribe in turn. Of which, 1≤n≤1000，1≤ti≤1e4.
Output an integer indicating the minimum cost.
Example 1 input 4 9 1 3 5 output 31
This problem is a greedy problem. In order to minimize the sum of expenses, it is necessary to minimize the expenses every time.
According to the title, we can get that the cost of the new tribe = the number of people is the sum of the numbers of the original two tribes.
How to minimize the waiting time?
If you think about this problem in this way, you can't do it. What should be considered is to minimize the waiting time and time of each student. Let's recall the question:
Waiting time of the first student S1=T1=0 -----(1) Waiting time of the second student S2=T1+T2=T2 -----(2) Waiting time of the third student S3=T1+T2+T3=T2+T3 -----(3) ...... The first N Waiting time of students Sn=T1+T2+T3+T4+T5+...+Tn-1 -----(n) Add 1 to n-1 Type bring in n Formula Sn=T1*n+T2\*(n-1)+T3\*(n-1)+....+Tn It can be seen that the front coefficient is the largest, so the front time should be minimized. So the greedy strategy is obtained to solve the problem. At this time, the greedy conclusion is the waiting time of each student(Waiting time of the previous student+The entrance time of the previous student+Office Hours +The former classmate's time to pack up)minimum.
A set of examples:
4 3 4 5 6 If combined in order: 3+4=7 7 5 6 7+5=14 14 6 14+6=20 Final cost: 7+14+20=41 In fact, the answer should be: 3 4 5 6 3+4=7 7 5 6 Sort again 5 6 7 5+6=11 11 7 11+7=18 The final cost is 7+11+18=36
Therefore, the greedy principle here is to maintain the minimum value, but it will be updated every time. After each update, it will be reordered. The time complexity is Nlog(n), which can be passed here. Of course, we can also use priority queue to solve problems.
Priority queues are as like as two peas, and priority queues will automatically sort them.
An ordinary queue is a first in first out data structure. Elements are added at the end of the queue and deleted from the queue head. In the priority queue, elements are given priority. When accessing an element, the element with the highest priority is deleted first. Priority queues have the behavioral characteristics of first in, largest out. It is usually implemented by heap data structure.
Simple multiple sorting:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
int cnt=0,k;
vector<int> t;
for(int i=0; i<n; i++)
{
cin>>k;
t.push_back(k);
}
while(t.size()>1)
{
//sort
sort(t.begin(),t.end());
//Take out the first two values
int k=t[0]+t[1];
//Answer summation
cnt+=k;
//Delete the first two used values
t.erase(t.begin());
t.erase(t.begin());
//Adds the resulting new value to the collection
t.push_back(k);
}
cout<<cnt<<endl;
return 0;
}
Priority queue method:
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n,cnt=0;
priority_queue<int>pq; //The default is large top heap, sorted from large to small
cin>>n;
for(int i=0; i<n; ++i)
{
int a;
cin>>a;
pq.push(-a); //Save negative value, sort from small to large
}
if(pq.size()==1)
{
cout<<-pq.top();
}
else
{
while(pq.size()!=1)
{
int x=pq.top();
pq.pop();
int y=pq.top();
pq.pop();
pq.push(x+y);
cnt+=-x-y;
}
cout<<cnt<<endl;
}
return 0;
}
Priority queue
First of all, the header file #include should be included. The difference between it and queue is that we can customize the priority of the data in it, so that the one with higher priority will be in front of the queue and out of the queue first.
Priority queue has all the characteristics of queue, including the basic operation of queue. On this basis, an internal sort is added. Its essence is a heap implementation.
Real topic of 2008 NOIP popularization group - row seats
Meaning:
In class, there are always some students whispering with people around, which is a headache for the head teacher of primary school. However, the head teacher Xiaoxue found some interesting phenomena. When the seats of the students were determined, there were only limited opportunities D They will whisper to their classmates in class. The students sat in the classroom M that 's ok N Column, sit on the second floor i Line number j The position of the students in the column is( i，j)，In order to make it convenient for students to get in and out of the classroom K A transverse passage, L A longitudinal passage. Therefore, smart Xiaoxue thought of a way to reduce the problem of students' whispering in class: she planned to rearrange the tables and chairs and change the position of the channel between the tables and chairs, because if a channel separates two students who will whisper, then they won't whisper. Please help write a program for Xiaoxue and give the best channel division scheme. Under this scheme, the number of students whispering in class is the least.
Input:
Enter the first line with 5 integers separated by spaces, which are M，N，K，L，D(2≤N，M≤1000，0≤K<M，0≤L<N，D≤2000). next D Row, each row has 4 integers separated by spaces, the second row i 4 integers of the row Xi，Yi，Pi，Qi，Indicates sitting position (Xi,Yi)And (Pi,Qi) The two students will whisper to each other (input to ensure that they are adjacent front and rear or left and right). The input data guarantees the uniqueness of the optimal scheme.
Output:
There are two lines of output. Include first line K An integer, a1,a2,⋯aK，Represents the second a1a_1a1 Line sum a1+1a_1+1a1+1 Between lines, second a2 Line and page a2+1 Between lines aK Line and page aK+1 A channel shall be opened between rows, in which ai<ai+1，Every two integers are separated by spaces (no spaces at the end of the line). The second line contains L An integer, b1,b2,⋯bk，Represents the second b1 Column sum b1+1 Between columns b2 Liehedi b2+1 Between columns bL Liehedi bL+1 A channel shall be opened between columns, where bi<bi+1，Every two integers are separated by spaces (no spaces at the end of the line).
Example 1 input 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 output 2 2 4
Therefore, when outputting the channels to be divided, the channels should be sorted by number from small to large before outputting.
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN= 1001;
int x[MAXN]; //Abscissa bucket
int y[MAXN]; //Ordinate bucket
int c[MAXN];
int o[MAXN];
int main()
{
int M, N, K, L, D;
cin >> M >> N >> K >> L >> D;
int xi, yi, pi, qi;
while (D--)
{
cin >> xi >> yi >> pi >> qi;
if (xi == pi) //Same abscissa
{
y[min(yi, qi)]++;
}
else //Same ordinate
{
x[min(xi, pi)]++;
}
}
//Double cycle to find the abscissa value of the first K
for (int i = 1; i <= K; i++)
{
int maxn = -1;
int p;
for (int j = 1; j < M; j++)
{
if (x[j]>maxn)
{
maxn = x[j];
p = j;
}
}
x[p] = 0;
c[p]++;
}
//Double cycle to find out the abscissa value of the first L
for (int i = 1; i <= L; i++)
{
int maxn = -1;
int p;
for (int j = 1; j < N; j++)
{
if (y[j]>maxn)
{
maxn = y[j];
p = j;
}
}
y[p] = 0;
o[p]++;
}
for (int i = 0; i<MAXN; i++)
{
if (c[i])
printf("%d ", i);
}
printf("\n");
for (int i = 0; i<MAXN; i++)
{
if (o[i])
printf("%d ", i);
}
return 0;
}
Summary:
It can be seen that in the real competition, it is common to mix questions with all kinds of knowledge like this. A single knowledge point is called a check-in question, which is what everyone will do. Of course, in the provincial competition of the Blue Bridge Cup, you can learn the previous knowledge well. There is no problem in the second province. If you want to impact higher awards, the basic chapter just lays a good foundation. The later courses will take you to know more algorithms and experience the beauty of algorithms.
Original website: https://www.lanqiao.cn/courses/3993/learning/?id=248906