1. 知识点总结

本次作业涉及到的知识点有：

模拟
简单图论

题号	难度	知识点
1148	🐸😣	模拟，比较考察思维全面性的一道题
1149	🐸	简单图论（邻接图存储），稳住心态，一般前两题卡时间也不会卡得非常难
1150	🕊	先鸽了哈，之前做过了~
1151	🐸🐸	二叉树+数组（时间复杂度优化）

2. 分题题解

2.1 第一题

这题……不难😅但是卡了45min(目前第一道卡的时间最久的一次)，没有时间卡分的测试点，暴力模拟即可，需要注意的是思维的全面性，假定i与j分别为假话狼和真话狼，则-v[i]与v[j]是两个正确事实，若为负数，则绝对值必须是i或j,若为正数，则必须是i,j之外的其他数字；其他的“人”讲真话的话，若为负则绝对值为i,j若为正则其他数字，需要注意的是有一个人讲谎话，所以必须有一个编号为“人”的不满足上述约束

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v; 
bool isok(int wolf1,int wolf2){
	//wolf1假话，wolf2真话 
	//-v[wolf1] v[wolf2]
	if(abs(v[wolf1])==abs(v[wolf2])&&v[wolf1]==v[wolf2]){
		return false;//一定是相互矛盾的话 
	}else if(v[wolf2]==wolf1||v[wolf2]==wolf2||-v[wolf1]==wolf2||-v[wolf1]==wolf1){
		return false;
	} 
	//这是两句真话 
	int t1= -v[wolf1];
	int t2= v[wolf2];
	if(t1<0&&t1!=-wolf1&&t1!=-wolf2)return false;
	if(t2<0&&t2!=-wolf1&&t2!=-wolf2)return false;
	int cnt=0;//记录说假话的次数 
	for(int i=1;i<=n;i++){
		if(i==wolf1||i==wolf2){
			continue;
		}
		if(v[i]==-t1||v[i]==-t2){
			cnt++;
			//printf("isok:1假话%d\n",i);
			continue;
		}
		
		if(v[i]<0){
			if(v[i]!=-wolf1&&v[i]!=-wolf2){
				//printf("isok:2假话%d\n",i);
				cnt++;
			}
		}else{
			if(v[i]==wolf1||v[i]==wolf2){
				//printf("isok:3假话%d\n",i);
				cnt++;
			}
		}
	}
	if(cnt==1)return true;
	return false;
}
int main(){
	//两个狼人，一个狼人说假话，一个人说假话
	scanf("%d",&n);
	v.resize(n+1);
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);
	}
	int ans1=-1,ans2=-1;
	for(int i=1;i<n;i++){
		ans1=i;
		for(int j=i+1;j<=n;j++){
			if(isok(i,j)){
				ans2=j;
				//printf("真话：%d 假话:%d\n",j,i);
				break;
			}else if(isok(j,i)){
				ans2=j;
				//printf("真话：%d 假话:%d\n",i,j);
				break;
			} 
		} 
		if(ans2>0){
			break;
		}
	}
	if(ans1>0&&ans2>0){
		printf("%d %d",ans1,ans2);
	}else{
		printf("No Solution");
	}
	return 0;
}

2.2 第二题

图论的一道题目，会卡时间、卡内存，简单优化一下即可

首先对于所有存在冲突的编号进行存储，之后遍历的时候遇到非冲突编号直接跳过，降低时间复杂度
其次，不可以用二阶矩阵存储，内存会爆，这里用map<int,vector<int> >邻接列表降低内存

#include<bits/stdc++.h>
using namespace std;
map<int,vector<int> >mp;
map<int,bool>exist;
int n,m;
int num;
vector<int>v;
int a,b;
bool isADJ(int x,int y){
	for(int i=0;i<mp[x].size();i++){
		//printf("x=%d,map[%d]临边%d\n",mp[x][i]);
		if(mp[x][i]==y)return true;
	}
	return false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d%d",&a,&b);
		exist[a]=true;
		exist[b]=true;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	for(int i=0;i<m;i++){
		scanf("%d",&num);
		v.resize(num);
		for(int j=0;j<num;j++){
			scanf("%d",&v[j]);
		}
		bool flag=true;
		for(int j=0;j<num;j++){
			if(!exist[v[j]])continue;
			for(int k=j+1;k<num;k++){
				if(!exist[v[k]])continue;
				if(isADJ(v[j],v[k])){
					printf("No\n");
					flag=false;
					break;
				}
			}
			if(!flag)break;
		}
		if(flag){
			printf("Yes\n");
		}
		v.clear(); 
	}
	return 0;
}

