PAT Autumn 2021

Background

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

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

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

Solution ( Top Level )

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

A. Sorted Cartesian tree

给定 \(n\) 个pair<priority, key> ，构建一棵 \(n\) 个节点的二叉树，满足：

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

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

把树建出来，输出 priority 和 key 的Level-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\le3)\)，两个人玩（开始双方均为 \(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 同学还在奋战，我就开始快乐的浙传半日游～

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

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