算法训练33

编程练习 机考
算法与数据结构
发布日期:   2022-08-01
更新日期:   2022-08-01
文章字数:   2k
阅读时长:   11 分
阅读次数:  

1. 知识点总结

真正考试的话大概封顶80，卡在了第一题……呜呜呜

第一题花了两个小时找bug

2-4题一个半小时AC

论取舍的重要性

题目 难度 知识点
1148 Werewolf - Simple Version 🎯🎯 英语
1149 Dangerous Goods Packaging 🎯 STL
1150 Travelling Salesman Problem 🎯 图论
1151 LCA in a Binary Tree 🎯🎯 二叉树+层次遍历+STL

2. 分题题解

2.1 PAT 1148 Werewolf - Simple Version

Werewolf（狼人杀） is a game in which the players are partitioned into two parties: the werewolves and the human beings. Suppose that in a game,

  • player #1 said: “Player #2 is a werewolf.”;
  • player #2 said: “Player #3 is a human.”;
  • player #3 said: “Player #4 is a werewolf.”;
  • player #4 said: “Player #5 is a human.”; and
  • player #5 said: “Player #4 is a human.”.

Given that there were 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liars. Can you point out the werewolves?

Now you are asked to solve a harder version of this problem: given that there were N players, with 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liars. You are supposed to point out the werewolves.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (5≤N≤100). Then N lines follow and the i-th line gives the statement of the i-th player (1≤i≤N), which is represented by the index of the player with a positive sign for a human and a negative sign for a werewolf.

Output Specification:

If a solution exists, print in a line in ascending order the indices of the two werewolves. The numbers must be separated by exactly one space with no extra spaces at the beginning or the end of the line. If there are more than one solution, you must output the smallest solution sequence – that is, for two sequences A=a[1],…,a[M] and B=b[1],…,b[M], if there exists 0≤k<M such that a[i]=b[i] (i≤k) and a[k+1]<b[k+1], then A is said to be smaller than B. In case there is no solution, simply print No Solution.

最关键的在于读懂题目……卡了两个小时在一个测试点，就是因为对于划线句子理解不到位,我一直以为分两只狼说谎和一狼一人说谎两种情况（英语理解属实……）

解题思路：

假设两个狼的编号的基础上，要求满足

  • 只有一只狼说谎
  • 只有一个人说谎
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>say;//陈述 
bool flag=false;
//14分 
bool isSolution(int a,int b){
	//a,b是两只狼 
	vector<int>liar;
	for(int i=1;i<=N;i++){
		if(say[i]>0&&(say[i]==a||say[i]==b)){
			liar.push_back(i);
		}
		if(say[i]<0&&!(-say[i]==a||-say[i]==b)){
			liar.push_back(i);
		}
	}
	//首先说谎的人要有两个，其次狼需要有一个说谎 
	if(liar.size()==2){
		int cnt=0;
		if(find(liar.begin(),liar.end(),a)!=liar.end()){
			cnt++;
		}
		if(find(liar.begin(),liar.end(),b)!=liar.end()){
			cnt++;
		}
		if(cnt==1){
			return true;
		}
	}
	return false;
}
int main(){
	scanf("%d",&N);
	say.resize(N+1);
	for(int i=1;i<=N;i++){
		scanf("%d",&say[i]);
	}
	//遍历去找答案
	for(int i=1;i<=N;i++){
		for(int j=i+1;j<=N;j++){
			if(isSolution(i,j)){
				flag=true;
				printf("%d %d",i,j);
				return 0;
			}
		}
	} 
	printf("No Solution");
	return 0;
}

2.2 PAT 1149 Dangerous Goods Packaging

有点卡时间，建议先找对应的id是否在 incompatible goods编号中，再进行关系探查

#include<bits/stdc++.h>
using namespace std;
int N;
int M;
int K;
vector<int>g;
map<int,vector<int>>mp;
int a,b;
int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++){
		scanf("%d%d",&a,&b);
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	while(M--){
		scanf("%d",&K);
		g.resize(K);
		for(int i=0;i<K;i++){
			scanf("%d",&g[i]);
		}
		//判断
		bool flag=true;
		for(int i=0;i<K;i++){
			if(mp.find(g[i])==mp.end()){
				continue;
			}
			for(int j=i+1;j<K;j++){
				if(find(mp[g[i]].begin(),mp[g[i]].end(),g[j])!=mp[g[i]].end()){
					printf("No\n");
					flag=false;
					break;
				}
			}
			if(!flag)break;
		}
		if(flag)printf("Yes\n");
	}
	return 0;
}

2.3 PAT 1150 Travelling Salesman Problem

简单图论，需要理解一下TS的含义，考察英文阅读理解水平

