PAT Autumn 2021
Eva.Q Lv9
2021-09-25 02:03:55

刚Co老师打游戏，他说：“不试试，真的不知道自己其实还是挺厉害的。”

确实，不试试，真的不知道也许以后还是有机会的吧。

前情

大概就是为了检验跟Co老师学习了几天的学习成果，和Co老师一起去传媒考了PAT。Co老师是 Top Level ，我是 Advanced Level 。Co老师满分了，但我只有63分。（虽然好像Co老师甲级也拿不到满分，因为第一题太坑了）但Co老师给我的两个目标还真就勉勉强强达到了：

  1. 做出两道题
  2. 及格

题目

Arrays and Linked Lists

20分的题目，我只拿了13分。后来发现读错了题意……这题有一个坑点，后面会具体提到。

题意

对于数组 ，有 个元素，起始地址为 。每次一个询问 ，询问的是数组中下标为 的元素（即 ）的地址。题目会给几组数组，且分别给定每个数组的起始地址。

例如，题目给了两个数组 和 。如果 （因为数组下标从 开始，所以是小于号），则返回 ；如果 且 ，则返回 ；如果 ，则输出Illegal Access。

对于每次询问需要输出地址。且在最后打印有多少个数组被声明。

扫盲

！！！被声明！！！！

需要注意的是，如果我们询问的区间包含了第 个数组，那么它和它前面所有的数组都是被声明过的。我考试的时候以为是询问涉及到了几个数组，最后就输出几。（这都有13分……）

还有一个坑点，就是如果每次访问都是非法的，最后输出的不是 ，而是 。

注意到这些坑点，这道题也没那么难了。

代码
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
#include <bits/stdc++.h>
#define N 1000007
using namespace std;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int a[N], bl[N], sum, ans = 1;

int main() {
    int n = rd();
    int m = rd();
    for (int i = 1; i <= n; ++i) {
        int ad = rd();
        int len = rd();
        for (int j = 0; j < len; ++j, ++sum) {
            a[sum] = ad + j * 4; bl[sum] = i; 
        }
    }
    for (int i = 1; i <= m; ++i) {
        int x = rd();
        if (x >= sum) {puts("Illegal Access"); continue;}
        printf("%d\n", a[x]);
        ans = max(ans, bl[x]);
    }
    printf("%d\n", ans);
    return 0;
}
Stack of Hats
题意

一摞帽子，帽子各有大小，从下到上给出各帽子的大小。一群人，编号从 到 ，每一个人需要按体重分配一顶帽子。

输出帽子从上到下所配对的人的编号。

思路

我也不知道这题在考什么……瞎做。就排序，疯狂排序。

开两个结构体数组，一个是帽子的，一个是人的。结构体里三个值，id 代表编号。帽子的编号最初代表上下关系，因为最后输出需要按帽子从上到下的顺序，把最下面的帽子编号为 ，最上面的编号为 ，后面存储了与它相对应的人的编号。number 代表排序后所在的位置。 value 对于帽子来说就是大小，对于人来说就是体重。

先把两个结构体数组都按 value 值排序，记录 number ，对于帽子数组，还需再按 id 排序过。然后将帽子与人进行匹配，将人的 id 存储到帽子数组的 id 。最后按相应的顺序进行输出。

代码
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
#include <bits/stdc++.h>
#define N 10007
using namespace std;

int n, k, num = 0;

struct node{
	int number;
	int id;
	int value;
}hat[N], person[N];

inline int rd(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}

bool cmp1(node a, node b){
	return a.value > b.value;
}

bool cmp2(node a, node b){
	return a.id < b.id;
}
int main(){
	n = rd();
	for(int i = 1; i <= n; ++i){
		hat[i].id = i;
		hat[i].value = rd();
	}
	sort(hat + 1, hat + n + 1, cmp1);
	for(int i = 1; i <= n; ++i) hat[i].number = i;
	sort(hat + 1, hat + n + 1, cmp2);
	for(int i = 1; i <= n; ++i){
		person[i].id = i;
		person[i].value = rd();
	}
	sort(person + 1, person + n + 1, cmp1);
	for(int i = 1; i <= n; ++i) person[i].number = i;
	for(int i = n; i > 0; --i){
		for(int j = 1; j <= n; ++j){
			if(person[j].number == hat[i].number){
				hat[i].id = person[j].id;
				break;
			}
		}
	}
	printf("%d",hat[n].id);
	for(int i = n - 1; i > 0; --i){
		printf(" %d", hat[i].id);
	}
	return 0;
}
Playground Exploration
题意

