PTA class a simulated 8th bomb: 1164-1167

1. Summary of knowledge points

Last shot , Just kidding （ There are still many debts ahead ）

at present 1140-1167 What it feels like to me is —— The whole is not particularly difficult （ This refers to the difficulty ≥ The subject of , Of course, the food is still the same , Home efficiency is really …… It's hard to say ）, And as the number of questions increases , The feeling of routine questions has not changed , Should the template be or should it be , It is best to be able to use flexibly , Because one of the general four topics is about strain （ Be commonly called “ Card score question ”）

Feeling pta Can lay the foundation ~ But the knowledge involved is still incomplete , Preparing for the machine test still requires extensive practice …… Otherwise, it will be for nothing

Question no	difficulty	Knowledge point
1164		string manipulation + matrix
1165		Linked list
1166		Simple applications of graphs
1167		Middle preface + Pile up （ Binary tree simple application ）

2. Sub topic solution

2.1 The first question is 1164 Good in C (20 branch )

【 Subject portal 】

String processing and basic use of matrix , Keep your mind steady ~

• The format is strictly in accordance with the meaning of the title ( Don't be rash )

• The difficulty lies in sentence segmentation , involves string Substring function uses

#include<bits/stdc++.h>
using namespace std;
string sentence;
vector<string>words;// Segment sentences  
struct Alpha{
    
	char matrix[7][5];
}; 
Alpha alpha[26];
void Cut(){
    
	// Segment sentences 
	int len=sentence.length();
	int left=0,right=0;
	string word;
	bool flag=false;
	int i;
	for(i=0;i<len;i++){
    
		if(sentence[i]<='Z'&&sentence[i]>='A'){
    
			if(!flag){
    
				flag=true;
				left=i;
			}
		}else{
    
			// There are consecutive letters in front  
			if(flag){
    
				word=sentence.substr(left,i-left);
				words.push_back(word);
				flag=false;
			} 
		}
	}
	if(flag&&i-left>0){
    
		word=sentence.substr(left,i-left);
		words.push_back(word);
	} 
}
void Print(string word){
    
	int len=word.length();
	for(int row=0;row<7;row++){
    
		if(row){
    
			printf("\n");
		}
		for(int col=0;col<len;col++){
    
			// Print every letter 
			if(col!=0)printf(" ");
			for(int i=0;i<5;i++){
    
				int id;
				if(word[col]<='Z'&&word[col]>='A'){
    
					id=word[col]-'A';
				}else{
    
					id=word[col]-'a';
				}
				printf("%c",alpha[id].matrix[row][i]);
			} 
		}
		
	}
}
int main(){
    
	for(int i=0;i<26;i++){
    
		for(int row=0;row<7;row++){
    
			for(int column=0;column<5;column++){
    
				cin>>alpha[i].matrix[row][column];
			}
		}
	}
	getchar();
	getline(cin,sentence);
	Cut(); 
	for(int i=0;i<words.size();i++){
    
		if(i)printf("\n\n");
		Print(words[i]);
	}
	return 0;
}

2.2 The second question is 1165 Block Reversing (25 branch )

【 Topic link 】

Static list basic questions , Not very hard , Pay attention to the details of the output

But it needs to be revised

The first edition :24/25

#include<bits/stdc++.h>
using namespace std;
int L,N,num;
int head;
struct Node{
    
	int val;
	int addr;
	int next;
};
map<int,Node>nodes;
int addr,val,next_node;
vector<Node>list1;
int main(){
    
	scanf("%d%d%d",&head,&N,&L);
	for(int i=0;i<N;i++){
    
		scanf("%d%d%d",&addr,&val,&next_node);
		Node temp;
		temp.addr=addr;
		temp.val=val;
		temp.next=next_node;
		nodes[addr]=temp;
	}
	// First 
	int p=head;
	while(p!=-1){
    
		list1.push_back(nodes[p]);
		p=nodes[p].next;
	} 
	//list1 In the store  : How to output 
	//0 1 2 3 4 5 6 7
	int n=N/L+(N%L==0?0:1);
	int res=N%L; 
	int fid;
	bool flag=false;
	for(int i=n;i>=1;i--){
    
		if(res){
    
			num=res;
			fid=(i-1)*L;
		}else{
    
			num=L;
			fid=(i-1)*L;
		}
		if(res)res=0;
		for(int j=fid;j<fid+num;j++){
    
			if(!flag){
    
				flag=true;
			}else{
    
				printf(" %05d\n",list1[j].addr);
			}
			printf("%05d %d",list1[j].addr,list1[j].val);
		}
	}
	printf(" -1");
	return 0;
}

The second edition ：AC

#include<bits/stdc++.h>
using namespace std;
int head,n,block;
int arr,val,nex;
struct Node{
    
	int arr;
	int val;
	int next;
};
map<int,Node>nodes;
vector<Node>list0;
int main(){
    
	scanf("%d%d%d",&head,&n,&block);
	for(int i=0;i<n;i++){
    
		scanf("%d%d%d",&arr,&val,&nex);
		Node temp;
		temp.arr=arr;
		temp.val=val;
		temp.next=nex;
		nodes[arr]=temp;
	}
	int p=head;
	while(p!=-1){
    
		list0.push_back(nodes[p]);
		p=nodes[p].next;
	}
	// change , Output : 0 1 2 3 4 5 6 7 
	//1 2 3 4 5 6 7 8
	bool flag=false;
	int len=list0.size();
	int res=len%block;
	int times=len/block;
	if(res!=0)times++;
	//printf(" need %d Time \n",times);
	for(int i=1;i<=times;i++){
    
		int first=(times-i)*block;
		//printf("first=%d\n",first);
		int num=block;
		if(i==1&&res)num=res;
		//printf("num=%d\n",num); 
		// Output  
		for(int j=0;j<num;j++){
    
			if(!flag){
    
				flag=true;
			}else{
    
				printf(" %05d\n",list0[first+j].arr);
			}
			printf("%05d %d",list0[first+j].arr,list0[first+j].val);
		}
	}
	printf(" -1"); 
	return 0;
}


/* A test point ： 00100 8 4 71120 7 88666 00000 4 99999 00100 1 12309 68237 6 71120 33218 3 00000 99999 5 68237 88666 8 -1 12309 2 33218  need 2 Time  00100 1 12309 12309 2 33218 33218 3 00000 00000 4 -1 */ 

2.3 Third question 1166 Summit (25 branch )

【 Topic link 】

Basic problems of graph theory ：

Adjacency graph , No time and memory card , Feel free to write

#include<bits/stdc++.h>
using namespace std;
int n,m;
int k,l;
int a ,b;
vector< vector<int> >relation;
vector<int>q;
vector<int>visnum;
vector<bool>isin;
int main(){
    
	scanf("%d%d",&n,&m);
	relation.resize(n+1);
	visnum.resize(n+1);
	isin.resize(n+1);
	for(int i=0;i<m;i++){
    
		scanf("%d%d",&a,&b);
		if(a==b)continue;
		relation[a].push_back(b);
		relation[b].push_back(a);	
	}
	scanf("%d",&k);
	for(int cnt=1;cnt<=k;cnt++){
    
		fill(visnum.begin(),visnum.end(),0);
		fill(isin.begin(),isin.end(),false);
		scanf("%d",&l);
		q.resize(l);
		for(int i=0;i<l;i++){
    
			scanf("%d",&q[i]);
			isin[q[i]]=true;
		}
		for(int i=0;i<l;i++){
    
			int id=q[i];
			for(int j=0;j<relation[id].size();j++){
    
				int fid=relation[id][j];
				visnum[fid]++;
			}
		}
		// Calculation  1  illegal  2  Someone forgot to invite  
		int flag=0; 
		int ans=n+1; 
		for(int id=1;id<=n;id++){
    
			if(isin[id]&&visnum[id]!=l-1){
    
				flag=1;
				printf("Area %d needs help.\n",cnt);
				break;
			}else if(!isin[id]&&visnum[id]==l){
    
				ans=min(ans,id);
				flag=2;
			}
		} 
		if(flag==2){
    
			printf("Area %d may invite more people, such as %d.\n",cnt,ans);
		} else if(flag==0){
    
			printf("Area %d is OK.\n",cnt);
		}	
	}
	return 0;
}

2.4 Fourth question 1167 Cartesian Tree (30 branch )

【 Topic link 】

Simple questions , It belongs to the middle order + A class of problems of reconstructing tree structure by heap sorting （ Similar middle order + In the following order || Middle preface + Preface ）, The difficulty should be simple , Sequence each time from the middle (inL,inR) Find the smallest as the root node , The left-right sequence recurses to the next left-right subtree

#include<bits/stdc++.h>
using namespace std;
int N;
const int INF=99999999;
// The result of sequence traversal output in the small top heap ----> Sequence traversal output 
struct Node{
    
	int val;
	Node*left=NULL;
	Node*right=NULL;
}; 
vector<int>in;
Node*build(int inL,int inR){
    
	if(inR<inL){
    
		return NULL;
	}
	// Find the root node 
	int min_num=INF;
	int min_id=-1;
	for(int k=inL;k<=inR;k++){
    
		if(in[k]<min_num){
    
			min_num=in[k];
			min_id=k;
		}
	}
	Node *root=new Node;
	root->val=min_num;
	root->left=build(inL,min_id-1);
	root->right=build(min_id+1,inR);
	return root;
}
// Level traversal 
void levelTravel(Node *root){
    
	queue<Node*>q;
	q.push(root);
	bool flag=false;
	while(!q.empty()){
    
		Node*top=q.front();
		Node*temp;
		q.pop();
		if(top->left!=NULL){
    
			temp=top->left;
			q.push(temp);
		}
		if(top->right!=NULL){
    
			temp=top->right;
			q.push(temp);
		}
		if(!flag){
    
			flag=true;
		}else{
    
			printf(" ");
		}
		printf("%d",top->val);
	}
	return;
}

int main(){
    
	scanf("%d",&N);	
	in.resize(N);
	for(int i=0;i<N;i++){
    
		scanf("%d",&in[i]);
	}
	Node *root=build(0,N-1);
	levelTravel(root);
	return 0;
}

twitter , This year's exam questions are quite easy~

3. Reference link