PTA class a simulated 11th bomb: 1124-1131

1. Summary of knowledge points

This assignment is not arranged strictly according to the test paper title , At the same time, the previous （ Long ago ） I've done the topic , This arrangement …… Don't ask , Question is a kind of unnamed obsessive-compulsive disorder that wants to fill the gap

The knowledge points involved in this assignment are

• map+ Level six
• Binary tree
• Priority queue
• Depth-first search

Question no	difficulty	Knowledge point
1124		Array +map, English reading
1125		Array , Looking for a regular
1127		Binary tree , But I just want to give one and a half , Templates , Note output STL Reorder ~
1129		Priority queue + Structure ordering ( Not a problem , But the priority queue forgot how to handle the structure , It really shouldn't be )
1130		Middle order traversal of binary tree and love and hate between brackets
1131		In fact, it should not have this difficulty , It is quite basic to know after reading the solution DFS Variant Mainly to remind yourself DFS Less practice

2. Sub topic solution

2.1 The first question is 1124 Raffle for Weibo Followers (20 branch )

【 Topic link 】

The difficulty lies in …… English trumpet , I didn't understand what he meant , It doesn't feel very difficult , But it's hard to get stuck in reading comprehension ：

The meaning of the topic , There are no rules for how many winners , Just for the person who typed , From the initial position s, Every other n One win at a time , If someone repeats ,s++, Skip this person

For the first time, write according to the vague understanding , violence 12/20, Kneel down , Because I thought n It's a limitation , then m Individuals are in a circle , Wrong understanding baa ！！！ The positive solution is below

#include<bits/stdc++.h>
using namespace std;
int m,n,s;//m Maybe , Number of turns , Starting place  
vector<string>fid;
map<string,bool>winned; 
set<string>st;
int main(){
    
	scanf("%d%d%d",&m,&n,&s);
	fid.resize(m);
	for(int i=0;i<m;i++){
    
		cin>>fid[i];
		winned[fid[i]]=false;
		st.insert(fid[i]);
	}
	if(st.size()<n||s>m){
    
		printf("Keep going...");
	}else{
    
		vector<string>ans;
		int cnt=0;
		s--;// Starting position  
		while(cnt!=n){
    
			s%=m;
			if(winned[fid[s]]==false){
    
				winned[fid[s]]=true;
				ans.push_back(fid[s]);
				cnt++;
				s+=n;
			}else{
    
				s++;
			}
		} 
		// Output the answer  
		for(int i=0;i<ans.size();i++){
    
			printf("%s\n",ans[i].c_str());
		}
		
	}
	return 0;
} 

After revision ：

Refer to Liu Shen code , Conciseness is killed by the moment

#include<bits/stdc++.h>
using namespace std;
int m,n,s;//m Maybe , Number of turns , Starting place  

int main(){
    
	scanf("%d%d%d",&m,&n,&s);
	string str;
	bool flag=false;// Has anyone ever won a prize  
	map<string,bool>winned;
	for(int i=1;i<=m;i++){
    
		cin>>str;
		if(winned[str]==true){
    
			s++;
		}else if(i==s){
    
			winned[str]=true;
			cout<<str<<endl;
			flag=true;
			s=s+n;
		}
	}
	if(flag==false)printf("Keep going...");
	return 0;
} 

2.2 The second question is 1125 Chain the Ropes (25 branch )

【 Topic link 】

Find the rules , Hold your mind ：

First, sort the input rope length segments from small to large ,sum=(sum+v[i])/2, All the way to the end , such , The short ones are folded over and over again , But he is safe and sound , It can ensure that the final result is correct （ I thought it was deep search , As a result, it was easy to find the rule by pushing it on the draft paper ~）

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
int main(){
    
	scanf("%d",&n);
	v.resize(n);
	for(int i=0;i<n;i++){
    
		scanf("%d",&v[i]);
	}
	sort(v.begin(),v.end());
	int sum=v[0];
	for(int i=1;i<n;i++){
    
		sum=(sum+v[i])/2;
	}
	printf("%d",sum);	

	return 0;
}

2.3 Third question 1130 Infix Expression (25 branch )

【 Subject portal 】

Middle order traversal of trees , The output of parentheses needs attention , The outermost parentheses and leaf node parentheses do not need to be output , The rest output parentheses during recursion

#include<bits/stdc++.h>
using namespace std;
struct Node{
    
	char data[15];
	int left;
	int right;
};
vector<Node>nodes;
int n;
bool isLeaf(int a){
    
	if(a==-1)return false;
	if(nodes[a].left==-1&&nodes[a].right==-1){
    
		return true;
	}
	return false;
}
bool isOk(int a){
    
	if(a==-1)return false;
	if(isLeaf(nodes[a].left)&&isLeaf(nodes[a].right)){
    
		return true;
	}
	return false;
}
bool flag=false;
void preTravel(int root,int cnt){
    
	if(root==-1){
    
		return;
	}
	//bool flag=isOk(root);
	if(cnt&&!isLeaf(root)){
    
		printf("(");
	}
	preTravel(nodes[root].left,cnt+1);
	printf("%s",nodes[root].data);
	preTravel(nodes[root].right,cnt+1);
	if(cnt&&!isLeaf(root)){
    
		printf(")");
	}
} 
const int maxn=100;
bool isc[maxn]={
    false};
int main(){
    
	scanf("%d",&n);
	nodes.resize(n+1);
	for(int i=1;i<=n;i++){
    
		scanf("%s %d %d",nodes[i].data,&nodes[i].left,&nodes[i].right);
		isc[nodes[i].left]=true;
		isc[nodes[i].right]=true;
	}
	// Find the root node  
	int root=-1;
	for(int i=1;i<=n;i++){
    
		if(!isc[i]){
    
			root=i;
			break;
		}
	}
	preTravel(root,0);
	return 0;
}

2.4 Fourth question 1129 Recommendation System (25 branch )

【 Subject portal 】

Intuition tells me that priority queues should be used , Ran goose …… I forgot how to use the priority queue , Looking at the API…… Fault fault

Priority queue + Structure

Each time you output it, you have to make it different id Deposit in vector in , Output and then save back to the priority queue

#include<bits/stdc++.h>
using namespace std;
int n,k;
struct Node{
    
	int id;
	int t;
};
bool operator<(Node a,Node b){
    
	if(a.t!=b.t){
    
		return a.t<b.t;
	}else{
    
		return a.id>b.id;
	}
}
priority_queue<Node>ans;
const int maxn=50009;
int cnt[maxn]={
    0};
Node temp;
int id;
vector<Node>op;
set<int>st; 
int main(){
    
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
    
		scanf("%d",&id);
		cnt[id]++;
		if(i!=1){
    
			printf("%d:",id);
			int output=k<st.size()?k:st.size();
			// Output  
			for(int x=0;x<output;x++){
    
				temp=ans.top();
				ans.pop();
				printf(" %d",temp.id);
				if(temp.id!=id){
    
					op.push_back(temp);
				}
			}
			// Save it back 
			for(int x=0;x<op.size();x++){
    
				ans.push(op[x]);
			}
			op.clear();
			printf("\n");
		}
		temp.id=id;
		temp.t=cnt[id];
		ans.push(temp);
		st.insert(id);
	}
	return 0;
} 

