PAT Autumn 2021

Background

某天心血来潮拉上 Eva 同学一起报名了 PAT ~

开学前在 官方题库 里刷了两道题热身!其实是想刷完但是太鸽了

然后就到考试时间啦!借着考试翘掉了半天的军训!好耶!

Solution ( Top Level )

代码写的赶时间,比较丑。

A. Sorted Cartesian tree

给定 $n$ 个 pair<priority, key> ,构建一棵 $n$ 个节点的二叉树,满足:

  • 节点 priority 关键字满足堆的性质,即 priority 父节点小于子节点

  • 节点 key 关键字满足二叉搜索树的性质,即中序遍历 key 单调不降

把树建出来,输出 prioritykeyLevel-order traversal 序列

模拟题意 dfs 建树,传一个 set<node> 即可。

求层序遍历一个 bfs 就够了 考场上写了个dfn+dep双关键字排序

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
#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 ^ 48);
return f ? -x : x;
}

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

inline bool operator < (const node &a, const node &b) {
if (a.p != b.p) return a.p < b.p;
if (a.k != b.k) return a.k < b.k;
return a.id < b.id;
}

int ls[N], rs[N], k[N], p[N];

set<node> S;

int dfs(set<node> s) {
if (s.empty()) return 0;
node nw = *s.begin();
s.erase(nw);
set<node> l, r;
for (auto t : s) {
if (t.k <= nw.k) l.insert(t);
else r.insert(t);
}
ls[nw.id] = dfs(l);
rs[nw.id] = dfs(r);
return nw.id;
}

queue<int> q;

int main() {
int n = rd();
for (int i = 1; i <= n; ++i) {
c[i].id = i; c[i].k = rd(); c[i].p = rd();
S.insert(c[i]);
}
int ptr = 0, rt = dfs(S);
q.push(rt);
while (!q.empty()) {
int u = q.front(); q.pop();
if (ls[u]) q.push(ls[u]);
if (rs[u]) q.push(rs[u]);
k[++ptr] = c[u].k;
p[ptr] = c[u].p;
}
for (int i = 1; i < n; ++i) printf("%d ", k[i]); printf("%d\n", k[n]);
for (int i = 1; i < n; ++i) printf("%d ", p[i]); printf("%d", p[n]);
return 0;
}

B. Unity is Strength

给一张有权无向图,以及若干条可以花 $w_i$ 连接 $u_i,v_i$ 的无向边。

先输出每个联通块的 “块内最小编号 - 块内最小边权” ,按照块大小-最小边权-最小点编号的顺序排序

然后计算把整个图联通的最小代价,除给定边外,任意两点之间都可以花 $10^4$ 的代价连接一条边。

并查集模拟题意即可,第一步求出来每个集合的若干信息,然后排序一下。

之后就是最小生成树,考虑给定边不一定能让整个图联通,最后答案加上(联通块数 $-1$ )$\times 10^4$ 即可。

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
#include <bits/stdc++.h>
#define N 100007
#define inf 1e9
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 f[N], mn[N], mnid[N], sz[N], totr, totc;

struct road {
int u, v, w;
}r[N];

inline bool cmp2(road a, road b) {
return a.w < b.w;
}

inline int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}

inline void merge(int a, int b, int w) {
a = find(a); b = find(b);
if (a == b) {
mn[a] = min(mn[a], w);
return;
}
f[a] = b; sz[b] += sz[a];
mnid[b] = min(mnid[b], mnid[a]);
mn[b] = min(mn[b], min(mn[a], w));
}

struct node {
int mnid, sz, str;
}c[N];

inline bool cmp1(node a, node b) {
if (a.str != b.str) return a.str > b.str;
if (a.sz != b.sz) return a.sz > b.sz;
return a.mnid < b.mnid;
}

int main() {
int n = rd();
int m = rd();
for (int i = 1; i <= n; ++i) {
f[i] = i; mn[i] = inf; mnid[i] = i; sz[i] = 1;
}
for (int i = 1, u, v, w; i <= m; ++i) {
u = rd(); v = rd(); w = rd();
if (w > 0) merge(u, v, w);
else r[++totr] = (road){u, v, -w};
}
for (int i = 1; i <= n; ++i)
if (f[i] == i) c[++totc] = (node){mnid[i], sz[i], (mn[i] == inf ? 0 : mn[i])};
sort(c + 1, c + 1 + totc, cmp1);
for (int i = 1; i < totc; ++i) printf("%d-%d ", c[i].mnid, c[i].str);
printf("%d-%d\n", c[totc].mnid, c[totc].str);
int ans = 0;
sort(r + 1, r + 1 + totr, cmp2);
for (int i = 1; i <= totr; ++i) {
int u = find(r[i].u);
int v = find(r[i].v);
if (u != v) {merge(u, v, r[i].w); ans += r[i].w;}
}
int cnt = 0;
for (int i = 1; i <= n; ++i)
cnt += (f[i] == i);
ans += (cnt - 1) * 10000;
printf("%d", ans);
return 0;
}

C. Manhattan

给定一个序列 ${ a_i }\ (1\le a_i\le 3)$,两个人玩(开始双方均为 $0$ 分),每次某个人取走最靠前的 $a_i$ 加到当前的得分里。

要求每个人拿完之后,当前的得分不得少于对方,问有多少种划分方案,答案 $\mod 10^ 9 + 7$

裸的 DP 就是 f[i][j] 表示当前考虑前 $i$ 个数,第一个人比第二个人多 $j$ 的方案数。

因为 $a_i\le 3$ ,所以如果某个人比另一个人多了超过 $3$ 分,对手就无法满足要求,之后就只能是这个人拿了。

所以 j 可以把特殊的状态放到一起,范围就只有 $9$ 了,复杂度 $O (9n)$ ,转移要注意条件。

实现的时候整体偏移了 $5$ ,也就是 $j=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
#include <bits/stdc++.h>
#define N 100007
#define mod 1000000007
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 f[N][10];

#define add(a,b) a = (a + b) % mod

int main() {
f[0][5] = 1;
int n = rd();
for (int i = 1, x; i <= n; ++i) {
x = rd();
for (int j = 1; j <= 9; ++j) {
if (j - x <= 1) add(f[i][1], f[i - 1][j]);
if (j + x >= 9) add(f[i][9], f[i - 1][j]);
}
for (int j = 2; j <= 8; ++j) {
if (j - x > 1 && j - x <= 5) add(f[i][j - x], f[i - 1][j]);
if (j + x < 9 && j + x >= 5) add(f[i][j + x], f[i - 1][j]);
}
}
int ans = 0;
for (int i = 1; i <= 9; ++i) add(ans, f[n][i]);
printf("%d", ans);
return 0;
}

Summary

比赛之前比较焦虑(毕竟军训一周都没碰键盘),到考场发现左边坐的是学长。

开场把三个题都开了, 题目描述都十分迷惑(英语太差),结合样例枚举题意读题。

分不清:Preorder 先序;Inorder 中序;Postorder 后序;Level-order traversal 层序遍历

过题顺序 T2 - T1 - T3 ,看榜应该是 Rank 2,所有题都是一次过非常舒适。

然后就提前跑路了!因为 Eva 同学还在奋战,我就开始快乐的浙传半日游~

浙传的校园就比较有感觉,总觉得杭电的楼都是一个样子的,缺点大学的气息…

井盖上超级可爱的小王子和狐狸~


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!