Summary of thinking questions in December competition

This blog summarizes my wrong thinking questions in the December competition. Because they have no fixed classification, I summarize them.
First question
Pu Yufan has recently learned many properties of prime numbers, so he has developed a strange habit that he can only choose prime numbers and turn a blind eye to composite numbers
Since he won the gold medal in the CCPC provincial competition, he has always promised to take members of the ACM algorithm association to dinner. This day has finally come!
He led all the members to the school restaurant. When everyone was ready to order, he shouted: you can only choose dishes with prime price!
As a future member of ACM algorithm Association, please calculate how many ordering strategies Pu Yufan has
As we all know, because Pu Yufan is very stingy, if he sees that the price is particularly high, he may not order a dish
Because the answer may be large, the final answer needs to take the remainder of 1e^9 + 7
Enter Description:
The first line contains an integer n, 1 < = n < = 1E ^ 3,
The second row has n arrays, and the range of each number is 1 ∼ 10 ^ 8
Example 1
input
6
1 344 34 17 5 2
output
8
Topic analysis mainly focuses on how to solve prime numbers more efficiently (using square)
And the combination of elements in the set sounds very simple. I didn't know it at that time
The details are habitually written in the remarks. The code is as follows.

#include<stdio.h>
int main()
{
	long long a[1020];
	int n;
	scanf("%d",&n);
	int count=0;
	for(int i=0;i<n;i++)//Input step
	{
		scanf("%lld",&a[i]);
		int flag=0;
		for(int j=2;j*j<=a[i];j++)//Just one more equal sign
		//Attention A
		{
			if(a[i]%j==0)//Not prime
			{
				flag=1;
				break;
			}
		}
		if(flag==0&&a[i]!=1)//Don't be
		{
			printf("%d",a[i]);
			count++;
		}
	}
	int sum=1;
	for(int i=1;i<=count;i++)
	{
		sum=(sum*2)%1000000007;//Wonderful method of taking remainder (dogs)
		//Attention B
	}
	printf("%d",sum);
	return 0;
}

There are two considerations
A: Be sure to add an equal sign!
In the non square method, we really don't need to calculate the last number, but in the square method, we may lose its prime number without adding an equal sign
eg:3*3=9. If the equal sign is not added, then 9 will be recognized as a prime number
B: About surplus!
Be sure to take the surplus in the process, otherwise it may explode.
Finally, add a high school knowledge
If there are elements in a set, the combination method is n-square. The number of dishes here is the square of the number of dishes ordered.
Happy second question
In most cases, Gan Jing is very standard in speaking Mandarin, but sometimes it is maddening. This has bothered him for a long time. Suddenly one day, he wanted to correct his pronunciation by reading numbers,
But he didn't want to read the numbers in the normal order, so he wrote some numbers on the blackboard according to some law. For example, if he wanted to count to 9, he would write the numbers in the following format:
1 2 6 7
3 5 8
4 9
If he wants to count to 15, he will write the number in the following format:
1 2 6 7 15
3 5 8 14
4 9 13
10 12
11
He suddenly found that his rule of writing numbers was a snake. The specific description was as follows:
For each slash from bottom left to top right, number 1,2,..., 2n-1 from top left to bottom right; Fill in the numbers from small to large in the order of numbers from small to large, including odd numbers from bottom left to top right, and even numbers from top right to bottom left
Enter Description:
Enter a positive integer n not greater than 10000, indicating the size of the number to be filled
Output Description:
These numbers are output regularly, with a single space between two adjacent elements
Example 1
input
50
output
1 2 6 7 15 16 28 29 45 46
3 5 8 14 17 27 30 44 47
4 9 13 18 26 31 43 48
10 12 19 25 32 42 49
11 20 24 33 41 50
21 23 34 40
22 35 39
36 38
37
At the beginning of this question, I thought of ending a line of output by constantly judging the stop point, so I wrote about more than 100 lines of code and haven't finished it yet.
Of course, that's not the point!
The positive solution of this problem is through oblique input and horizontal output, which can not only facilitate input without so much judgment, but also output without much brain.