2.5 Fifth question 1127 ZigZagging on a Tree (30 branch )

【 Topic link 】

Feeling PTA Generally, there are many variations of binary tree , however Dij、 Union checking set 、 Priority queues still have to be mastered , Otherwise, I will give it for nothing ,（ Looks like 、 Maybe 、 It seems that other computer testers won't be so obsessed with trees ~

• In the sequence traversal + After the sequence traversal **—>** Sequence traversal output
• The structure stores the output of the hierarchical traversal , Output as required after reordering

#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>post;
vector<int>in;
struct Node{
    
	int val;
	Node *left;
	Node *right;
	int level;
};
struct Ans{
    
	int data;
	int level;
	int cnt;
};
vector<Ans>ans;
bool cmp(Ans a,Ans b){
    
	if(a.level!=b.level){
    
		return a.level<b.level;
	}else{
    
		if(a.level%2==1){
    
			// Odd number floor , From right to left 
			return a.cnt>b.cnt; 
		}else{
    
			return a.cnt<b.cnt;
		}
	}
}
Node *build(int inL,int inR,int postL,int postR){
    
	if(inL>inR){
    
		return NULL;
	}
	Node *root=new Node;
	root->val=post[postR];
	int k;
	for(k=inL;k<=inR;k++){
    
		if(in[k]==post[postR]){
    
			break;
		}
	}
	int left_num=k-inL;
	root->left=build(inL,k-1,postL,postL+left_num-1);
	root->right=build(k+1,inR,postL+left_num,postR-1);
	return root;
}
void levelTravel(Node *root){
    
	queue<Node*>q;
	root->level=1;
	q.push(root);
	bool flag=false;
	Node *temp;
	int cnt=0;
	while(!q.empty()){
    
		cnt++;
		Node *top=q.front();
		q.pop();
		if(top->left!=NULL){
    
			temp=top->left;
			temp->level=top->level+1;
			q.push(temp);
		}
		if(top->right!=NULL){
    
			temp=top->right;
			temp->level=top->level+1;
			q.push(temp);
		}
		// Save... For each line  
		Ans a;
		a.level=top->level;
		a.data=top->val;
		a.cnt=cnt;
		ans.push_back(a);
	}
	return ;
}
int main(){
    
	scanf("%d",&N);
	post.resize(N);
	in.resize(N);
	for(int i=0;i<N;i++){
    
		scanf("%d",&in[i]);
	}
	for(int i=0;i<N;i++){
    
		scanf("%d",&post[i]);
	}
	Node*root=build(0,N-1,0,N-1);
	levelTravel(root);
	sort(ans.begin(),ans.end(),cmp);
	for(int i=0;i<N;i++){
    
		if(i)printf(" ");
		printf("%d",ans[i].data);
	}

	return 0;
} 

