天天看點
傳回

PAT(甲)2018年秋季考試題目記錄

7-1 Werewolf - Simple Version 

 這是道邏輯題，沒太做過類似這種的題目，是以不是很擅長，這題卡了我四十分鐘，而且是過掉2，3之後回頭才過掉這題的，但其實想來這題還是很簡單的。

看題目資料不大，而且狼人和人類中分别必有一人說謊，是以兩重循環，每輪假設兩個狼人其他均為人類，然後看他們說的話與對應角色的假設身份是否沖突，如果沖突，那麼就用掉一次該角色陣營的說謊次數，由于每方隻能說謊一次，假如出現了說謊次數不夠，就産生沖突，該種假設肯定不成立；反之，直到最後，沒産生沖突，而且兩陣營的說謊次數必須耗盡，則該假設成立。

#include<bits/stdc++.h>
using namespace std;

int n;
int sp[105];

int main(){
	scanf("%d",&n);
	memset(sp,0,sizeof(sp));
	for(int i = 1; i <= n; ++i)
		scanf("%d",&sp[i]);
	int good, wolf;
	int mark[105];
	for(int i = 1; i < n; ++i){
		for(int j = i+1; j <= n; ++j){//i j wolf
			memset(mark,1,sizeof(mark));
			mark[i] = mark[j] = -1;
			good = wolf = 1;
			int flag = 0;
			for(int k = 1; k <= n; ++k){//sp loop
				int tmp = sp[k], pos = abs(tmp);
				if((tmp > 0 && mark[pos] > 0) || (tmp < 0 && mark[pos] < 0)){
					//buguan
				}
				else{
					if(k == i || k == j){
						if(wolf == 1) wolf--;
						else {
							flag = 1;break;
						}
						
					}
					else{
						if(good == 1) good--;
						else {
							flag = 1;break;
						}
					}
				}
			}
			if(!flag && wolf == 0 && good == 0){
				printf("%d %d",i,j);
				return 0;
			}
				
		}
	}
	printf("No Solution");
	return 0;
}

 7-2 Dangerous Goods Packaging

這題有點意外，竟然用了個map就過了？？？我一開始看着很像虛點并查集，但是畫了畫忘了虛點并查基怎麼寫了，就想先暴力拿分再說，結果就過了。。。

