Happy New Year! The first blog in 2022 is mainly because I don't like summarizing, so I need to read more and summarize more. Then it's today's review!
1.vector
vector<int>a;
a.push_back();
a.pop_back();
a.insert(a.begin() + i, k);//Insert from position i
for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
cout << *i << endl;
}//Printing a vector requires iterations
//I didn't even knowP3156 [Shenji 15. Example 1] ask for student number
Title Description
There are n(n \le 2 \times 10^6)n(n ≤ 2 × 106 students entered the classroom one after another. We know that the student number of each student (between 1 and 10 ^ 9109) is given in the order of entering the classroom. After class, the teacher wants to know the student number of the second student entering the classroom (the first student entering the classroom i=1i=1), and the number of inquiries shall not exceed 10 ^ 5105 times.
Input format
The first line contains two integers n and m, which represent the number of students and the number of inquiries.
n integers in the second line represent the student numbers entering the classroom in order.
The third line is m integers, which means to ask the first student to enter the classroom.
Output format
m integers represent the answer, separated by a newline.
Sample input and output
Enter #1 copy
10 3 1 9 2 60 8 17 11 4 5 14 1 5 9
Output #1 copy
1 8 5
A very simple topic, the input element can be pressed into the vector and output
#include <iostream>
#include <vector>
using namespace std;
vector<int>vec;
int main()
{
int n, m;
int t;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> t;
vec.push_back(t);
}
for (int i = 1; i <= m; i++) {
cin >> t;
cout << vec[t-1] << endl;
}
}2.stack
First in and last out: the basic operations are also routine operations. This is relatively familiar, so just look at the examples.
P1241 bracket sequence
Title Description
Define the following rule sequence (string):
1. An empty sequence is a regular sequence;
2. If s is a regular sequence, then (S) and [S] are also regular sequences;
3. If both A and B are regular sequences, AB is also A regular sequence.
For example, the following strings are regular sequences:
()，[]，(())，([])，()[]，()[()]
The following are not:
(，[，]，)(，())，([()
Now, I'll give you some sequences composed of '(', ')', '[', ']'. What you need to do is to complete the sequence of parentheses, that is, scan the original sequence, and for each right parenthesis, find the matching left parenthesis closest to it on its left, and give up if it doesn't. After matching the original sequence in this way, complete the remaining unmatched parentheses.
Input format
The input file has only one line, which is composed of '(', ')', '[', ']', without other characters, and the length is no more than 100.
Output format
The output file also has only one line, all of which are composed of '(', ')', '[', ']', without other characters. You can output the completed rule sequence.
Sample input and output
Enter #1 copy
([()
Output #1 copy
()[]()
Description / tips
Complete the first two left parentheses.
#include <iostream>
#include <stack>
using namespace std;
stack<int>v;
string s, b;
int main()
{
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
b[i] = ')';
v.push(i);
}
if (s[i] == '[') {
b[i] = ']';
v.push(i);//Push the marked i onto the stack
}
if (s[i] == ')' || s[i] == ']') {
if (v.empty() || b[v.top()] != s[i]) {
if (s[i] == ')') {
b[i] = '(';
}
else {
b[i] = '[';
}
}
else {//If they are equal, they will be converted to '' in the b array, and then the top of the stack will be deleted
b[v.top()] = ' '; v.pop();
}
}
}
for (int i = 0; i < s.size(); i++) {
if (b[i] == '(' || b[i] == '[') {
cout << b[i];
}
cout << s[i];//Output original sequence
if (b[i] == ')' || b[i] == ']') {
cout << b[i];
}
}
}3.queue
First in first out (I'm good at it, so please look at the example)
P2058 [NOIP2016 popularization group] seaport
Title Description
Xiaok is a customs officer in a seaport. Many ships arrive at the seaport every day. There are usually many passengers from different countries on board.
Xiao K is very interested in these ships that arrive at the harbor. He records every ship that arrives at the harbor according to the time; For the ith arriving ship, he recorded the arrival time ti (unit: Second) and the number of passengers on board k_iki, and the nationality of each passenger {x_{i,1}, x_{i,2},…,x_{i,k}xi,1,xi,2,…,xi,k.
Xiaok has counted the information of nn ships. I hope you can help calculate how many different countries all passengers arriving by ship come from within 2424 hours (2424 hours = 8640086400 seconds) until the arrival time of each ship.
Formally, you need to calculate nn pieces of information. For the second piece of information output, you need to make statistics to meet t_ i-86400<t_ p \le t_ Ship pp with ITI − 86400 < TP ≤ ti, in all x_ How many different numbers are there in {P, J} XP, J}.
Input format
In the first line, enter a positive integer nn, indicating that small K counts the information of nn ships.
Next nn lines, each line describes the information of a ship: the first two integers t_iti and k_iki ， respectively represents the time when the ship arrives at the harbor and the number of passengers on board, and then k_iki# integer x_{i,j}xi,j} indicates the nationality of the passengers on board.
Guaranteed input t_iti is incremented in seconds; It means that the timing starts from the first work of xiaok, and the ship is at t_iti # seconds to the harbor.
Ensure that 1 \le n \le 10^51 ≤ n ≤ 105, \ sum{k_i} \le 3*10^5 ∑ ki ≤ 3 * 105, 1\le x_{i,j} \le 10^51≤xi,j≤105， 1 \le t_{i-1}\le t_i \le 10^91≤ti−1≤ti≤109.
Where \ sum{k_i}Σki represents all k_ The sum of IKI.
Output format
Output line nn, and an integer in line ii represents the statistical information after the arrival of ship ii.
Sample input and output
Enter #1 copy
3 1 4 4 1 2 2 2 2 2 3 10 1 3
Output #1 copy
3 4 4
Enter #2 copy
4 1 4 1 2 2 3 3 2 2 3 86401 2 3 4 86402 1 5
Output #2 copy
3 3 3 4
#include <iostream>
#include <queue>
using namespace std;
struct node {
int t;
int x;
};
queue<node>v;
int n, m, t, b;
int ans = 0;
int a[1001000];//The array needs to be larger
node k;
int main()
{
cin >> n;
while (n--) {
cin >> t >> m;
while (!v.empty()) {
k = v.front();//Take the head of the line
if (k.t + 86400 <= t) {
a[k.x]--;
if (a[k.x] == 0) {
ans--;//Persons without the nationality of that country, persons with the nationality of that country - 1
}
v.pop();
continue;//Skip this cycle and enter the next cycle
}
break;
}
for (int i = 1; i <= m; i++) {
cin >> b;
k.t = t; k.x = b;
v.push(k);
a[k.x]++;//The number of occurrences of this number is increased by 1
if (a[k.x] == 1) {
ans++;
}
}
cout << ans << endl;
}
}4.dueue
5.priority_queue
6.list / / linked list
push_back(x);//Add an element at the end of the container pop_back();//Delete the last element in the container push_front(x);//Insert an element at the beginning of the container pop_front();//Remove the first element from the beginning of the container insert(a,b);//Insert a copy of element b in position a and return the location of the new data. clear();//Remove all data from the container erase(begin,end);//Delete the data in the [begin,end) interval and return the position of the next data. erase(a);//Delete the data at position a and return to the position of the next data. remove(a);//Delete all elements in the container that match the a value.
7.set(multiset)
8.map(multimap)
9.algorithm / / header file
max(); min(); abs(); swap(a,b) reverse(a.begin(),a.end())//Flip function sort(a,b,cmp) unique()//De duplication function, used after sort find(x)//If there is x, return the position of X; if not, return the subscript of n+1 upper_bound(x);//Returns the position of the first subscript greater than x lower_bound(x);//Returns the first position greater than or equal to the x subscript fill();//Function in filled interval count(a,a+n,b);//Calculate the number of b in the interval __gcd(a,b)//Find the greatest common factor next_permutation(a,a+n)//Full arrangement nth_element(a.begin(),a.begin()+2,a.end())//Put the number with the original position of 2 on the second largest position to ensure that the number in front is less than this number and the number behind is greater than this number.
Today's review is over, and the linear table Luogu is over immediately. I'm so happy. In the future, I should also convert knowledge into systematic knowledge, so that I can apply it more flexibly in the subject, make progress slowly, understand slowly, come on, I wish you a happy New Year!!! Zhong Yimiao continued to make progress in the new year.
Review greed and order tomorrow!