#include<bits/stdc++.h>
using namespace std;
int N,M;//点的个数，边的个数 
const int inf=INT_MAX;
int K;
int n;
vector<vector<int>>graph;
vector<int>C; 
int u,v,d;
int isCircle(){
	int dist=0;
	for(int i=1;i<n;i++){
		if(graph[C[i]][C[i-1]]==inf){
			return -inf;
		}else{
			dist+=graph[C[i]][C[i-1]];
		}
	}
	if(C[0]!=C[n-1]){
		return -dist;
	}
	return dist;
}
int ans=inf;
int id=0;
int main(){
	scanf("%d%d",&N,&M);
	graph.resize(N+1);
	for(int i=1;i<=N;i++){
		graph[i].resize(N+1);
		fill(graph[i].begin(),graph[i].end(),inf);
	}
	for(int i=0;i<M;i++){
		scanf("%d%d%d",&u,&v,&d);
		graph[u][v]=min(graph[u][v],d);
		graph[v][u]=min(graph[v][u],d);
	}
	scanf("%d",&K);
	for(int x=1;x<=K;x++){
		scanf("%d",&n);
		C.resize(n);
		set<int>cnt;
		for(int i=0;i<n;i++){
			scanf("%d",&C[i]);
			cnt.insert(C[i]);
		} 
		//首先判断是不是一个圈
		int dist=isCircle();
		int vis_num=cnt.size();
		printf("Path %d: ",x);
		if(dist>=0&&vis_num==N&&n-1==N){
			printf("%d (TS simple cycle)\n",dist);
			if(dist<ans){
				ans=dist;
				id=x;
			}
		}else if(dist>=0&&vis_num==N&&n-1>N){
			printf("%d (TS cycle)\n",dist);
			if(dist<ans){
				ans=dist;
				id=x;
			}
		}else{
			if(dist!=-inf){
				printf("%d (Not a TS cycle)\n",abs(dist));
			}else{
				printf("NA (Not a TS cycle)\n");
			}
		}
	}
	printf("Shortest Dist(%d) = %d",id,ans);
	return 0;
}

2.4 PAT 1151 LCA in a Binary Tree

看上去代码量大，实际上都是基础的模板运用。

个人认为是用空间换时间的题目，从根节点到每条结点的路径需要存map中，用val索引，否则最后两个测试点会超时.

  • 首先，pre+in序列构建二叉树
  • 接着层次遍历获取结点的parent信息
  • 对于每次询问，先查找结点是否存在，再判断节点之间是否有直接的parent-child关系
  • 否则比较两个结点的path,找到最后一个相同的后缀输出
#include<bits/stdc++.h>
using namespace std;
int M,N;//关系，结点
vector<int>in,pre; 
struct Node{
	Node*parent=NULL;
	Node*left=NULL;
	Node*right=NULL;
	int val;
};
Node*build(int inL,int inR,int preL,int preR){
	if(inL>inR||preL>preR||inL<0||inR>=N||preL<0||preR>=N){
		return NULL;
	}
	Node* root=new Node;
	root->val=pre[preL];
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==root->val){
			break;
		}
	}
	int num=k-inL;
	root->left=build(inL,k-1,preL+1,preL+num);
	root->right=build(k+1,inR,preL+num+1,preR);
	return root;
}
map<int,Node*>mp;
map<int,vector<int>>path;
void levelTravel(Node*root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		mp[top->val]=top;
		//printf("@%d\n",top->val);
		if(top->left!=NULL){
			top->left->parent=top;
			q.push(top->left);
		}
		if(top->right!=NULL){
			top->right->parent=top;
			q.push(top->right);
		}
		q.pop();
	}
}
int u,v;
int main(){
	scanf("%d%d",&M,&N);
	in.resize(N);
	pre.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&in[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&pre[i]);
	}
	Node*root=build(0,N-1,0,N-1);
	levelTravel(root);
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		if(find(in.begin(),in.end(),u)==in.end()){
			if(find(in.begin(),in.end(),v)==in.end()){
				printf("ERROR: %d and %d are not found.\n",u,v);
			}else{
				printf("ERROR: %d is not found.\n",u);
			}
		}else if(find(in.begin(),in.end(),v)==in.end()){
			printf("ERROR: %d is not found.\n",v);
		}else{
			//找到u,v的共同祖先
			if(mp[u]->parent!=NULL&&mp[u]->parent->val==v){
				printf("%d is an ancestor of %d.\n",v,u);
				continue;
			}else if(mp[v]->parent!=NULL&&mp[v]->parent->val==u){
				printf("%d is an ancestor of %d.\n",u,v);
				continue;
			}
			vector<int>path1,path2;
			int p;
			if(path.find(u)!=path.end()){
				path1=path[u];
			}else{
				p=u;
				path1.push_back(p);
				while(mp[p]->parent!=NULL){
					p=mp[p]->parent->val;
					path1.push_back(p);
				}
				reverse(path1.begin(),path1.end()); 
				path[u]=path1;
			}
			if(path.find(v)!=path.end()){
				path2=path[v];
			}else{
				p=v; 
				path2.push_back(p);
				while(mp[p]->parent!=NULL){
					p=mp[p]->parent->val;
					path2.push_back(p);
				}
				reverse(path2.begin(),path2.end());
				path[v]=path2;
			}
			int ans=0;
			for(int i=0;i<min(path1.size(),path2.size());i++){
				ans=path1[i];
				if(path1[i]!=path2[i]){
					if(i)ans=path1[i-1];
					break;
				}
			} 
			if(ans==u){
				printf("%d is an ancestor of %d.\n",u,v);
			}else if(ans==v){
				printf("%d is an ancestor of %d.\n",v,u);
			}else{
				printf("LCA of %d and %d is %d.\n",u,v,ans);
			}
		}
	}
	return 0;
}

3. 参考资料

无

文章作者: Gao
文章链接: https://ghy0202.github.io/2022/08/01/suan-fa-xun-lian-33/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Gao !
编程练习 机考
赏
评论
  目录