2.3 第三题

2.4 第四题

这题和之前做得一道很相似见1143题解，属于变式了😜

exam1：18/30建立树，然后搜索，为了简化时间复杂度用了temp存储中间建立树的时候的父节点们，但是……内存超限了😅😅

exam2：AC借鉴了之前的做法，直接数组开刷,不需要建立树，只需要根据in中序遍历的数组求得每个结点的优先顺序，然后遍历pre数组，当遍历到的数组结点temp在a,b中间（这里的中间是指temp在in数组的相对位置在a,b之间）时候即可跳出循环，为LCA

exam1:18/30

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>in;
vector<int>pre;
map<int,vector<int> >father;
map<int,bool>exist;
int a,b;
struct Node{
	int val;
	Node* left;
	Node*right;
};
vector<int>temp;
Node *build(int inL,int inR,int preL,int preR){
	if(inR<inL){
		return NULL;
	}
	int val=pre[preL];
	Node *root=new Node;
	root->val=val;
	//给每个结点添加父节点的 
	temp.push_back(val);
	father[val]=temp;
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==val){
			break;
		}
	}
	int left_num=k-inL;//左边的数量
	vector<int>ctemp;
	ctemp=temp;
	root->left=build(inL,k-1,preL+1,preL+left_num);
	temp=ctemp;
	root->right=build(k+1,inR,preL+left_num+1,preR);
	return root; 
}
int main(){
	scanf("%d%d",&m,&n);
	in.resize(n);
	pre.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&in[i]);
		exist[in[i]]=true;//出现了某个结点 
	}
	for(int i=0;i<n;i++){
		scanf("%d",&pre[i]);
	}
	Node *root=NULL;
	root=build(0,n-1,0,n-1); 
	//检验
//	for(int i=0;i<n;i++){
//		printf("子节点%d:",in[i]);
//		for(int j=0;j<father[in[i]].size();j++){
//			printf("%d ",father[in[i]][j]);
//		}
//		printf("\n");
//	} 
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		if(!exist[a]){
			if(exist[b]){
				printf("ERROR: %d is not found.\n",a);
			}else{
				printf("ERROR: %d and %d are not found.\n",a,b);
			}
		}else{
			if(exist[b]){
				//搜索 
				int an;
				int lena=father[a].size();
				int lenb=father[b].size();
				for(int i=min(lena,lenb)-1;i>=0;i--){
					if(father[a][i]==father[b][i]){
						an=father[a][i];
						break;
					}
				}
				if(an==a){
					printf("%d is an ancestor of %d.\n",an,b);
				}else if(an==b){
					printf("%d is an ancestor of %d.\n",an,a);
				}else{
					printf("LCA of %d and %d is %d.\n",a,b,an);
				}
			}else{
				printf("ERROR: %d is not found.\n",b);
			}
		}
	}
	return 0;
}

exam2:30/30

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a,b;
vector<int>in;
vector<int>pre;
map<int,int>order;
map<int,bool>exist;
int main(){
	scanf("%d%d",&m,&n);
	in.resize(n);
	pre.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&in[i]);
		order[in[i]]=i;
		exist[in[i]]=true;
	}
	for(int i=0;i<n;i++){
		scanf("%d",&pre[i]);
	}
	while(m--){
		scanf("%d%d",&a,&b);
		if(!exist[a]){
			if(exist[b]){
				printf("ERROR: %d is not found.\n",a);
			}else{
				printf("ERROR: %d and %d are not found.\n",a,b);
			}
		}else{
			if(exist[b]){
				//搜索 
				int an;
				for(int i=0;i<n;i++){
					int temp=pre[i];
					if(order[temp]<order[a]&&order[temp]>order[b]||order[temp]<order[b]&&order[temp]>order[a]){
						an=temp;
						break;
					}else if(temp==a||temp==b){
						an=temp;
						break;
					}
				}
				if(an==a){
					printf("%d is an ancestor of %d.\n",an,b);
				}else if(an==b){
					printf("%d is an ancestor of %d.\n",an,a);
				}else{
					printf("LCA of %d and %d is %d.\n",a,b,an);
				}
			}else{
				printf("ERROR: %d is not found.\n",b);
			}
		}
	}
	return 0;
}