#include<stdio.h>
int main()
{
	int a[200][200]={0};
	int n;
	scanf("%d",&n);
	int hang=1;
	int temp=n;//To save the value of n
	while(temp-hang>0)//Judge how many oblique lines there are
	{
		temp-=hang;
		hang++;
	}
	//New definition of temp
	//Make it an intermediate variable
	temp=1;
	for(int i=0;i<hang;i++)
	{
		//int j;// As the standard of relationship
		//Store data
		//Focus A
		if(i%2==0)//Judge from bottom to top
		{
			for(int j=0;j<=i;j++)
			{
				a[i-j][j]=temp;
				temp++;
				if(temp>n)
					goto loop;
			}
		}
		else//Judge from bottom to top
		{
			for(int j=0;j<=i;j++)
			{
				a[j][i-j]=temp;
				temp++;
				if(temp>n)
					goto loop;
			}
		}
	}
loop:;//When the value is 50, it can be cut off
	for(int i=0;i<hang;i++)//Lateral output
	{
		for(int j=0;j<hang;j++)
		{//Focus B
			if(a[i][j]!=0)
			{
				printf("%d",a[i][j]);
				if(a[i][j+1]!=0||j!=hang-1)
					printf(" ");
				if(j==hang-1)
					printf("\n");
			}
			else
			{
				printf("\n");
				break;
			}
		}
	}
	return 0;
}

Key point A: this question is a serpentine assignment mode, so we must pay attention to whether the assignment is from bottom to top or from top to bottom.
Key point B: the core of this problem is to create a two-dimensional sufficient array of all zeros, then assign values one by one, and finally output comprehensively, but 0 is not what we want, so we wrap as soon as we encounter 0, which can be the output we want.
Sweet third question
Pu Yufan's senior is out on a date with his younger sister! As a standard straight man, senior Pu Yufan wanted to buy a cup of milk tea for his younger sister, so he asked her what kind of milk tea she liked to drink. She replied two words
Whatever!
Pu Yufan is silly, but as an excellent ACMer, he won't wait to die. He got the price of milk tea that his younger sister likes to drink and the price list of milk tea shop early! Now you have to judge which kind of milk tea your younger sister likes to drink according to the price of milk tea. If the price of a variety of milk tea meets the requirements, enter the one with the top type
Enter Description:
The first line contains an integer n, indicating that there are n kinds of milk tea
The second line has n numbers a[i], a[i] indicates the price of the i-th milk tea
The third line contains an integer Q, representing Q queries
The fourth line contains Q integers x[i], indicating the price of the ith cup of milk tea that the younger sister likes to drink. If it is not found, it will output - 1
Output Description:
Output Q lines, and an integer in each line represents the answer
Example 1
input
6
1 2 10 5 3 2
1
3
output
5
Example 2
input
5
3 1 7 5 8
2
6
7
output
-1
3
This question involves a knowledge point, that is, map. Because I haven't studied C + +, I don't know enough about the basic usage of map, but I use it in order to save storage space.
Manual split line
map is a kind of mapping, which can establish the mapping of different data types. In fact, it is a bit like an array. The data types I need here are int, so it is more like an array.

map<int,int>pos;

Here we define a mapping of int type to int type and name it pos.
In this way, we don't need to open up a space like the price version of milk tea.
Then we get back to the point
Tell me the idea of this question.
By establishing a one-to-one mapping, store the milk tea and price, and then store the price and location of each milk tea, and avoid repetition through if judgment (because only the first cup of milk tea is needed). In this way, the first map corresponds to the price and the second map corresponds to the location.
It's much easier to find.
Finally, attach the code.

#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
int main()
{
	map<int,int>pos;
	long long pri[100000];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)//Calculate the position of each flower
	{
		scanf("%lld",&pri[i]);
		if(pos[pri[i]]==0)
			pos[pri[i]]=i+1;//pri is the price of milk tea and pos is the location of milk tea
	}
	int ask;
	scanf("%d",&ask);
	for(int i=0;i<ask;i++)//Complete all kinds of milk tea problems
	{
		long long ans;
		scanf("%lld",&ans);
		if(pos[ans]==0)//There is no milk tea at this price
			printf("-1\n");
		else
			printf("%lld",pos[ans]);
	}
	return 0;
}