2.6 Sixth question 1131 Subway Map (30 branch )

【 Topic link 】

twitter ： I don't think there are many searches , Difficult words , Just read the topic , Generally, it's not very too laggy time （）~

Because it took me an afternoon to barely get to 19…… Meow, meow , Facing the wall , So I read the answer of the blog directly , The idea given by Liu Shen is to search deeply ……（ Introduction to the standard ）, Somebody said DFS In fact, it is not allowed under the strict data ,PTA The test data points are not very strict , So in general DFS You can go through

The revised ideas and points for attention are posted at the bottom of the first edition ~

The first edition ：19/30

DFS I feel my hands are rustling

#include<bits/stdc++.h>
using namespace std;
# define INF 99999999
struct Node{
    
	int sid;
	int line;
};
int n,k,num,sid;
int sign;
int vis[10000]={
    0};
vector<Node>taken;
vector<Node>final;// The final answer  
vector<vector<int> >lines;// The name of the station that each line passes through 
map<int,vector<int> >stop; // Which route does each station belong to  
// Calculate the minimum number of platforms 
int st,ed; 
int ans;
int changes;
int getNextSid(int pos,int line){
    
	int len=lines[line].size();
	for(int i=0;i<len;i++){
    
		if(lines[line][i]==pos){
    
			if(i==len-1){
    
				return -1;
			}else{
    
				return  lines[line][i+1];
			}
		}
	}
	return -1;
} 
int getPreSid(int pos,int line){
    
	int len=lines[line].size();
	for(int i=1;i<len;i++){
    
		if(lines[line][i]==pos){
    
			return lines[line][i-1];
		}
	}
	return -1;
} 
void dfs(int pos,int line,int gone,int cnt){
    
	/* Current platform number , line , Number of sites that have passed */
	// If the answer is not unique , Output the least multiplicative  
	//printf(" Current site %04d,  Current route :%d , The current number of sites passing by %d\n",pos,line,gone); 
	gone++;
	vis[pos]=sign;
	Node node;
	node.line=line;
	node.sid=pos;
	taken.push_back(node);
	if(gone>ans||(gone==ans&&cnt>changes)){
    
		return;
	}
	// end , No further exploration is required  
	if((pos==ed&&ans>gone)||(pos==ed&&ans==gone&&cnt<changes)){
    
		ans=gone;
		final=taken; 
		return;
	}
	// Explore  
	for(int i=0;i<stop[pos].size();i++){
    
		int tline=stop[pos][i];
		// Next Station ： 
		int nextpos=getNextSid(pos,tline);
		int nc=cnt;
		if(tline!=line)nc++;
		if(nextpos!=-1&&vis[nextpos]!=sign){
    
			dfs(nextpos,tline,gone,nc);
			// to flash back  
			taken.pop_back();
			vis[nextpos]=sign-1;
		}
		// Last station ：
		int prepos=getPreSid(pos,tline);
		if(prepos!=-1&&vis[prepos]!=sign){
    
			dfs(prepos,tline,gone,nc);
			// to flash back  
			taken.pop_back();
			vis[prepos]=sign-1;
		}
	} 
	return;
}
int main(){
    
	scanf("%d",&n);
	lines.resize(n); 
	for(int i=0;i<n;i++){
    
		scanf("%d",&num);
		for(int j=0;j<num;j++){
    
			scanf("%d",&sid);
			lines[i].push_back(sid);
			stop[sid].push_back(i);
		}	
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
    
		sign=i;
		taken.clear();
		scanf("%d%d",&st,&ed);
		ans=INF;
		changes=INF;
		for(int j=0;j<stop[st].size();j++){
    
			dfs(st,stop[st][j],0,0);
		}
		// Output the answer  
		printf("%d\n",ans-1);
		bool flag1=false,flag2=false;// The starting point 、 Whether the end point has been output  
		int s=final[0].sid,e=final[0].sid,myline=final[0].line;
		for(int x=0;x<final.size();x++){
    
			if(final[x].line==myline){
    
				e=final[x].sid;
			}else{
    
				// Dissimilarity 
				printf("Take Line#%d from %04d to %04d.\n",myline+1,s,e); 
				s=final[x-1].sid,e=final[x].sid,myline=final[x].line;
			}
		}
		printf("Take Line#%d from %04d to %04d.\n",myline+1,s,e); 
		
	}
	return 0;
}

