Luogu
P1138 the kth integer
Title Description
There are n positive integers, and it is required to find the kth smallest integer among the n positive integers (integers of the same size are calculated only once).
Input format
The first behavior is n and k; The second line starts with the value of n positive integers separated by spaces.
Output format
The value of the k th smallest integer; If there is no solution, NO RESULT is output.
sample input
10 3 1 3 3 7 2 5 1 2 4 6
sample output
10 3 1 3 3 7 2 5 1 2 4 6
Description / tips
n ≤ 10000, k \leq 1000k ≤ 1000, positive integers are less than 3000030000.
code
This problem is automatically reordered with set set, and then iterated.
#include <bits/stdc++.h> using namespace std; int a,i, n,k,m; set<int>Q; set<int>::iterator it; int main() { scanf("%d%d",&n,&k); for (i = 1; i <= n; i++) scanf("%d", &a),Q.insert(a); if(Q.size()<k) cout<<"NO RESULT"; else{ it=Q.upper_bound(0); for(i=1;i<k;i++) it++; cout<<*it; } return 0; }
P1449 suffix expression
Title Description
The socalled suffix expression refers to an expression in which parentheses are no longer referenced, and the operation symbols are placed after the two operation objects. All calculations are strictly new from left to right according to the order in which the operation symbols appear (regardless of the priority of the operator).
For example, the suffix expression corresponding to 3* (52) + 7 is: 3.5.2.*7.+@. In this formula, @ is the ending symbol of the expression Is the end symbol of the operand.
Input format
Enter a string s on a line to represent the suffix expression.
Output format
Output an integer representing the value of the expression.
sample input
3.5.2.*7.+@
sample output
16
Description / tips
Data guarantee: 1 ≤ ∣ s ∣ ≤ 50, and the absolute value of each value in the answer and calculation process does not exceed 10^9.
code
This question is a naked question using stack
Idea:
 If you encounter a number, put it into a temporary array, so that you can find the number later
 If you encounter '.', Then convert the strings in the temporary array into numbers (see the program notes for specific operations) and push them into the number stack
 If you encounter an operation symbol, take out the two elements at the top of the stack and do the corresponding operation (Note: if you encounter  'or' / ', you should subtract or divide the second element at the top of the stack by the element at the top of the stack!!!)
 Finally, output the last remaining element in the digital stack
Children's shoes who want to copy the code can skip this part):
#include <bits/stdc++.h> using namespace std; stack<int> m; char ch; int ans; int main() { while(ch!='@') { ch=getchar(); if(ch=='+'ch==''ch=='*'ch=='/'){ int x=m.top();m.pop();int y=m.top();m.pop(); switch(ch) { case '+':m.push(x+y);break; case '':m.push(yx);break; case '*':m.push(x*y);break; case '/':m.push(y/x);break; } } else{ if(ch=='.'){ m.push(ans);ans=0; } else{ ans=ans*10+ch'0'; } } } printf("%d\n",m.top()); return 0; }
P1996 Joseph problem
Title Description
n people form a circle, start counting from the first person, count to m people out of the line, and then the next person starts counting again from 1, count to m people out of the circle, and so on, until all people are out of the circle, please output the number of people who are out of the circle in turn.
Note: the expression of this question is slightly different from that of the example in "simple in depth  Basic chapter". The statement in the book is to eliminate n1 children, and the question is to circle all.
Input format
Enter two integers n,m.
Output format
Output a line of n integers, and output the number of each person in turn.
sample input
10 3
sample output
3 6 9 2 7 1 8 5 10 4
Description / tips
1≤m,n≤100
code
Idea:
This problem is a simulation problem. First, we need to simulate a queue and press all elements into the queue
In the loop (until the queue is empty), first you need to know:
1. The queue can only be deleted in the head, which requires us to put this person at the end of the queue as long as he has been judged and will not be eliminated;
2. If this person happens to be eliminated, output him first, and then kick him out.
#include <bits/stdc++.h> using namespace std; queue <int> Q; int n,m,s=0; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) Q.push(i); while(!Q.empty()) { s++; if(s==m){ s=0; cout<<Q.front()<<' '; Q.pop(); } else{ Q.push(Q.front()); Q.pop(); } } return 0; }
P1540 [NOIP2010 improvement group] machine translation
Title Description
Xiao Chen has installed a machine translation software on his computer, which he often uses to translate English articles.
The principle of this translation software is very simple. It just replaces each English word with the corresponding Chinese meaning from beginning to end. For each English word, the software will first find the Chinese meaning of the word in the memory. If there is one in the memory, the software will use it to translate; If it is not in the memory, the software will search in the dictionary in the external memory, find out the Chinese meaning of the word, and then translate it, and put the word and the translated meaning into the memory for subsequent search and translation.
Suppose there are m units in the memory, and each unit can store a word and translation. Whenever the software stores a new word in memory, if the number of words stored in the current memory does not exceed M1, the software will store the new word in an unused memory unit; If M words have been stored in the memory, the software will empty the word that entered the memory first, vacate the unit and store the new word.
Suppose an English article is N words long. Given this article to be translated, how many times does the translation software need to look up the dictionary in external memory? Assume that there are no words in memory before the translation starts.
Input format
There are 2 lines in total. Two numbers in each line are separated by a space.
The first line is two positive integers M,N represents the memory capacity and the length of the article.
The second line is N non negative integers. According to the order of the article, each number (no more than 1000) represents an English word. Two words in the article are the same word if and only if their corresponding non negative integers are the same.
Output format
An integer, which is the number of times the software needs to look up the dictionary.
sample input
3 7 1 2 1 5 4 4 1
sample output
5
Description / tips
Example explanation
The whole process of looking up the dictionary is as follows: each line represents the translation of a word, and the memory condition after this translation is before the colon:
 1: Find word 1 and call it into memory.
 12: find word 2 and call it into memory.
 12: find word 1 in memory.
 125: find word 5 and call it into memory.
 254: find word 4 and call into memory to replace word 1.
 254: find word 4 in memory.
 541: find word 1 and call into memory to replace word 2.
I checked the dictionary five times in total.
 For 10% of the data, M=1, N ≤ 5;
 For 100\%100% data, there are ≤ M ≤ 100, 1 ≤ N ≤ 1000.
code
Idea:
Relatively simple simulation.
Seeing the statement "empty the word that entered the memory first", I thought of the first in first out queue.
So everything becomes very easy.
#include <bits/stdc++.h> using namespace std; int main() { int m,n,word,t=0,a[1001]={0}; queue<int>q; cin>>m>>n; for(int i=1;i<=n;i++) { cin>>word; if(!a[word]) { q.push(word); a[word]=1; t++; } if(q.size()>m) { a[q.front()]=0; q.pop(); } } cout<<t; return 0; }
P5740 [deep foundation 7. Example 9] the best student
Title Description
At present, N students have participated in the final exam and obtained the information of each student: name (a string of no more than 8 characters with only English lowercase letters), Chinese, mathematics and English grades (all natural numbers of no more than 150). The student with the highest total score is the best. Please output the information of the best student (name, grades of each subject). If there are multiple students with the same total score, the one with the highest output.
Input format
On the first line, enter a positive integer N, indicating the number of students.
The second line starts with the next N lines. For each line, first enter a string to represent the student's name, and then enter three natural numbers to represent the grades of Chinese, mathematics and English. Are separated by spaces.
Output format
Output the best students.
sample input
3 senpai 114 51 4 lxl 114 10 23 fafa 51 42 60
sample output
senpai 114 51 4
Description / tips
Data guarantee: 1 ≤ N ≤ 1000, the name is a string with a length of no more than 8, and the grades of Chinese, mathematics and English are natural numbers with a length of no more than 150.
code
Idea:
You can quickly sort the structure through the priority queue and output it directly.
#include <bits/stdc++.h> using namespace std; int n,i; struct node{ string f; int a,b,c; friend bool operator < (node x,node y) { return (x.a+x.b+x.c)<(y.a+y.b+y.c); } }k; int main() { priority_queue<node>Q; scanf("%d",&n); for (i = 1; i <= n; i++){ cin>>k.f>>k.a>>k.b>>k.c; Q.push(k); } cout<<Q.top().f<<' '<<Q.top().a<<' '<<Q.top().b<<' '<<Q.top().c; return 0; }
P3378 [template] stack
Title Description
Given a sequence, the initial value is empty. Please support the following three operations:
 Given an integer x, please add x to the sequence.
 The smallest number in the output sequence.
 Delete the smallest number in the number series (if there are multiple numbers with the smallest number, only one will be deleted).
Input format
The first line is an integer indicating the number of operations n.
Next, n lines, each representing an operation. Each line begins with an integer op indicating the operation type.
 If op = 1, there is an integer x after it, indicating that x is to be added to the sequence.
 If op = 2, it means that the minimum number in the sequence is required to be output.
 If op = 3, it means to delete the minimum number in the series. If there are more than one with the smallest number, only one will be deleted.
Output format
For each operation 2, an integer on a line is output to represent the answer.
sample input
5 1 2 1 5 2 3 2
sample output
2 5
Description / tips
 For 30% of the data, ensure that n ≤ 15.
 For 70% of the data, ensure that n ≤ 10^4.
 For 100% data, ensure 1 ≤ n ≤ 10^6, 1 ≤ x<2^31, op ∈ {1,2,3}.
code
Idea:
You can quickly sort the input and output through the priority queue.
#include<bits/stdc++.h> using namespace std; int a,b,i, n; priority_queue< int, vector< int >, greater< int > >q; int main() { scanf("%d", &n); for (i = 1; i <= n; i++){ scanf("%d", &b); switch(b) { case 1:scanf("%d", &a);q.push(a);break; case 2:cout<<q.top()<<endl;break; case 3:q.pop();break; } } return 0; }
P1102 AB data pair
Title Description
It's a painful thing to set a question!
Seeing too many of the same topics will also lead to aesthetic fatigue, so I abandoned the familiar A+B Problem and switched to AB, haha!
Well, the topic is like this: given a string of numbers and a number C, it is required to calculate the number of all number pairs of A  B = C (the same number pairs in different positions calculate different number pairs).
Input format
There are two lines of input.
The first line, two integers N, C.
The second line, N integers, is the string number required to be processed.
Output format
One line represents the number of number pairs satisfying A − B=C contained in the string number.
sample input
4 1 1 1 2 3
sample output
3
Description / tips

For 75% of the data, 1 ≤ N ≤ 2000.
For 100% data, 1 ≤ N ≤ 2 × 10^5.
Ensure that the absolute value of all input data is less than 2^30 and C ≥ 1.
Two new data groups were added on April 29, 2017
code
Idea:
This problem converts AB=C into AC=B. First, count the number of occurrences of each element of array A and map it. Finally, subtract one C from array a each time, and then scan array a again. The answer is to sum up the number of mappings. (pay attention to long long)
#include<bits/stdc++.h> using namespace std; long long ans=0,n,c,a[200001]; map<long long,long long>m; int main() { scanf("%d%d", &n,&c); for (int i=1;i<=n;i++){ scanf("%d", &a[i]); m[a[i]]++; a[i]=c; } for(int i=1;i<=n;i++) ans+=m[a[i]]; cout<<ans; return 0; }