The fourth question of getting rich
Because zhb likes buying hands very much, but he is very poor, so he wants to make money through stock speculation!
Given an array with a length of N, the ith number in the array represents the price of a given stock on the ith day. Please calculate the maximum profit zhb can obtain. Buy and sell as many shares as possible.
Note: zhb cannot participate in multiple transactions at the same time (zhb must sell the previous shares before buying again).
input
The first line contains the integer N, which represents the length of the array.
The second line contains N positive integers no greater than 100000, representing the complete array.
1 ≤ N ≤ 10^5
output
Output an integer representing the maximum profit.
sample input
6
7 1 5 3 6 4
sample output
7
This problem seems relatively simple, but how to reduce the complexity of logic as much as possible to realize this program is still very important. (timeout tears)
If we are trying to think about this problem, we need to consider when it is the optimal solution of buying, which makes us need to go through many times. It is very easy to timeout and may make mistakes.
So how should we think about it? We should think about it in reverse. If the stock price in the back is higher than that in the front, there will be a purchase process.
Here's the point: writing the program in this way can avoid the process of finding the optimal solution, that is, as long as the price of the stock behind is higher than that of the stock before, it will be completed. (because I certainly won't sell stocks during this period), so I don't have to consider the procedures of buying and selling stocks. Once the stock price grows, the front is higher than the back. At this time, I certainly don't buy from a high place, but I may complete the selling procedures at a high place, so I need to pay attention to it when going through the process. I can't repeat the process, (if you look back and forward) each cycle starts at a place where the share price is high.
The code is as follows

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int a[100000];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[n-i-1]);//Input in reverse order to find the stock price in reverse
	}
	int sum=0;
	for(int j=0;j<n-1;j++)
	{
		int count=0;
		for(int k=j+1;k<n;k++)
		{
			if(a[j]>a[k])
			{
				count+=a[j]-a[k];
				j=k;//Don't repeat it
			}
			else
				break;
		}
		sum+=count;
	}
	printf("%d",sum);
	return 0;
}

Ending flower topic
Pu Yufan, a senior student, recently fell in love with a beautiful primary school sister. He wanted to send a special flower to this primary school sister.
He now has a handful of N beautiful flowers, each of which has a[i] petals. If the difference between the number of petals of one flower and the number of petals of any other flower is equal to 2, he can choose to throw this flower away or discard it.
After several operations, can Pu Yufan find the only special flower for his primary school sister?
Enter Description:
An integer t (1 < = T < = 500) in the first line indicates the number of test samples
The first line of each test sample is an integer n (1 < = n < = 1E4) indicating the number of flowers, and the second line is n integers a i Indicates the number of petals.
Output Description:
Output t line "YES"or"NO"
Example 1
input
1
4
2 4 6 8
output
YES
Example 2
input
1
5
9 3 5 6 7
output
NO
The basic idea of this question is to use map to do a duplicate check, and then after sorting, find out whether the next flower is 2 larger than the previous flower. If it is 2 larger, it can be eliminated.
It doesn't seem difficult, but! One point is very important. If there is only one flower with one number of petals, what should be done? If this flower is unique, it should be OK. If it is not unique, it must not be.

#include<cstdio>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long n;//Number of cycles
    map<long long,long long>ban;
    long long a[100000]={0};//Number of petals stored
	scanf("%lld",&n);
	for(long long k=0;k<n;k++)
	{
		int flag=0;
        ban.clear();//Empty the map for a new start
		long long account;
		scanf("%lld",&account);
		long long judge=0;
        long long t=0;
        int count=0;
		for(long long j=0;j<account;j++)
		{
			scanf("%lld",&t);//Enter the number of petals per flower
			if(ban[t]==0)//The map is used for duplicate checking
			{
				a[judge]=t;//Check the number of petals
				ban[t]=1;//Duplicate checking is realized
				judge++;//Judge how many flowers there are behind
			}
            count++;
		}
		if(judge==1)//A flower with only one number of petals
		{
            if(count>1)//If there are many flowers
                printf("NO\n");
            else//If there is and only one
			    printf("YES\n");
			goto loop;
		}
		sort(a,a+judge);//Sort the flowers from small to large
		for(int j=0;j<judge-1;j++)
		{
			if(a[j]!=a[j+1]-2)//If it is not big, it must not be
			{
				flag=1;
				break;//Then I'll jump out of the loop
			}
		}
		if(flag==1)
			printf("NO\n");
		else
			printf("YES\n");
        loop:;//This cycle ends directly
    }
	return 0;
}

The remarks are very detailed. They are all tears.
Or I'm too delicious and need to work hard.

Posted by Cronje on Mon, 02 May 2022 15:45:21 +0300