当前位置：网站首页>The sixth day of the third question of daily Luogu

P1177 【 Templates 】 Quick sort
Title Description
Use the quick sort algorithm to read in NN The number is sorted from small to large and then output .
Quick sort is one of the necessary algorithms in information science competition . For students who don't know much about quick sort, they can query relevant information on the Internet by themselves , Complete independently after mastering .（C++ Please don't try to use STL, Although you can use sort Over and over again , But you haven't mastered the essence of the quick sort algorithm .）
Input format
The first 11 Act as a positive integer NN, The first 22 Line inclusion NN Positive integers separated by spaces a_iai, For the number you need to sort , The data guarantees A_iAi No more than 10^9109.
Output format
Will be given NN The number of output from small to large , The numbers are separated by spaces , Wrap at the end of the line without spaces .
I/o sample
Input #1 Copy
5
4 2 4 5 1
Output #1 Copy
1 2 4 4 5
explain / Tips
about 20\%20% The data of , Yes N\leq 10^3N≤103;
about 100\%100% The data of , Yes N\leq 10^5N≤105.
Make a summary
This topic mainly focuses on divide and conquer , Quick sort , First run STL, Turn on O（2） Optimize all samples through

# include <iostream>
using namespace std;
int a[100010];
void qsort(int a[],int l,int r)
{
if(l>=r)
{
	return ;
}
int pivot=a[l];
	int left=l;
	int right=r;
	while(left<right)
	{
		while(left<right&&a[right]>=pivot)
			{
				
				right--;
			}
			if(left<right)      // explain   a[right]<pivot    Shift required pivot On the left  
			{
				a[left]=a[right];  // Overwrite the leftmost value     Because there is pivot It's temporary  
			}
			while(left<right&&a[left]<=pivot)// After the right side, go to the left  
			{
				left++; 
			}
			if(left<right)  // explain  a[left]>pivot     Right key  
			{
			a[right]=a[left];      //   here right The value of has been adjusted  				
			} 
			if(left>=right)
			{
			a[left]=pivot;	
			} 
			// Above is the first sort 
			// Below is divide and conquer    about 
	}
	
		qsort(a,l,right-1);// Initial position to  pivot The previous position  
		qsort(a,right+1,r); //  from pivot Position next to last  
}

int main() 
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	qsort(a,0,n-1); 
	
		for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	
}

P1923 【 Deep base 9. example 4】 Please k Small number
Title Description
Input nn（1 \le n < 50000001≤n<5000000 And nn It's odd ） A digital a_iai（1 \le a_i < {10}^91≤ai<109）, Output the... Of these numbers kk Small number . The smallest number is 00 Small .
Please try not to use nth_element Write this question , Because the focus of this problem is to practice the divide and conquer algorithm .
Input format
nothing
Output format
nothing
I/o sample
Input #1 Copy
5 1
4 3 2 1 5
Output #1 Copy
2
Make a summary
This question is still about quick sorting , And it's also STL, Turn on O（2） It's also STL, Input and output are changed to scanf printf
And open O（2） The example passed completely

# include <bits/stdc++.h>

using namespace std;
int a[5000000];
void qusort(int a[],int l,int r)
{
	if(l>r)
	{
		return ;
	}
	int left=l;
	int right=r;
	int piv=a[l];
	while(left<right)
	{
		while(left<right&&a[right]>piv)
		{
			right--;
		} 
		 if(left<right) // explain a[right]<piv    transposition  
		 {
		 	a[left]=a[right];
		 }
		 // After the right shift, the left marker moves 
		 while(left<right&&a[left]<=piv)  //= To prevent a[right] 
		{
		left++; 	
		} 
		if(left<right)
		{
			a[right]=a[left]; 
		}
		if(left>=right)
		{
			a[left]=piv;
		}
	}
	// Out cycle description =
	// Divide and conquer 
	 qusort(a,l,left-1);
	 qusort(a,left+1,r); 
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	//cin>>n>>m;
		int a[n];
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
qusort(a,0,n-1);		
printf("%d",a[m]);
//	cout<<a[m];
 }

P1200 [USACO1.1] Your flying saucer is here Your Ride Is Here
Title Description
as everyone knows , There's one behind every comet UFO. these UFO From time to time to collect loyal supporters on earth . Unfortunately , Their flying saucers can only bring a group of supporters on every trip . therefore , They want to use a clever scheme to let these groups know in advance who will be taken away by the comet . They gave each comet a name , Use these names to determine whether the group is the specific group taken away （ Who do you think named these comets ？）. The details of how to match will be told below ; Your task is to write a program , The name of the group and the name of the comet determine whether the group can be used by the... Behind the comet UFO Take away .
The group name and comet name are converted into a number in the following way ： The final number is the product of all the letters in the name , among \texttt AA yes 11,\textttZ yes 2626. for example ,\texttt{USACO}USACO The group is 21 \times 19 \times 1 \times 3 \times 15=1795521×19×1×3×15=17955. If the group's number \bmod 47mod47 Equal to the number of comets \bmod 47mod47, You have to tell the team that it needs to be ready to be taken away ！（ remember “a \bmod bamodb” yes aa Divide bb The remainder of , for example 34 \bmod 1034mod10 be equal to 44）
Write a program , Read the comet name and the group name and figure out if you can match the two names with the above scheme , If you can match it , It outputs GO, Otherwise output STAY. The group name and comet name are a string of capital letters without spaces or punctuation （ No more than 66 Letters ）.
Input format
The first 1 That's ok ： A length of 11 To 66 Uppercase string of , The name of the comet .
The first 2 That's ok ： A length of 11 To 66 Uppercase string of , Indicates the name of the team .
Output format
nothing
I/o sample
Input #1 Copy
COMETQ
HVNGAT
Output #1 Copy
GO
Input #2 Copy
ABSTAR
USACO
Output #2 Copy
STAY
explain / Tips
Title Translation from NOCOW.
USACO Training Section 1.1
Make a summary
This question belongs to the entry level It's simple