PAT（甲级）2022年夏季考试 题解

可能是今年最后一篇pat甲级题解

着手备战甲级是学了70%的数据结构课本开始的，跟着晴神的书和柳神的题解，以及严版数据结构和算法导论一路写了差不多100道题，最后摸了个满分也算圆满收场了（笑）感谢姥姥加开夏季场给了咱一个补票的机会

本次甲级题目偏简单，全场44个满分348个参与者，接下来就开始题解正文吧

——KKKah

7-1 What Day is Today

分数 20 作者 陈越 单位 浙江大学

Amy and Tom are arguing about what day is today. Their conversations are as the following:

Amy: Today is Friday.
Tom: No! Today is Saturday.
Amy: But Wednesday was yesterday.
Tom: No way! Yesterday was Thursday.
Amy: Then tomorrow must be Tuesday.
Tom: Are you kidding? It's Monday tomorrow.
Now their mother tells you that each of them has said only one thing correct.  It’s your job to tell exactly what day is today.
Input Specification:
Each input file contains one test case. Each case consists of 2 lines, each gives the claims of a kid, in the following format:
yesterday today tomorrow
where the days are represented by numbers from 0 to 6, corresponding to Sunday through Saturday.
Output Specification:
First output in a line the English name for “today”.  It is  guaranteed that each kid has said only one thing correct, and there is a unique answer for “today”.
Then in the next two lines, print in order the correct days (either yesterday or today, or tomorrow) obtained from the kids.
Sample Input:
3 5 2
4 6 1
Sample Output:
Friday
today
yesterday
Note: The English names for the days are
0 - Sunday
1 - Monday
2 - Tuesday
3 - Wednesday
4 - Thursday
5 - Friday
6 - Saturday
代码长度限制  16 KB
时间限制     400 ms
内存限制     64 MB
两小儿讨论今儿个是星期几，每个儿童说昨/今/后天是星期几，但两小儿都只说了一句真话
说出今天是星期几，以及输出两小儿的真话说的是昨/今还是后天
思路与代码
分别根据两小儿的叙述折算出对应的今天星期，两个人都提到的那一天是真的。按着这个思路写就好办了，尤其这道题输入还是数字，不用亲自抠字符串是好文明
代码有点乱，见谅
// 7-1 What Day is Today (20)
// 4ms
#include <iostream>
#include <string>
using namespace std;
string weekday[7] = {
    "Sunday", "Monday", "Tuesday", "Wednesday",
    "Thursday", "Friday", "Saturday"};
