PAT Autumn 2021 - Colin's Space

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双关键字排序~~

#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$ 即可。

#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$ 时两个人得分一样。

#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;
}