Lemon-XQ

记 2018.9.8 PAT甲级+题解

写在前面

  前两天考完就想写了,结果一直拖到现在orz……8月中旬的时候无意中看到PAT这个东东,因为刚好在准备保研,要复习机试的东西,就报了这个,虽然之前有接触过一点点ACM,不过个人对这种数据结构算法一直都不是特别擅长,准备了半个多月,每天都在刷题总结复习中度过,直到考完才感觉松了一口气,放一下分数和排名吧=w=(虽然感觉可以考的更好,不过也还算满意啦)

分数:91/100

排名:78/2237

感受

这次PAT考试有几个特点:

  1. 放宽了时间限制,也就是说完全暴力也可以AC……
  2. 第一道题逻辑难,据说是顶级30分题?太打击了,反正我一开始就没思路(当时以为不能暴力…)
  3. STL、DFS太重要了……
      考试一共是3个小时,考前几次模拟我都是第一道题15min左右,第二、三道30min左右,最后一道视情况(30min-1h),不过这次考试显然有点特殊,第一道狼人杀就把我打击到了,10几分钟都没有思路,只能先放着,跳到第二道,二、三都不是很难,1h左右跑通两道,提交的时候有一道错了一个3分的测试点,没管,直接看最后一道= =(考完发现那个错误其实很低级。。)
      最后一道是LCA,考试前做了一道LCA的,是针对BST的,BST的LCA很容易找,但是考试要求求的是普通二叉树的LCA,一开始一直想的是各种先后序层序遍历序列找,试了快一个小时都没成功,最后换成DFS,10minAC……
      做完三道只剩半个小时了,回去看那道狼人杀,试了10min连样例都跑不通QAQ内心一直想放弃,突然灵光一现(?)改了一种半暴力的方法,居然跑通样例了,这时只剩5min了,赶紧提交,居然只错了一个测试点,不过剩下的时间也不够了,就这样结束了我的第一次(也是最后一次)PAT考试@_@

一些建议

  1. 考纲里的每个点都要掌握!数据结构主要是队列、栈、链表、树、图,算法主要是最短路、DFS、BFS那些
  2. 考前一个月每天都要保持题量和题感,最好是把题库里的都做一遍!
  3. 每次遇到不会的题不要一下子就去网上找题解,一般2h想不出的我才会去看看别人的思路,然后看看自己是哪里想错了,进行改进,不要直接copy代码!
  4. 确定考场后要第一时间确定考场提供的IDE是哪些,确保有自己熟悉的IDE,没有的话最好提前一个月更换IDE进行练习(比如我之前一直是用C-Free的,邮件问了考场老师才知道考场没有C-Free,只有Dev-C++…),不然就会像考场里很多同学一样,花了不少时间在熟悉IDE上……

题解

说了这么多,放一下本次考试题解吧(对应PAT题库1148-1151),均是可以AC的

  1. 第一题狼人杀,题意就是给出N个人的叙述,N个人中有两个狼人(1个撒谎1个不撒谎),而所有人中撒谎的只有两个,也就是说最终有一个撒谎的狼人和一个撒谎的村民,因此可以直接暴力枚举所有狼人组合,对每一个狼人组合,统计撒谎的狼人数和撒谎的村民数,如果都为1说明找到答案,如果枚举所有组合后都找不到答案,说明无解。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include <iostream>
    #include <algorithm>

    using namespace std;

    int main(){
    int N;
    cin>>N;
    int arr[N+1];
    for(int i=1;i<=N;i++) cin>>arr[i];
    bool flag=false;
    int a,b;
    // 列举每一种狼人组合
    for(int i=1;i<=N;i++){
    for(int j=i+1;j<=N;j++){
    int lie_wolf=0,lie_human=0;
    for(int k=1;k<=N;k++){// 判断该狼人组合下是否满足1个撒谎的狼人+1个撒谎的村民
    if(k==i || k==j){// 狼人
    if(arr[k]>0 && arr[k]==i || arr[k]==j) lie_wolf++;
    else if(arr[k]<0 && abs(arr[k])!=i && abs(arr[k])!=j) lie_wolf++;
    }else{// 村民
    if(arr[k]>0 && arr[k]==i || arr[k]==j) lie_human++;
    else if(arr[k]<0 && abs(arr[k])!=i && abs(arr[k])!=j) lie_human++;
    }
    }
    if(lie_wolf==1 && lie_human==1){
    a=i;
    b=j;
    flag=true;
    break;
    }
    }
    if(flag) break;
    }
    if(flag) cout<<a<<" "<<b<<endl;
    else cout<<"No Solution"<<endl;
    return 0;
    }

2.第二题题意是给出一些危险物配对,比如A和B不能一起出现,B和C不能一起出现(但A和C可以一起出现,所以不是并查集问题),求所给序列中有没有危险物。思路也很简单,直接暴力遍历序列,找有没有危险匹配即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXV=100001;
vector<int> m[MAXV];// 存储每个物品对应的危险物品列表

