2022 Summer vacation daily question

week1

4268. Sexy prime

“ Sexy prime ” It is shaped like (p,p+6) Such a pair of prime numbers .
It's called , Because the Latin tube “ 6、 ... and ” It's called “sex”（ That is, English “ sexy ”）.
Now give an integer , Please judge whether it is a sexy prime .

Input format
Input gives a positive integer on a line N.
Output format
if N It's a sexy prime , Output in one line Yes, And output and on the second line N Another sexy prime paired （ If such a number is not unique , The one with the smaller output ）.
if N Not a sexy prime , Output in one line No, Then output greater than... On the second line N The minimum number of sexy prime .

Data range
1≤N≤108
sample input 1：
47
sample output 1：
Yes
41
sample input 2：
21
sample output 2：
No
23

#include<bits/stdc++.h> 
using namespace std;


bool is_prime(int x)
{
    
	if(x < 2)return false;
		
	for(int i = 2;i <= x / i;i++)
		if(x % i == 0)
			return false;
	return true;
}

int main() 
{
    
	int n;
	cin >> n;
	 
	for(int i = n- 6; i <= n ;i += 12)   // It's sexy prime  
	 	if(is_prime(i) && is_prime(n))
	 	{
    
			cout << "Yes" << endl;
			cout << i << endl;
			return 0;	 	
	 	}
	 
	for(int i = n + 1;;i++)   // Not a sexy prime , Find the latest sexy prime  
		if(is_prime(i) && (is_prime(i-6) || is_prime(i+6)) )
		{
    
			cout << "No" << endl;
			cout << i << endl;
			return 0;
		}
	
	return 0;
}

4269. School day

2019 Zhejiang University will celebrate its establishment in 122 Anniversary of the .
In preparation for the school day , Alumni Association collects all alumni ID number. .
Now I need you to write a program , The ID number of all the people who attend the celebration. , Count how many alumni have come .
Input format
The input gives a positive integer on the first line N.
And then N That's ok , Each row gives an alumni ID number. （18 Bits consist of numbers and uppercase letters X Composed string ）. The title ensures that the ID number is not duplicated. .
Then give the information of all the people who came to attend the school celebration ：
First is a positive integer M.
And then M That's ok , Each row gives the ID number of a person. . The title ensures that the ID number is not duplicated. .
Output format
First, output the number of alumni participating in the celebration in the first line .
Then output the oldest alumni ID number in the second row. —— Pay attention to ID No 7-14 Bit gives yyyymmdd Birthday in format .
If no alumni come , Then output the ID number of the oldest guests in the second row. . The title guarantees that such alumni or guests must be the only one .

Data range
1≤N,M≤105
sample input ： [ Former alumni , Another guest ]
5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042
sample output ：
3
150702193604190912

// Two sets calculate the number of intersections use --> Hashtable

#include<bits/stdc++.h>
using namespace std;

int main()
{
    
	int n,m;   // Number of students on campus  ,  Number of guests  
	cin >> n ;
	
	unordered_set<string> hash;   // Store all alumni ID number  
	while(n --) // Traverse  
	{
    
		string name;
		cin >> name;
		hash.insert(name);  //set Containers .insert() 
	} 
	
	cin >> m;  
	string a,b; 
	
	int cnt = 0;
	while(m --)  
	{
    
		string name; // Comparison of the same type  
		cin >> name;
		if(hash.count(name))   // [ use count function , Just having it can serve 1]  Count the number of alumni  &  Find the oldest  
		{
    
			cnt ++;
			if(a.empty() || a.substr(6,8) > name.substr(6,8)) a = name;   //x.substr( Start subscript 6, Read 8 position ) 
		}	
		if(b.empty() || b.substr(6,8) > name.substr(6,8)) b = name;
	}
	
	cout<< cnt << endl;  // Count the number of alumni  
	if(cnt) cout << a << endl;   
	else cout << b << endl;   // No alumni , Is the oldest guest  
	
	return 0;
}

week2

4273. List merge

Given two single chain tables L1=a1→a2→…→an-1→an and L2=b1→b2→…→bm-1→bm.
If n≥2m, Your task is to reverse the shorter list , Then merge it into a longer linked list , Get the shape of a1→a2→bm→a3→a4→bm-1… Result .
For example, give two linked lists as 6→7 and 1→2→3→4→5, You should output 1→2→7→3→4→6→5.
Add
This question may contain nodes that are not in the two single linked lists , These nodes need not be considered .

