[C++知识库]PAT甲级准备方法（附2021年PAT甲级秋季考试题解）

第一次参加PAT甲级考试，两小时顺利拿了满分，读题上不太仔细导致浪费了至少大概半小时，这次PAT甲级难度确实相比之前几次有些简单，满分估计有三百来个了吧，具体多少不太了解。这里大概讲一下怎么样准备PAT甲级。

准备工作

之前算得上是断断续续在刷PAT甲级，偶尔心情好了来一道，实际情况就是到了三月份我感觉自己树和图都还没怎么刷就没去参加春季考试了。总的来说还是要系统训练一两个月，这个应该算是平均水平，对于大佬可能半个月、一个月，对于零基础可能还要稍微久一点，每天的时间也不必分配太多，大概三个半小时以内吧，刷久了其实也很无聊的。

总的来说，确实还是分类来刷比较好的，因为这会让你整个模块知识构建更快更清晰，然后我的代码里面已经分好类了，也讲了一些思路。注意：最后一定要留足半个月时间来刷往年真题，这会让你对接下来主要会考哪些内容有所了解，掌握大致方向，真题测试的话是需要去教育商店买，一套五块钱也还好（我前后都冲了30）
最后附上我的刷题集，其中record就记录了分类，其实打了勾的我都刷了，总体题量是没有155这么多的，稍微轻松一点，部分代码参考柳婼。有时间就可以二刷，没有时间也不强求，我其实前后也没全部刷完，但是真题是每套都刷完了的，真题从17年开始刷起就好，最好是先搜题自己做了之后再去教育商店买题进行提交，网上各大博客很多地方都能搜到真题，但是测试你得去PAT上测试。

然后附上2021秋季题解

7-1
这道题一开始就对了两个测试点11分，给我整的有点懵，后来改了17分，最后换了个代码才AC了，其实都是读题不仔细。有两个要点：
Ⅰ、 给出来n个数组是可以给你n个数组用，要用到才算进去，比如给三个数组，但是前两个数组就已经满足query要求了，那么用到的数组数应该输出2
Ⅱ、 第一个数组是一直存在的，所以对于它的测试样例，如果我只执行query查50，那么用到的数组数应该输出1而不是0（那三分就卡这个地方，很多人都卡这个地方），所幸我的新代码不需要考虑这个点
最初代码（17分）

// 这个代码主要是如果直接越界就输出1，因为从一开始是有一个数组的，而不是所有的都是临时建的，如果觉得这个更好理解请自行修改
#include <iostream>
using namespace std;

struct node
{
    int initial, len;
} arr[10005];
bool visit[10005];

int main()
{
    int n, k, query, total = 0, maxNum = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].initial >> arr[i].len;
        total += arr[i].len;
    }

    for (int i = 0; i < k; i++)
    {
        cin >> query;
        if (query >= total)
            cout << "Illegal Access" << endl;
        else
        {
            for (int j = 0; j < n; j++)
            {
                maxNum = max(j + 1, maxNum);
                if (arr[j].len <= query)
                    query -= arr[j].len;
                else
                {
                    cout << arr[j].initial + query * 4 << endl;
                    break;
                }
            }
        }
    }
    cout << maxNum << endl;
    return 0;
}

AC代码：

#include <iostream>
#include <vector>
using namespace std;

int start[10005];
int size[10005];
vector<int> rec;

int main()
{
    int n, k, query, maxQuery = -1;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> start[i] >> size[i];
        for (int j = 0; j < size[i]; j++)
            rec.push_back(start[i] + j * 4);
    }
    for (int i = 0; i < k; i++)
    {
        cin >> query;
        if (query >= rec.size())
            cout << "Illegal Access" << endl;
        else
        {
            maxQuery = max(maxQuery, query);
            cout << rec[query] << endl;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (maxQuery < size[i])
        {
            cout << i + 1 << endl;
            break;
        }
        else
            maxQuery -= size[i];
    }
    return 0;
}

7-2
这题不难，但是自我感觉写得很烂，看不懂请参考更优质代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

struct node
{
    int weight, index;
} list[10005];

vector<int> hats(10005);