一个无向图有 个点， 条边。每次选择与当前点相连的点中编号最小的点进行移动，且每个点只能访问一次。问从哪个点开始移动，可到达的点数最多。输出这个点和可到达的点数。

思路

本来是想用邻接表存图的，但如果用邻接表我不知道怎么排序选择编号最小的点移动。 也不大，所以就用邻接矩阵了。

因为每个点只能走一次，故用 vis 数组打标记。mxlen 存储最后的答案。枚举起点，dfs 计算路径长度。

代码
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
#include <bits/stdc++.h>
#define N 107
using namespace std;

int n, m, mxlen, ans, vis[N], mx;

int a[N][N];

int rd(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}

int dfs(int x, int len){
    if(mx < len) mx = len;
	vis[x] = 1;
	for(int i = 1; i <= n; ++i){
        if(!vis[i] && a[x][i] == 1) dfs(i, len + 1);
    }
    return mx;
}

int main(){
	n = rd(); m = rd();
	for(int i = 1; i <= m; ++i){
		int u = rd(), v = rd();
		a[u][v] = 1;
        a[v][u] = 1;
	}
	for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j) vis[j] = 0;
        mx = 0;
		int t = dfs(i, 1);
		if(t > mxlen){
			mxlen = t;
			ans = i;
		}
	}
	printf("%d %d", ans, mxlen);
	return 0;
}
Sorted Cartesian Tree
题意

每个结点有两个值。 key 和 priority 。要求建一棵树满足以下条件：

  1. 对于 priority 来说，这棵树是一个小顶堆。
  2. 对于 key 来说，中序遍历得到的序列是增序。

最后输出这一棵树的层次遍历，第一行是对应的 key 第二行是对应的 priority 。

思路

这就是我0分的题……

考试的时候连题目都没看懂…… 大概就是排序什么的，但没看懂是个什么顺序，考完试Co老师说这是顶级的第一题。

首先根据要求 1，对于这棵树和这棵树的每一个子树来说，priority 最小的点一定是根。再根据要求 2，我们可以根据根的值，确定剩下的点在根的左子树上还是右子树上，这就是 divide 函数的作用。

层次遍历其实就是 bfs 可以借助一个队列完成。

温馨小提示：访问 vector 里面的东西可以用 [] 。

代码
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
#include <bits/stdc++.h>
#define N 37
using namespace std;

inline int rd(){	
	int x = 0;
	bool f = 0;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) f |= (c == '-');
	for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? -x : x;
}

struct node{
	int k, p;
}a[N];

int ls[N], rs[N];

int divide(vector<int> s){
	if(s.empty()) return -1;
	int root = s[0];
	for(auto i : s) 
		if(a[i].p < a[root].p) root = i;
	vector<int> l, r;
	for(auto i : s)
		if(i == root) continue;
		else a[i].k < a[root].k ? l.push_back(i): r.push_back(i);
	ls[root] = divide(l);
	rs[root] = divide(r);
	return root;
}

vector<int> id;

int main(){
	int n = rd();
	vector<int> s;
	for(int i = 1; i <= n; ++i){
		a[i].k = rd(); a[i].p = rd();
		s.push_back(i);
	}
	int Root = divide(s);
	queue<int> q;
	q.push(Root);
	while(!q.empty()){
		int t = q.front();
		q.pop();
		if(ls[t] != -1) q.push(ls[t]);
		if(rs[t] != -1) q.push(rs[t]);
		id.push_back(t);
	}
	printf("%d", a[id[0]].k);
	for(int i = 1; i < n; ++i) printf(" %d", a[id[i]].k);
	printf("\n%d", a[id[0]].p);
	for(int i = 1; i < n; ++i) printf(" %d", a[id[i]].p);
	return 0;
}

彩蛋

因为Co老师比我早出考场大概两个小时，所以有时间去拍拍浙传，而我就只配盗图了。

  • Post title：PAT Autumn 2021
  • Post author：Eva.Q
  • Create time：2021-09-25 02:03:55
  • Post link：https://qyy/2021/09/25/Algorithm/PAT2021Autumn/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.