Input format
Input first gives two linked lists in the first row L1 and L2 The address of the header node of , And positive integers N, That is, the total number of nodes given .
The address of a node is 5 Nonnegative integer of digits （ May contain leading 0）, Empty address NULL use -1 Express .
And then N That's ok , Each line gives the information of a node in the following format ：
Address Data Next
among Address Is the address of the node ,Data No more than 105 The positive integer ,Next Is the address of the next node .
The title ensures that there is no empty linked list , And the longer list is at least twice as long as the shorter list .
Output format
Output the result linked list in order , Each node occupies a row , The format is the same as the input .
Data range
1≤N≤10⁵
sample input ：
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
sample output ：
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
difficulty ： Simple
when / Empty limit ：0.4s / 64MB
Total number of passes ：1861
Total attempts ：4517
source ：PAT Class a real topic 1161
Algorithm tags

【 Only interview and write a linked list , Otherwise, it's hard to please

 
#include<bits/stdc++.h>
using namespace std;
#include<cstring>
#include<vector>
#include<algorithm> 

#define x first // Every node (x,y) =  Binary pair( A weight , Next address )
#define y second

typedef pair<int ,int > PII;

const int N = 100010;

int h1,h2,n;   // The address of the head node is stored h1,h2 , n Number of knots  
int v[N],ne[N];  // Save weights and next ,  If the subscript just corresponds, there is no need to save  , So far, the whole linked list structure is accessed 
 

int main()
{
    
	
	scanf("%d%d%d",&h1,&h2,&n); 
	while(n--)
	{
    
		int addr,val,next; // Address  ,  A weight  ,next 
		scanf("%d%d%d",&addr,&val,&next); 
		v[addr] = val, ne[addr] = next; 
	}
	
	vector<PII> a,b; // Two arrays   Analog list  【PII pair<int ,int> type  】 
	for(int i = h1;i != -1;i = ne[i]) a.push_back({
    i,v[i]});   //{ Address , A weight } 
	for(int i = h2;i != -1;i = ne[i]) b.push_back({
    i,v[i]});
	
	if(a.size() < b.size() ) swap(a,b);  // send a For long arrays  
	
	vector<PII> c;
	for(int i = 0,j = b.size() -1 ;i < a.size();i += 2,j-- ) 
	{
    
		c.push_back(a[i]);
		if(i + 1 < a.size() ) c.push_back(a[i + 1]);
		if(j >= 0)c.push_back(b[j]); 
	}
	
	for(int i = 0;i < c.size() ;i ++)
	{
    
		printf("%05d %d ",c[i].x,c[i].y);
 		if (i + 1 < c.size()) printf("%05d\n", c[i + 1].x);
        else puts("-1");
    }

    return 0;
}
 

4274. Postfix expression

Given a binary expression tree , Please output the corresponding suffix expression , Brackets are required to reflect the priority of the operator .

Input format
The first line contains integers N, Represents the number of nodes . Node number 1～N.
Next N That's ok , Each row gives information about a node （ The first i Row corresponds to the second row i Nodes ）
The format is ：data left_child right_child
among ,data It's not more than 10 Character string ,left_child and right_child Are the numbers of the left and right child nodes of the node .

No child node （ namely NULL）, Then use -1 Express .

The following two figures correspond to the two examples given .

Output format
Output answers in one line , There must be no spaces between expression symbols .

Data range
1≤N≤20
sample input 1：
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
sample output 1：
(((a)(b)+)((-(d))))
sample input 2：
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1
sample output 2：
(((a)(2.35)*)(-((str)(871)%))+)

【 Suffix expressions don't actually need parentheses , Read the number and press it into the stack , Read the two element operations in the symbol fetch stack and put them back on the stack 】
Computers can process operations with suffix expressions without brackets

#include<bits/stdc++.h>
using namespace std;

const int N = 25;

int n;
string v[N];  // value  
int l[N],r[N]; // Left and right child numbers  ,  Not for -1 
bool st[N];  // Mark whether there is a parent node  

void dfs(int u)
{
    
	cout << "(";  // Every point should be surrounded by brackets  
	
	if(l[u] != -1 && r[u] != -1) // If left and right children have  , Ergodic left 、 Right  
	{
    
		dfs(l[u]);
		dfs(r[u]);
		cout << v[u];
	}	
	else if(l[u] == -1 && r[u] == -1) // If there are no left or right children  , Is leaf variable  
	{
    
		cout << v[u]; // Output weights  
	}
	else 
	{
    
		cout << v[u];
		dfs(r[u]);// Go down again   Right son  
	}
	
	cout << ")";
	
}


int main()
{
    
	cin >> n;
	for(int i = 1;i <= n;i ++)
	{
    
		cin >> v[i] >> l[i] >> r[i];
		if(l[i] != -1) st[l[i]] = true;
		if(r[i] != -1) st[r[i]] = true;
	} 
	
	int root;// The root node  
	for(int i = 1;i <= n;i++)
		if(!st[i])
			root = i;
	
	dfs(root);
	
	return 0;
}

4275. Dijkstra Sequence

