1. 知识点总结

100/100~

题目	难度	知识点
Good in C	🎯	数组
Block Reversing	🎯	链表
Summit	🎯	图
Cartesian Tree	🎯	二叉树（层序遍历）

2. 分题题解

2.1 Good in C

作为第一题来讲算是比较难和麻烦的题目了，有点搞心态；

实际上还是基础的string+数组，仔细审题大概30min内可以KO

#include<bits/stdc++.h>
using namespace std;
struct Matrix{
	char m[7][5];
};
map<char,Matrix>matrix; 
string sentence;
vector<string>words; 
void Cut(string sentence){
	int len=sentence.length();
	string word="";
	for(int i=0;i<len;i++){
		if(sentence[i]<='Z'&&sentence[i]>='A'){
			word+=sentence[i];
		}else{
			if(word!=""){
				words.push_back(word);
				word="";
			}
		}
	}
	if(word!=""){
		words.push_back(word);
		word="";
	}
	return ;
}
void Print(string word){
	
	int len=word.length();
	for(int r=0;r<7;r++){
		for(int i=0;i<len;i++){
			for(int c=0;c<5;c++){
				printf("%c",matrix[word[i]].m[r][c]);
			}
			if(i!=len-1){
				printf(" ");
			}
		}
		if(r!=6){
			printf("\n");
		}
	}
}
int main(){
	for(int i=0;i<26;i++){
		char temp='A'+i;
		for(int r=0;r<7;r++){
			for(int c=0;c<5;c++){
				cin>>matrix[temp].m[r][c];
			}
		}
	}
	getchar();
	getline(cin,sentence);//输入句子 
	Cut(sentence);//将句子拆开
	int len=words.size();
	for(int i=0;i<len;i++){
		Print(words[i]);
		if(i!=len-1){
			printf("\n\n");
		}
	}
	
	return 0;
}

2.2 Block Reversing

链表+STL基础

#include<bits/stdc++.h>
using namespace std;
int num,k,head;
struct Node{
	int addr;
	int val;
	int nxt;
};
vector<vector<Node>>blocks;
vector<Node>block;
map<int,Node>nodes;
int addr,nxt,val;
int main(){
	scanf("%d%d%d",&head,&num,&k);
	for(int i=0;i<num;i++){
		scanf("%d%d%d",&addr,&val,&nxt);
		nodes[addr].val=val;
		nodes[addr].addr=addr;
		nodes[addr].nxt=nxt;
	}
	//遍历
	int cnt=0;
	int index=0;
	int p=head;
	while(p!=-1){
		cnt++;
		block.push_back(nodes[p]);
		if(cnt%k==0){
			blocks.push_back(block);
			block.clear();
		}
		p=nodes[p].nxt;
	}
	if(block.size()!=0){
		blocks.push_back(block);
	}
	//下面是输出答案
	int len=blocks.size();
	for(int i=len-1;i>=0;i--){
		//逆着block的组装顺序
		int tlen=blocks[i].size();
		
		for(int j=0;j<tlen;j++){
			if(j==0&&i!=len-1){
				printf("%05d\n",blocks[i][j].addr);
			}
			if(j!=tlen-1){
				printf("%05d %d %05d\n",blocks[i][j].addr,blocks[i][j].val,blocks[i][j].nxt);
			}else{
				printf("%05d %d ",blocks[i][j].addr,blocks[i][j].val);
			}
		} 
	} 
	printf("-1");
	return 0;
}

2.3 Summit

没怎么卡时间复杂度，所以暴力破解就可以

#include<bits/stdc++.h>
using namespace std;
int N,M;
int K,L;
//强连通图
vector<set<int>>graph;
vector<int>q;
int u,v;
//大家共有的直接朋友：最小编号 
int main(){
	scanf("%d%d",&N,&M);
	graph.resize(N+1);
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		graph[u].insert(v);
		graph[v].insert(u);
	}
	scanf("%d",&K);
	for(int i=0;i<K;i++){
		scanf("%d",&L);
		q.clear();
		q.resize(L);
		for(int j=0;j<L;j++){
			scanf("%d",&q[j]);
		}
		//是否每个人都是另一个人的直接朋友 
		bool flag1=false;
		for(int u=0;u<L;u++){
			for(int v=u+1;v<L;v++){
				if(graph[q[u]].find(q[v])==graph[q[u]].end()){
					printf("Area %d needs help.\n",i+1);
					flag1=true;
					break;
				}
			}
			if(flag1){
				break;
			}
		} 
		if(flag1){
			continue;
		}
		//是否还有其他人可以加入 
		bool flag2=false;
		set<int>temp;
		for(int u=0;u<L;u++){
			for(set<int>::iterator it=graph[q[u]].begin();it!=graph[q[u]].end();it++){
				if(find(q.begin(),q.end(),*it)==q.end()){
					temp.insert(*it);
				}
			}
		}
		//判断temp中是否存在大家都有的元素
		for(set<int>::iterator it=temp.begin();it!=temp.end();it++){
			int u;
			for(u=0;u<L;u++){
				if(graph[q[u]].find(*it)==graph[q[u]].end()){
					break;
				}
			}
			if(u==L){
				printf("Area %d may invite more people, such as %d.\n",i+1,*it);
				flag2=true;
				break;
			}
		}
		if(!flag2){
			printf("Area %d is OK.\n",i+1);
		}
	} 
	return 0;
}

2.4 Cartesian Tree

考察小顶堆+二叉树的层次遍历，基础题

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
const int inf=INT_MAX;
struct Node{
	int val;
	Node* left=NULL;
	Node* right=NULL;
}; 
Node* build(int l,int r){
	//找到l到r之间最小的作为
	int k=-1;
	int min_val=inf;
	for(int i=l;i<=r;i++){
		if(min_val>v[i]){
			min_val=v[i];
			k=i;
		}
	}
	if(k==-1){
		return NULL;
	}
	Node*root=new Node;
	root->val=min_val;
	root->left=build(l,k-1);
	root->right=build(k+1,r);
	//printf("root:%d\n",root->val); 
	return root;
}
//层次遍历
void levelTravel(Node*root){
	queue<Node*>q;
	q.push(root);
	int cnt=0;
	while(!q.empty()){
		Node *top=q.front();
		q.pop();
		if(top->left!=NULL){
			q.push(top->left);
		}
		if(top->right!=NULL){
			q.push(top->right);
		}
		if(cnt){
			printf(" ");
		}
		cnt++;
		printf("%d",top->val);
	}
} 
int main(){
	scanf("%d",&n);
	v.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	//构建二叉树:最小堆
	Node*root=build(0,n-1);
	levelTravel(root);
	return 0;
}