string day[4] = {"", "yesterday", "today", "tomorrow"};
int main() {
    int book[2][7] = {0};
    for (int i = 0; i < 2; i++) {
        int d[4];
        cin >> d[1] >> d[2] >> d[3];
        d[3] = (d[3] + 7 - 1) % 7;
        d[1] = (d[1] + 1) % 7;
        for (int j = 1; j <= 3; j++)
            book[i][d[j]] = j;
    for (int i = 0; i < 7; i++) {
        if (book[0][i] && book[1][i]) {
            cout << weekday[i] << '\n';
            for (int j = 0; j < 2; j++)
                cout << day[book[j][i]] << '\n';
    return 0;
7-2 Least Recently Used Cache
分数 25  作者 陈越  单位 浙江大学
Least Recently Used (LRU) cache scheme is to remove the least recently used frame (the one hasn’t been used for the longest amount of time) when the cache is full and a  new page is referenced which is not there in cache.
Your job is to implement this LRU cache scheme.
Input Specification:
Each input file contains one test case. For each case, the first line gives 2 positive integers N (≤104) and M (≤105) which are the size of the cache and the number of referenced page ID’s. Then M referenced page ID’s are given in the next line.  A page ID is a number in the range [1,2×104]. All the numbers in a line are separated by a space.
Output Specification:
For each test case, output in a line the page ID’s in the order of  their being removed from the cache.  All the numbers in a line must be  separated by 1 space, and there must be no extra space at the beginning  or the end of the line.
It is guaranteed that at least one page will be removed.
Sample Input:
1 2 3 1 4 5 2 1 5 6 3
Sample Output:
2 3 4 2
Hint:
When pages with ID’s 1, 2, and 3 comes in order, they are all stored in the cache and page 1 is now the LRU frame.
When page 1 is accessed, page 2 then becomes the LRU frame.
Page 4 can still be stored in the cache, and now the cache is full.   When page 5 is to be cached, page 2 will be removed and page 3 becomes  the LRU frame.
When the next page 2 comes in, page 3 is removed and page 1 becomes the LRU frame.
Then page 1 is accessed, so page 4 becomes the LRU frame.
When page 5 is accessed, the LRU frame is not changed.  Then page 6  comes in and page 4 is removed.  The LRU frame is now page 2.
Finally page 2 is removed when page 3 comes in.
代码长度限制  16 KB
Java (javac)
时间限制  900 ms
内存限制  256 MB
其他编译器
时间限制  150 ms
内存限制  64 MB
一堆待编号的页面，缓存空间有限所以最不经常访问的页面要删掉，给出缓存大小和访问序列，按顺序输出页面的删除序列
思路与代码
我在知乎上看到这个题好像有个短得多的解法。但是我忘了存链接所以就这样吧
目测是堆。用出现在访问序列中的位置（像“时间戳”一样），最小的（也就是最早访问的）删除掉，小根堆。重新访问的时候会改变页面id所对应的时间戳，但是我对stl的优先队列掌握不熟遇到这情况不会用了（尴尬）只能手写堆。（期间还犯了好几次蠢，把down的函数写错了……耗时最久的题）
最后两个测试点结点id范围1e5，倒数第二个点数据量大tle了一次（当时没有加从元素id指向堆中位置的数组/unordered_map，现在这部分代码已经加上了并对老代码注释处理）
其实inheap和heap_pos可以合并的，但是我懒了23333所以就这样吧
// 7-2 Least Recently Used Cache (25)
// 24ms
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define N 10010
#define M 100010
int heap[N], t[M], idx = 1, heap_size = 0;
bool inheap[M];
int heap_pos[M]; // 已加上 // 缺一个记录坐标在堆中位置的优化 5分
vector<int> pop_seq;
// void debug_print_heap() {
//     for (int i = 1; i < idx; i++)
//         printf("%d(%d)  ", heap[i], t[heap[i]]);
//     puts("");
void heap_insert(int p_id);
void heap_update(int p_id);
int main() {
    int m;
    scanf("%d %d", &heap_size, &m);
    for (int timei = 1; timei <= m; timei++) {
        int tmp_id;
        scanf("%d", &tmp_id);
        t[tmp_id] = timei;
        if (inheap[tmp_id] == false)
            heap_insert(tmp_id);
            heap_update(tmp_id);
        // debug_print_heap();
    for (int i = 0; i < (int)pop_seq.size(); i++)
        printf("%d%c", pop_seq[i], (i + 1 == pop_seq.size() ? '\n' : ' '));
    return 0;
void heap_up(int pos);
void heap_down(int pos);
void heap_insert(int p_id) {
    inheap[p_id] = true;
    if (idx <= heap_size) {
        heap[idx] = p_id;
        heap_pos[p_id] = idx;
        idx++;
        heap_up(idx - 1);
        return;
    pop_seq.push_back(heap[1]);
    inheap[heap[1]] = false;
    heap[1] = p_id;
    heap_pos[p_id] = 1;
    heap_down(1);
void heap_update(int p_id) {
    int pos = heap_pos[p_id];
    // for (pos = 1; pos < idx; pos++)
    //     if (heap[pos] == p_id)
    //         break;
    heap_up(pos);
    heap_down(pos);
inline void heap_swap(int posa, int posb) {
    swap(heap_pos[heap[posa]], heap_pos[heap[posb]]);
    swap(heap[posa], heap[posb]);
void heap_up(int pos) {
    if (pos == 1) return;
    int parent = pos / 2;
    if (t[heap[parent]] <= t[heap[pos]])
        return;
    // swap(heap[parent], heap[pos]);
    heap_swap(parent, pos);
    heap_up(parent);
void heap_down(int pos) {
    int lc = 2 * pos, rc = 2 * pos + 1, tmp = pos;
    if (lc < idx && t[heap[lc]] < t[heap[tmp]])
        tmp = lc;
    if (rc < idx && t[heap[rc]] < t[heap[tmp]])
        tmp = rc;
    if (tmp == pos)
        return;
    // swap(heap[tmp], heap[pos]);
    heap_swap(tmp, pos);
    heap_down(tmp);
7-3 DFS Sequence
分数 25   作者 陈越    单位 浙江大学
The above question is commonly seen in a final exam of the course Data Structures.  That is, given a graph G, you are supposed to tell if a sequence of vertices can be possibly obtained from any depth first search (DFS) on G.
Now it is your job to write a program which can give the answers automatically.
Note: it is required that each vertex must be visited once even if the graph is not connected.  In the graph given by the sample  input, if we start from vertex 4, then vertex 1 cannot be reached during this DFS, yet it can be the first vertex visited in the next DFS. Hence the 5th query 4 3 2 5 1 is possible.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive integers: N (≤103), M (≤104), and K (≤100), which are the number of vertices, the number of edges, and the number of queries, respectively.  Then M lines follow, each gives an edge in the format:
source destination
which means that there is an edge from source vertex to destination vertex.  Here we assume that all the vertices are numbered from 1 to N.  It is guaranteed that source is never the same as destination.
Finally K lines of queries are given, each contains N vertices.  The numbers in a line are separated by spaces.
Output Specification:
For each query, print in a line yes if the given sequence does correspond to a DFS sequence, or no if not.
Sample Input:
5 7 6
1 5 4 3 2
1 3 2 5 4
1 2 5 4 3
1 2 3 4 5
4 3 2 5 1
5 4 3 2 5
Sample Output:
代码长度限制    16 KB
Java (javac)
时间限制    1200 ms
内存限制    256 MB
其他编译器
时间限制    400 ms
内存限制    64 MB
给一个有向图，判断下列dfs序列的合法性
思路与代码
按着一步一步来就好，详情看check函数注释＜（＾－＾）＞
// 7-3 DFS Sequence (25)
// 25ms
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
int g[N][N], n;
vector<int> seq;
bool check();
int main() {
    memset(g, 0x3f, sizeof(g));
    int m, k, l, r;
    scanf("%d %d %d", &n, &m, &k);
    while (m--) {
        scanf("%d %d", &l, &r);
        g[l][r] = 1;
    seq.resize(n);
    while (k--) {
        for (int i = 0; i < n; i++)
            scanf("%d", &seq[i]);
        puts(check() ? "yes" : "no");
    return 0;
bool check() {
    bool vis[N];
    memset(vis, 0, sizeof(vis));
    // 对每个结点，检查下一个结点是否合法
    for (int i = 0; i < n - 1; i++) {
        // if (vis[seq[i]]) return false; // 如果当前节点已访问，返回否
        vis[seq[i]] = true;
        if (vis[seq[i + 1]]) return false; // 下一个节点走过的话肯定false
        if (g[seq[i]][seq[i + 1]] != INF)  // 如果下个节点联通
            continue;
        else {
            for (int j = 1; j <= n; j++)
                if (g[seq[i]][j] != INF && (!vis[j]))  // 如果序列的下一个结点不连通，并且存在一个已联通且未访问的结点
                    return false;
    return true;
7-4 Complete D-Tree
分数 30   作者 陈越   单位 浙江大学
A d-tree is a tree of degree d.  A complete tree is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Given the pre-order traversal sequence of a complete d-tree, you are supposed to obtain its level-order traversal sequence.  And  more, for any given node, you must be able to output the bottom-up path  from this node to the root.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: N (≤50) and d (2≤d≤5), which are the total number of nodes in the tree, and the tree’s degree, respectively.  Then in the next line, N integer keys (≤100) are given as the pre-order traversal sequence of the tree.  Finally K (≤N) and K positions are given, where each position is the index of a key in the level-order traversal sequence, starting from 0.
All the numbers in a line are separated by a space.
Output Specification:
For each case, first print in one line the level-order traversal sequence of the complete d-tree.  Then for each given position,  print in a line the bottom-up path from this node to the root.
All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.
Sample Input:
91 71 2 34 10 15 55 18 7
5 7 3
Sample Output:
91 71 15 7 2 34 10 55 18
34 71 91
55 15 91
代码长度限制    16 KB
时间限制    400 ms
内存限制    64 MB
给定一个完全d叉树的前序遍历序列，输出层序遍历序列。对于给定的“层序遍历中元素所在位置”输出这个元素到根的路径
思路与代码
数组保存，根节点存0，对于每个节点（下标$p$）的孩子范围是$p*d+1$到$p*d+d$，父亲坐标是$(p-1)/d$。下标小于元素个数的是合法位置。基于这几点就好些了，dfs建树，不断“找父亲”像根遍历（不是根加空格，是的话加换行）。个人感觉说不定这个题设置25分更合适，说实话有点太简单了
// 7-4 Complete D-Tree (30)
// 3ms
#include <cstdio>
using namespace std;
#define N 60
int n, deg, ls[N], depth = 1;
int pre_seq[N];
void build_tree(int tpos);
void find_father(int treepos);
int main() {
    scanf("%d %d", &n, &deg);
    for (int i = 0; i < n; i++)
        scanf("%d", &pre_seq[i]);
    build_tree(0);
    for (int i = 0; i < n; i++)
        printf("%d%c", ls[i], (i == n - 1 ? '\n' : ' '));
    int k, sonpos;
    scanf("%d", &k);
    while (k--) {
        scanf("%d", &sonpos);
        find_father(sonpos);
    return 0;
// dfs建树
void build_tree(int tpos) {
    static int rawpos = 0;
    ls[tpos] = pre_seq[rawpos++];
    int lim = (tpos + 1) * deg;
    for (int sp = tpos * deg + 1; sp < n && sp <= lim; sp++)
        build_tree(sp);
void find_father(int tpos) {
    printf("%d%c", ls[tpos], (tpos == 0 ? '\n' : ' '));
    if (tpos)
        find_father((tpos - 1) / deg);