甲级模拟第五d：1148-1151

title: PTA甲级模拟1148-1151
date: 2022-01-31 10:42:36
categories:

算法与数据结构
tags:编程练习PTA

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

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

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

#include
using namespace std;
int n;
vectorv; 
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假话%dn",i);
			continue;
		}
		
		if(v[i]<0){
			if(v[i]!=-wolf1&&v[i]!=-wolf2){
				//printf("isok:2假话%dn",i);
				cnt++;
			}
		}else{
			if(v[i]==wolf1||v[i]==wolf2){
				//printf("isok:3假话%dn",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;i0){
			break;
		}
	}
	if(ans1>0&&ans2>0){
		printf("%d %d",ans1,ans2);
	}else{
		printf("No Solution");
	}
	return 0;
} 

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

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

#include
using namespace std;
map >mp;
mapexist;
int n,m;
int num;
vectorv;
int a,b;
bool isADJ(int x,int y){
	for(int i=0;i 
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
using namespace std;
int n,m;
vectorin;
vectorpre;
map >father;
mapexist;
int a,b;
struct Node{
	int val;
	Node* left;
	Node*right;
};
vectortemp;
Node *build(int inL,int inR,int preL,int preR){
	if(inRval=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;//左边的数量
	vectorctemp;
	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=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
using namespace std;
int n,m;
int a,b;
vectorin;
vectorpre;
maporder;
mapexist;
int main(){
	scanf("%d%d",&m,&n);
	in.resize(n);
	pre.resize(n);
	for(int i=0;iorder[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;
}
 
3. 参考资料 
菜菜子的1143题解订正
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714795.html