思路簡單明了，将沖突的兩種make_pair作為key存入map中，查詢的時候，前面輸入中沒有出現過的直接忽略，出現過的放入一個vector中，後來者就與所有已經存入的比較是否在map中存在這一對，如果存在就沖突。

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<pair<int,int>, int> mp;
int vis[100005];
int main(){
	scanf("%d%d",&n,&m);
	int a, b;
	for(int i = 0; i < n; ++i){
		scanf("%d%d",&a,&b);
		mp[make_pair(a,b)] = 1;
		mp[make_pair(b,a)] = 1;
		vis[a] = vis[b] = 1;
	}
	int k,num;
	for(int i = 0; i < m; ++i){
		scanf("%d",&k);
		vector<int> list;
		int flag = 1;
		for(int j = 0; j < k; ++ j){
			scanf("%d",&num);
			if(flag == 1){
				if(vis[num] == 1){
				for(int t = 0; t < list.size(); ++t){
					if(mp[make_pair(num,list[t])] == 1){
						flag = 0;
						break;
						}
					}
				if(flag)
					list.push_back(num);
				}
			}
			
		}
		if(flag)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

7-3 Travelling Salesman Problem (圖)

這題更加直白簡單，完全就是個代碼題吧，沒啥好說的。

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100000;
int N, M;
int g[205][205];
void init(){
	for(int i = 0; i < N+2; ++i){
		for(int j = 0; j < N+2; ++j){
			g[i][j] = g[j][i] = MAX;
		}
	}
}
struct Ans{
	int path, dis;
	
	bool operator < (const Ans &a) const{
		return dis < a.dis;
	}
};
vector<Ans> dist;

int main(){
	scanf("%d%d",&N,&M);
	init();
	int a, b, dis;
	for(int i = 0; i < M; ++i){
		scanf("%d%d%d",&a,&b,&dis);
		g[a][b] = g[b][a] = dis;
	}
	int k, n;
	scanf("%d",&k);
	for(int cnt = 1; cnt <= k; ++cnt){
		scanf("%d",&n);
		int tol = 0,origin, pre, cur, flag = 1;
		int vis[N+5];
		memset(vis,0,sizeof(vis));
		scanf("%d",&pre);
		origin = pre;
		vis[pre] = 1;
		for(int i = 1; i < n-1; ++i){
			scanf("%d",&cur);
			if(g[pre][cur] != MAX){
				tol += g[pre][cur];
				vis[cur] += 1;
				pre = cur;
			}
			else flag = -1;
		}
		scanf("%d",&cur);
		if(flag == -1 || cur != origin){//not cycle
			if(flag == -1)
				printf("Path %d: NA (Not a TS cycle)\n",cnt);
			else
				printf("Path %d: %d (Not a TS cycle)\n",cnt,tol+g[pre][cur]);
		}
		else{
			for(int j = 1; j <= N; ++j){
				if(vis[j] == 0){
					flag = -1;
				}
				else if(vis[j] > 1 && flag != -1){
					flag = 2;
				}
			}
			if(flag == -1)
				printf("Path %d: %d (Not a TS cycle)\n",cnt,tol+g[pre][cur]);
			else if(flag == 2){
				printf("Path %d: %d (TS cycle)\n",cnt,tol+g[pre][cur]);
				Ans tmp;
				tmp.path = cnt;
				tmp.dis = tol+g[pre][cur];
				dist.push_back(tmp);
			}
				
			else{
				printf("Path %d: %d (TS simple cycle)\n",cnt,tol+g[pre][cur]);
				Ans tmp;
				tmp.path = cnt;
				tmp.dis = tol+g[pre][cur];
				dist.push_back(tmp);
			}
				
		}
	}
	sort(dist.begin(),dist.end());
	printf("Shortest Dist(%d) = %d\n",dist[0].path,dist[0].dis);
	return 0;
}

 7-4 LCA in a Binary Tree (LCA+中序先序建二叉樹)

其實我至今沒想明白，為什麼我在考場上一個小時沒建出樹來，雖說回來後寫完了建樹的方法，最後沒拿滿分，但是90+是妥妥的，當時出來真的心态崩了，感覺對不起前面三道題的滿分。

這題有兩種方法，一種建立二叉樹，然後搜，我自己沒有想出很好的搜尋的方法，是以最後兩個case超記憶體了，反正網上建樹的方法多得是，不贅述了。

第二種方法就是不建樹，通過中序裡子樹和其根的關系來搞定，代碼簡單，易懂。

我們隻需要控制三個變量：inl（中序的左邊界），inr（中序右邊界），pre_root（先序的根結點位置）

然後會有三種情況：1.u,v在中序裡都在根的左邊或者右邊，這就說明他們必然有下一個公共的根。

                                 2.u,v在中序裡根的兩邊，那麼這個根就是他們的公共根。

                                 3.u或v位置等于目前根的位置，那麼相同位置的就是另一個的根。

LCA的代碼：

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
vector<int> inorder;
vector<int> preorder;
map<int,int> key2pos;
map<int,int> vis;

void lca(int inl, int inr, int pre_root, int u, int v){
	if(inl > inr) return;
	int in_root = key2pos[preorder[pre_root]], uindex = key2pos[u], vindex = key2pos[v];
	if(uindex < in_root && vindex < in_root){//left subtree
		lca(inl,in_root - 1,pre_root+1,u,v);
	}
	else if((uindex < in_root && vindex > in_root) || (uindex > in_root && vindex < in_root)){//in_root is root
		printf("LCA of %d and %d is %d.\n", u, v, inorder[in_root]);
	}
	else if(uindex > in_root && vindex > in_root){//right subtree{
		lca(in_root+1,inr,pre_root+1+in_root-inl,u,v);
	}
	else{
		if(uindex == in_root) printf("%d is an ancestor of %d.\n", u, v);
		else printf("%d is an ancestor of %d.\n", v, u);
	}	
}

int main(){
	scanf("%d%d",&m,&n);
	int a;
	for(int i = 0; i < n; ++i){
		scanf("%d",&a);
		inorder.push_back(a);
		key2pos[a] = i;
		vis[a] = 1;	
	}
	for(int i = 0; i < n; ++i){
		scanf("%d",&a);
		preorder.push_back(a);
	}
	int u, v;
	for(int i = 0; i < m; ++i){
		scanf("%d%d",&u,&v);
		if (!vis[u] && !vis[v])
        {
            printf("ERROR: %d and %d are not found.\n",u,v);
        }
        else
        if (!vis[u])
        {
            printf("ERROR: %d is not found.\n",u);
        }
        else
        if (!vis[v])
        {
            printf("ERROR: %d is not found.\n",v);
        }
        else
        {
        	lca(0,n-1,0,u,v);
        }
	}
	return 0;
}

建樹搜尋的代碼，最後兩個case超記憶體，但主要為了記錄下建樹，防止下回還TM一小時建不出樹：

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
struct Node{
	int h, left, right, data;
	Node(){
	}
	bool operator < (const Node &a) const{
		return h < a.h;
	} 
};
vector<int> inorder;
vector<int> preorder;
Node tree[10005];
map<int,int> vis;
vector<Node> ans;

int build(int prel, int prer, int inl, int inr, int pos, int height){
	if(pos >= n) return -1;
	tree[pos].h = height;
	tree[pos].data = preorder[pos];
	tree[pos].left = tree[pos].right = -1;
	for(int i = inl; i <= inr; ++i){
		if(inorder[i] == preorder[prel]){
			if(i > inl){
				tree[pos].left = build(prel+1,prel+i-inl,inl,i-1,prel+1,height+1);
			}
			if(i < inr){
				tree[pos].right = build(i-inl+prel+1,prer,i+1,inr,i-inl+prel+1,height+1);
			}
		}
	}
	return pos;
}


void finds(int x, int pos, vector<Node> path, int &flag){
	if(x == tree[pos].data){
		path.push_back(tree[pos]);
		ans.insert(ans.end(),path.begin(),path.end());
		flag = 1;
		return;
	}
	if(flag == 1) return;
	path.push_back(tree[pos]);
	if(tree[pos].left != -1)
		finds(x,tree[pos].left,path,flag);
	if(flag == 1) return;
	if(tree[pos].right != -1)
		finds(x,tree[pos].right,path,flag);
	if(flag == 1) return;
}

int main(){
	scanf("%d%d",&m,&n);
	int a;
	for(int i = 0; i < n; ++i){
		scanf("%d",&a);
		inorder.push_back(a);
		vis[a] = 1;	
	}
	for(int i = 0; i < n; ++i){
		scanf("%d",&a);
		preorder.push_back(a);
	}
	build(0,n-1,0,n-1,0,1);
	int u, v;
	for(int i = 0; i < m; ++i){
		scanf("%d%d",&u,&v);
		if (!vis[u] && !vis[v])
        {
            printf("ERROR: %d and %d are not found.\n",u,v);
        }
        else
        if (!vis[u])
        {
            printf("ERROR: %d is not found.\n",u);
        }
        else
        if (!vis[v])
        {
            printf("ERROR: %d is not found.\n",v);
        }
        else
        {
        	int flag = 0;
        	vector<Node> tmp1;
            finds(u,0,tmp1,flag);
            vector<Node> tmp2;
            flag = 0;
            finds(v,0,tmp2,flag);
            sort(ans.begin(),ans.end());
            int res;
            for(int i = 0; i < ans.size(); i += 2){
            	if(i != ans.size()-1 && ans[i].data == ans[i+1].data){
            		res = ans[i].data;
            	}
            }
            if (res == u) printf("%d is an ancestor of %d.\n",u,v);
			else if (res == v) printf("%d is an ancestor of %d.\n",v,u);
			else
            printf("LCA of %d and %d is %d.\n",u,v,res);
            ans.clear();
        }
	}
	return 0;
}

甲級其實完全沒有有難度的算法，大部分考的還是資料結構的基礎，這次在二叉樹上翻了車，想來還是不夠紮實吧，12月一定要拿個高分啊。

樹 PAT 資料結構與算法 圖論 思維 邏輯
上一篇: PAT甲級2020年秋季題目記錄分析（全部AC，簡單易懂）PAT甲級2020年秋季題目記錄分析
下一篇: PAT甲級題目（純C語言）

繼續閱讀