DFS edition ：

Ignore Line The impact of the route , First, it is regarded as the problem of finding the shortest path in graph theory , Deep search deployment , When making the final judgment, first compare the path length , Compare the number of line stations with the same length .

In traditional dfs Find the shortest path , Combined with the lines【i】【j】 The array stores which route a road segment belongs to Line( Because the title clearly states that there are no overlapping sections , Only coincident sites , Reflect again the importance of examining questions ！！！！)

• graph theory （DFS Shortest path ）
• STL Store answers
• When the length of the last route is the same ,transCount(temppath) Function to calculate the number of station transfers ~

The second edition ：AC

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
const int inf=99999999;
vector<vector<int> >graph(maxn);// Storage map _ Connection between sites  
int lines[maxn][maxn];
bool vis[maxn]={
    false};
vector<int>path,temppath;
int n,k,num,sid; 
int st,ed,pre;
int minCnt,minTrans;
int transCount(vector<int>temppath){
    
	int len=temppath.size();
	if(len<=2)return 0;
	
	int sum=0;
	int pre=temppath[0],sid=temppath[1];
	int preLine=lines[pre][sid];
	for(int i=2;i<len;i++){
    
		pre=temppath[i-1];
		sid=temppath[i];
		if(lines[pre][sid]!=preLine){
    
			sum++;
			preLine=lines[pre][sid];
		}
	}
	return sum;
}
void dfs(int pos,int cnt) {
    
	// Current station number , Number of stops 
	if(pos==ed&&((cnt<minCnt)||(cnt==minCnt&&transCount(temppath)<minTrans))){
    
		// eligible 
// printf("pos==%d\n",pos);
// printf("debug:%d %d real:%d %d\n",temppath[0],temppath[temppath.size()-1],st,ed); 
		minCnt=cnt;
		minTrans=transCount(temppath);
		path=temppath;
		return;
	} 
	if(pos==ed||cnt>minCnt){
    
		return;
	}
	// Deep search 
	for(int i=0;i<graph[pos].size();i++){
    
		int newpos=graph[pos][i];
		if(vis[newpos]==false){
    
			vis[newpos]=true;
			temppath.push_back(newpos);
			dfs(newpos,cnt+1);
			// to flash back 
			vis[newpos]=false;
			temppath.pop_back();
		}
	} 
}
int main(){
    
	scanf("%d",&n);
	for(int i=0;i<n;i++){
    
		scanf("%d%d",&num,&pre);
		for(int j=1;j<num;j++){
    
			scanf("%d",&sid);
			graph[pre].push_back(sid);
			graph[sid].push_back(pre);
			lines[sid][pre]=i;
			lines[pre][sid]=i;
			pre=sid;
			
		}
	}
	scanf("%d",&k);
	for(int i=0;i<k;i++){
    
		scanf("%d%d",&st,&ed);
		minCnt=inf;
		minTrans=inf;
		temppath.clear();
		temppath.push_back(st);
		vis[st]=true;
		dfs(st,0);
		vis[st]=false;
		printf("%d\n",minCnt);
		// Output the answer 
		int s=st,len=path.size();
		int preLine=lines[s][path[1]];
		for(int j=1;j<len;j++){
    
			if(lines[path[j-1]][path[j]]!=preLine){
    
				printf("Take Line#%d from %04d to %04d.\n",preLine+1,s,path[j-1]); 
				s=path[j-1];
				preLine=lines[path[j-1]][path[j]];
			}
		}
		// The final output 
		printf("Take Line#%d from %04d to %04d.\n",lines[path[len-2]][ed]+1,s,ed); 
// for(int j=1;j<len;j++){
    
// printf("line#%d: %04d->%04d\n",lines[path[j-1]][path[j]],path[j-1],path[j]);
// }
		
	}
	
	return 0;
} 

Dig a hole , I think Dij It's OK, too ~

3. Reference link

1. 1124 Answer key —— Liu god
2. C++ Priority queues are used in structures
3. 1131 Answer key —— Liu god （DFS）
4. 1131 Answer key —— efficiency