Dijkstra Algorithm is one of the most famous greedy algorithms .
It is used to solve the single source shortest path problem , That is, specify a specific source vertex , Find the shortest path from this vertex to all other vertices of a given graph .
It was developed by computer scientists Edsger W. Dijkstra On 1956 Conceived in and published three years later .
In this algorithm , We need to constantly maintain a set of vertices in the shortest path tree .
At each step , We find a vertex that is not yet in the set and has the smallest distance from the source vertex , And put it in the collection .
therefore , adopt Dijkstra Algorithm , We can generate an ordered sequence of vertices step by step , We call it Dijkstra Sequence .
For a given graph , There may be more than one Dijkstra Sequence .
for example ,{5,1,3,4,2} and {5,3,1,2,4} Are all given graphs Dijkstra Sequence .
Be careful , The first vertex in the sequence is the specified source vertex .
Your task is to check whether a given sequence is Dijkstra Sequence .

Input format
The first line contains two integers N and M, Represents the number of points and edges in the graph .
Number of points 1～N.
Next M That's ok , Each line contains three integers a,b,c, Indication point a Sum point b There is an undirected edge between , The length is c.
The next line contains integers K, Indicates the number of sequences to be judged .
Next K That's ok , Each line contains a 1～N Permutation , Represents a given sequence .
Output format
common K That's ok , The first i Line output the K Judgment of sequences , If the sequence is Dijkstra Sequence is output Yes, Otherwise output No.

Data range
1≤N≤1000,
1≤M≤10⁵,
1≤a,b≤N,
1≤c≤100,
1≤K≤100,
Ensure that a given undirected graph is connected ,
Ensure no double edges and self rings （ The official website didn't mention , But after actual measurement , The official website data meets this condition ）.

sample input ：
5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4
sample output ：
Yes
Yes
Yes
No

#include<bits/stdc++.h>
using namespace std;

const int N = 1010 , INF = 0x3f3f3f3f;



int n,m;
int dist[N],g[N][N]; // g Save map  
bool st[N];   // Mark past  
int q[N];

bool dijstra()
{
    
	memset(dist,0x3f,sizeof dist);  
	memset(st,0,sizeof st);  
	dist[q[0]] = 0;
	
	for(int i = 0;i < n;i++)
	{
    
		int t = q[i];
		for(int j = 1;j <= n ;j++)
			if(!st[j] && dist[j] < dist[t])  // Traverse all points , see t Is it the shortest path  
				return false;
		st[t] = true;
		for(int j = 1;j <= n ;j++)
		dist[j] = min(dist[j], dist[t] + g[t][j]);
	}
	return true;
}
int main()
{
    
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof g);  
	while(m--)
	{
    
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a][b] = g[b][a] = c;
	}
	
	int k;
	scanf("%d",&k);
	while(k --)
	{
    
		for(int i = 0;i < n;i ++ ) scanf("%d",&q[i]);
		if(dijstra())puts("Yes");
		else puts("No");
	}
	
	return 0;
}

week3

3644. Narcissistic number

Spring is the season of flowers , Narcissus is one of the most charming representatives , There's a narcissus number in math , It's defined as ：
“ Narcissistic number ” A three digit number , The cube sum of its digits is equal to itself , such as ：153=13+53+33.
Now it's required to output all the data in m and n The number of daffodils in the range .
Input format
Input contains multiple sets of test data .
Each group of data occupies one row , Contains two integers m and n.
The last line 0 0 End of input .

Output format
Output one line of answers for each group of data , Output from small to large all located in [m,n] The number of daffodils in the range , The numbers are separated by spaces , If not, output no.

Data range
100≤m≤n≤999,
The input can contain at most 10 Group data .

sample input ：
100 120
300 380
0 0
sample output ：
no
370 371

#include<bits/stdc++.h> 
using namespace std;
int main() {
    
	
int n,m;
bool flag ;	
while(cin >> m >> n ,n || m)   //n , m != 0 , Range [m,n] 
{
    
	flag = true;
	for(int i = m;i <= n; i++)
	{
    
		int j =  i % 10 , k = i /10 % 10 , l = i / 100;    // Ten hundred  /10%10 
		if(j*j*j + k*k*k + l*l*l == i){
     
			cout << i << " ";
			flag = false;	
		}		
	
	}
	
	if(flag) cout << "no" << endl;
	else cout << endl;
}
	
	
	return 0;
}
*/

/* Reference method 2  int main() { int n,m; while(cin>>n>>m,n,m){ int f=-1; for(int i=n;i<=m;i++){ // Test range  int t; int s=0; int k=i; while(k!=0){ // One right at a time , Take one  t For each number of temporary records, the total is s t=k%10; k/=10; s+=t*t*t; } if(s==i) {cout<<i<<' '; f=0;} } if(f==-1) puts("no"); else puts(""); } return 0; }