bool cmp(node n1, node n2)
{
    return n1.weight > n2.weight;
}

int main()
{
    int n, num;
    cin >> n;
    for (int i = n; i >= 1; i--)
        cin >> hats[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> num;
        list[i] = {num, i};
    }

    vector<int> temp = hats;
    sort(temp.begin() + 1, temp.begin() + n + 1);

    sort(list + 1, list + n + 1, cmp);
    map<int, int> rec;
    for (int i = 1; i <= n; i++)
        rec[temp[i]] = n - i + 1;

    for (int i = 1; i <= n; i++)
    {
        if (i != 1)
            cout << " ";
        int rank = rec[hats[i]];
        cout << list[rank].index;
    }
}

7-3
这题一开始只得了15分，一个测试点错误，两个超时。因为我是全局路径搜索，最后来检查的时候读题发现每次都找数字最小的那个spot爬过去，因此其实对于每个开始spot，总共就只有一条路可走，其实这样更简单了。这题就注意这个地方就行，DFS。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 105, INF = 0x3f3f3f3f;
vector<vector<int>> edge(MAXN);
int rec[MAXN];
bool visit[MAXN];

int maxTotal;

void dfs(int start, int total)
{
    if (start == INF)
        return;
    if (total > maxTotal)
        maxTotal = total;
    visit[start] = true;
    int minNum = INF;
    for (int i = 0; i < edge[start].size(); i++) // 之前在那儿无脑找，后面看题意只需要找最小那个数字就行了
    {
        int next = edge[start][i];
        if (visit[next] == false && next < minNum)
            minNum = next;
    }
    dfs(minNum, total + 1);
}

int main()
{
    int n, m, v1, v2;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> v1 >> v2;
        edge[v1].push_back(v2);
        edge[v2].push_back(v1);
    }

    for (int i = 1; i <= n; i++)
    {
        fill(visit, visit + MAXN, false);
        maxTotal = 0;
        dfs(i, 1);
        rec[i] = maxTotal;
    }

    int maxSpot = 0, resIndex;
    for (int i = 1; i <= n; i++)
    {
        if (rec[i] > maxSpot)
        {
            resIndex = i;
            maxSpot = rec[i];
        }
    }
    cout << resIndex << " " << maxSpot; // 这题输出spot不包含自身
    return 0;
}

7-4
这题其实意思没读懂其实不太影响，看图再结合题意大致都能明白什么意思，先排个序然后建树再层序遍历即可。其实个人觉得7-3出成全局路径搜索完全可以和这题换个位置。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct node
{
    int key, prior;
    node *left, *right;
} tree[35];

bool cmp(node n1, node n2)
{
    return n1.prior < n2.prior;
}

node *insert(node *root, node cur)
{
    if (root == NULL)
    {
        root = new node();
        root->key = cur.key;
        root->prior = cur.prior;
        root->left = root->right = NULL;
    }
    else
    {
        if (cur.key < root->key)
            root->left = insert(root->left, cur);
        else if (cur.key > root->key)
            root->right = insert(root->right, cur);
    }
    return root;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> tree[i].key >> tree[i].prior;
    sort(tree, tree + n, cmp);

    node *root = NULL;
    for (int i = 0; i < n; i++)
        root = insert(root, tree[i]);

    vector<int> keyLevel, priorLevel;
    queue<node *> q;
    q.push(root);
    while (!q.empty())
    {
        node *front = q.front();
        q.pop();
        keyLevel.push_back(front->key);
        priorLevel.push_back(front->prior);
        if (front->left != NULL)
            q.push(front->left);
        if (front->right != NULL)
            q.push(front->right);
    }

    for (int i = 0; i < keyLevel.size(); i++)
    {
        if (i != 0)
            cout << " ";
        cout << keyLevel[i];
    }
    cout << endl;
    for (int i = 0; i < priorLevel.size(); i++)
    {
        if (i != 0)
            cout << " ";
        cout << priorLevel[i];
    }
    cout << endl;
    return 0;
}

第一次考PAT满分过关很开心，这里也预祝各位刷题愉快，PAT考试顺利！