int main(){
int N,M;
cin>>N>>M;
for(int i=0;i<N;i++){
int a,b;
cin>>a>>b;
m[a].push_back(b);
m[b].push_back(a);
}
for(int i=0;i<M;i++){
int K;
cin>>K;
int arr[K];
bool flag=true;
for(int j=0;j<K;j++) cin>>arr[j];
for(int j=0;j<K-1;j++){// 从前到后暴力比较
for(int k=j+1;k<K;k++){
if(find(m[arr[j]].begin(),m[arr[j]].end(),arr[k])!=m[arr[j]].end()){
flag=false;
break;
}
}
if(!flag)break;
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

3.第三题是售货商问题。不过这道题不需要去求解,只需要判断所给序列是不是满足条件即可,思路也很简单,先判断路径是否连通,不连通就输出“Not a TS cycle”,连通的话再判断序列是否包含了全部结点且首尾结点相同,是则为TS cycle或TS simple cycle,二者可以通过序列长度进行判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const int INF=0x3fffffff;
const int MAXV=201;
int G[MAXV][MAXV];

int main(){
int N,M,K;
cin>>N>>M;
fill(G[0],G[0]+MAXV*MAXV,-1);
for(int i=0;i<M;i++){
int a,b,dis;
cin>>a>>b>>dis;
G[a][b]=G[b][a]=dis;
}
cin>>K;
int ans_index,ans_len=INF;
for(int i=1;i<=K;i++){
int n;
cin>>n;
int path[n],len=0;
bool flag=true;
set<int> s;
for(int j=0;j<n;j++){
cin>>path[j];
s.insert(path[j]);
}
for(int j=0;j<n-1;j++){
if(G[path[j]][path[j+1]]==-1){
flag=false;// 说明所给路径不连通
break;
}else len+=G[path[j]][path[j+1]];// 路径总长度
}
if(flag){
if(s.size()!=N || path[0]!=path[n-1]){
printf("Path %d: %d (Not a TS cycle)\n",i,len);
}else{
if(len<ans_len){// TS cycle 记录最短路径长度及路径编号
ans_len=len;
ans_index=i;
}
if(s.size()==n-1) printf("Path %d: %d (TS simple cycle)\n",i,len);
else printf("Path %d: %d (TS cycle)\n",i,len);
}
}
else printf("Path %d: NA (Not a TS cycle)\n",i);
}
printf("Shortest Dist(%d) = %d",ans_index,ans_len);
return 0;
}

4.最后一题是LCA问题。要求找二叉树中任两个结点的最小公共祖先结点。我的思路是先建树,然后对两个结点进行dfs,求出根节点到这两个结点的路径,对两条路径从头到尾比较,出现的第一个不同的结点则退出循环,该结点的前一个结点就是它们的LCA(比如:3结点的路径是1->5->3,4结点的路径是1->5->4,则它们的LCA为5),如果没有出现不同的结点说明二者是包含关系,根据两条路径长度可以判断谁是祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int MAXV=10001;

struct node{
node* lchild;
node* rchild;
int data;
node(){
lchild=rchild=NULL;
}
};

int in[MAXV],pre[MAXV];
map<int,int> m;
node* create(int preL,int preR,int inL,int inR){
if(preL>preR) return NULL;
node* root=new node;
root->data=pre[preL];
int i;
for(i=inL;i<=inR;i++){
if(in[i]==pre[preL]) break;
}
int len=i-inL;
root->lchild=create(preL+1,preL+len,inL,i-1);
root->rchild=create(preL+len+1,preR,i+1,inR);
return root;
}

vector<int> path,ans;
bool flag=false;
void dfs(node* root,int v){
if(root==NULL) return;
if(root->data==v){
flag=true;
path.push_back(root->data);
ans=path;
path.pop_back();
return;
}else{
path.push_back(root->data);
dfs(root->lchild,v);
if(flag) return;
path.pop_back();
path.push_back(root->data);
dfs(root->rchild,v);
if(flag) return;
path.pop_back();
}
}

int main(){
int M,N;
cin>>M>>N;
for(int i=0;i<N;i++){
cin>>in[i];
m[in[i]]=i;// 记录某个结点是否出现过
}
for(int i=0;i<N;i++) cin>>pre[i];
node* root=create(0,N-1,0,N-1);// 根据先序中序序列建树
for(int i=0;i<M;i++){
int u,v;
cin>>u>>v;
if(m.count(u)==0 && m.count(v)==0) printf("ERROR: %d and %d are not found.\n",u,v);
else if(m.count(u)==0) printf("ERROR: %d is not found.\n",u);
else if(m.count(v)==0) printf("ERROR: %d is not found.\n",v);
else{
// dfs分别遍历u,v结点,得到两条路径
vector<int> pu,pv;
path.clear();
flag=false;
dfs(root,u);
pu=ans;
path.clear();
flag=false;
dfs(root,v);
pv=ans;
// 找两条路径第一个不同的结点
int j;
for(j=0;j<min(pu.size(),pv.size());j++){
if(pu[j]!=pv[j]) break;
}
if(j!=min(pu.size(),pv.size())) printf("LCA of %d and %d is %d.\n",u,v,pu[j-1]);
else if(pu.size()<pv.size()) printf("%d is an ancestor of %d.\n",u,v);
else printf("%d is an ancestor of %d.\n",v,u);
}
}
return 0;
}
Lemon-XQ wechat
坚持原创技术分享,您的支持将鼓励我继续创作!