Luogu

P1138 the k-th integer

Title Description

There are n positive integers, and it is required to find the k-th 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 so-called 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* (5-2) + 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:

1. If you encounter a number, put it into a temporary array, so that you can find the number later
2. 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
3. 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!!!)
4. 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(y-x);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 n-1 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 M-1, 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. 1: Find word 1 and call it into memory.
2. 12: find word 2 and call it into memory.
3. 12: find word 1 in memory.
4. 125: find word 5 and call it into memory.
5. 254: find word 4 and call into memory to replace word 1.
6. 254: find word 4 in memory.
7. 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:

1. Given an integer x, please add x to the sequence.
2. The smallest number in the output sequence.
3. 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 A-B 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 A-B, 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 A-B=C into A-C=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;
}