2021.3月PAT经历(甲级满分)

2021.3月PAT经历(甲级满分) / Drrany

本文最后更新于：2021年3月15日 晚上

先说一下个人情况，我是科班，没参加过竞赛，上过算法课，自己去年也刷过200+LeetCode题，不过忘得差不多了……。加上自己之前主要用Java刷题，没学过C++，我觉得语言的熟悉程度挺重要的，有时候解法能有很多小trick，所以刚开始PAT总觉得不顺手(实在不敢用Java挑战超时)

学校一月份放了寒假，差不多回家就开始准备了。一开始是跟着晴神的算法笔记做，每天大概学习两个小时左右(带刷题)，刷完算法笔记用了一个月吧，主要是一天分配时间太少了……想着后期努力。

书看完之后开始自己独立刷题，一天大概也是两个小时5、6道，因为一边刷一边学。一般一道题卡快一个小时就开始找题解了，其实pat本质上出题都很模板，考得不光是你的能力，也是你对这些常用算法的熟悉程度(并查集、Dijsktra、堆等等)，所以不要一个人死耗，一道题看个一两天做出来了觉得自己很牛逼……其实是浪费时间，而且一定要学习别人的优质代码是怎么写的，一道题可能你也做出来了，但是耗时高，写的代码多(写得多就容易出bug)。

这里说下我觉得PAT高分最重要的不是天分，而是积累，只要你常用算法模板非常熟悉，在上面的小小变形是不成问题的，根基都没打牢的话高分只能看运气(恰好出了你会的题)。我建议刷题的过程中积累一些常见模板，比如怎么通过中序、前序/后序遍历构建二叉树，Dijsktra+DFS的套路等等，最重要的是你平时自己能写出来这套模板，背是不现实的，只有是你自己的东西才是记得最牢的。

PAT甲的真题我基本上刷了两遍，个人觉得后期的题参考价值比较大，不过时间够的前面刷刷也可以开阔思路~刷的多总是没错的。

考前两天做了20、19年的六套(春秋冬季)甲级卷，分数分别是94、92、93和100(19年三套都比较简单)，我觉得这几次模拟做对我的作用很大，因为第一套卷子我就一直卡题，全程做的很艰难，我还记得第一次过完四道题好像才七八十分，心里很凉，但是时间还多，就开始一个一个找bug(pat的时间还是很良心的)，最后努力到了90+，这次对我的心理素质提升非常大，因为觉得这么难搞的开局我都能90+，考试也不至于比这还差吧（这是个flag，谁想到考试开局比这还离谱……）

哦对了，PAT最重要的是一定要完全读懂题！！！完全！！！很多次过不去点是因为你漏了条件或者题读得有问题……这点真的很重要！！！

我个人觉得对考试成绩的因素中：完全读懂题>>常用算法熟练程度>能力

我的PAT代码都放在github仓库上了，不过有些没有优化，仅供参考：PAT代码

大概提前了快两个小时交卷，这次题不算很简单但也不坑，基本上认真看懂题都能AC。
趁着还记得来记录下这次波折的线上PAT经历……。

这次1:30开考，我12:40开始折腾设备。双机位考试，拍照和视频倒是被监考老师通过了，但是手机那边一直显示连接失败，我一开始不知道什么问题，再加上两边显示正常，就没有管。一直按着“呼叫监考老师”想问问老师怎么办，无奈可能是人太多了，根本没有老师管你……最后开考前20分钟，老师说我手机摄像头是黑的，我又四处问人，发现可能是手机权限问题(?)，但是当时还剩10分钟左右了，不管怎么搞都还是没办法连通。
幸好父上大人在家，飞速争用了他的手机，重新登录我的微信，各种重新验证，最后两分钟了我还在填准考证号和拍验证视频……。

而且这次最难AC的还是第一道题，我第一道题做了块40分钟还没AC，有两个测试点不过，就先跳过了。

经过这个开头我的心情一直是很down的，最后能AK还是多亏了自己的心理素质，一直在给自己打气。考试的时候你的能力决定你的上限，但是心理素质决定你的下限。
下面依次来说一下每道题吧~因为现在题目还没出，可能描述有些出入（老失忆大师了）

1. 等差质数

题目大意是给一个数n和范围range，让你找n个质数组成的等差数列(都不大于range)，如果不唯一就找差最大的，还不唯一就找第一个数字最大的。找不到就输出不大于range的最大素数。

我的方法比较暴力，先得到 $10^5$ 以内的素数表。然后遍历素数表，先确定前两个素数，这样就得到了他们的差，再找剩下n-2个素数，这就比较简单了，每次用前一个素数加上差，看得到的下一个数是不是素数就行了。
得到一个新答案就比较一下，最后输出。

这里我n=1特判了一下。以及第一次有两个点没AC是因为我用的<range，改成<=range就过了……。

/*
 * 1. 等差数列：连续两个数的差是常数
 * 2. 对于任意正整数n，存在至少一个等差数列，由n个质数组成
 * 3. 对于给定的n，找出最大的解（给定范围内）
 * 4. 如果存在解，递增输出；如果解不唯一，输出差最大的；如果仍然不唯一，输出第一个数组最大的
 * 4. 如果无解，输出给定范围内最大的质数
 * */
// 打素数表
const int maxn = 100010;
int range;
vector<int> prime;
vector<bool> isPrime(maxn, true);

void construct() {
    isPrime[0] = false, isPrime[1] = false;
    for (int i = 2; i < maxn; ++i) {
        if (isPrime[i]) { // 当i是素数时，i的所有倍数都是非素数
            prime.push_back(i);
            for (int j = i * 2; j < maxn; j += i)
                isPrime[j] = false;
        }
    }
}


int main() {
    int n;
    cin >> n >> range;
    construct();
    int len = prime.size(); // 一共有多少个素数
    // 得到最大的质数
    int maxPrime = 0;
    for (int i = 0; i < len && prime[i] <= range; ++i)
        maxPrime = prime[i];
    if (n == 1) { // 假设n为1，输出最大的质数
        printf("%d", maxPrime);
        return 0;
    }
    vector<int> ans, cur;
    // 遍历每个素数，假设以该素数为第一个数
    for (int i = 0; i < len && prime[i] <= range; ++i) {
        for (int j = i + 1; j < len && prime[j] <= range; ++j) { // 第二个素数
            int gap = prime[j] - prime[i];
            // 假设可以凑够n-2个间距gap的质数
            bool flag = true;
            int pre = prime[j];
            for (int k = 2; k < n; ++k) {
                int next = pre + gap;
                if (next > range || !isPrime[next]) {
                    flag = false;
                    break;
                }
                pre = next;
            }
            if (flag) { // 得到了一个答案
                cur.clear();
                for (int k = 0; k < n; ++k)
                    cur.push_back(prime[i] + k * gap);
                if (ans.empty()) ans = cur;
                else if (gap > (ans[1] - ans[0])) ans = cur;
                else if (gap == (ans[1] - ans[0]) && cur[0] > ans[0])
                    ans = cur;
            }
        }

    }
    if (ans.empty()) printf("%d", maxPrime);
    else {
        for (int i = 0; i < n; ++i) {
            printf("%d", ans[i]);
            if (i < n - 1) printf(" ");
        }
    }

}

2. 实验室使用安排

这个感觉不用多说了……经典贪心问题，学过就会，没学过就抓瞎(或者上dfs，基本上确定顺序都能用，就是容易超时，要剪好枝)。

先按结束时间从小到大排序，然后依次遍历每条记录，如果当前记录的进入时间大于上一个人的结束时间，那这个人就可以进入，然后更新结束时间。

struct record {
    int in = 0, out = 0;

    record(const string &inTime, const string &outTime) {
        in += stoi(inTime.substr(0, 2)) * 3600;
        in += stoi(inTime.substr(3, 2)) * 60;
        in += stoi(inTime.substr(6, 2));
        out += stoi(outTime.substr(0, 2)) * 3600;
        out += stoi(outTime.substr(3, 2)) * 60;
        out += stoi(outTime.substr(6, 2));
    }
};

bool cmp(const record &a, const record &b) {
    return a.out < b.out;
}

int main() {
    int n;
    cin >> n;
    string in, out;
    vector<record> arr;
    for (int i = 0; i < n; ++i) {
        cin >> in >> out;
        arr.emplace_back(in, out);
    }
    sort(arr.begin(), arr.end(), cmp);
    int count = 0;
    int leftTime = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i].in >= leftTime) {
            count++;
            leftTime = arr[i].out;
        }
    }
    printf("%d", count);

}

3. 大顶堆

体感是这次最难的一道题，虽然做的时间和第一题差不多，但主要是因为考前出事心态问题。幸好考前重新做了一遍堆排序题。

这题的主要难点是通过插入的值得到正确的树，只要构造出了正确的树，后面的父母孩子啥的都很好判断，直接用完全二叉树的特性第i个结点的孩子是第2i和第2i+1就行了。
我一开始是得到了所有的值，然后再直接调整，但是这样得到的树和样例不一样，最后发现得插入一次调整一次……。

void adjust(vector<int> &arr, int i, int n) { // 自下向上构造一个大顶堆
    int index = 2 * i;
    if (index > n) return;
    if (index + 1 <= n && (arr[index + 1] > arr[index])) index++;
    if (arr[index] > arr[i]) {
        swap(arr[i], arr[index]);
        adjust(arr, index, n);
    }
}

void toMaxHeap(vector<int> &tree, int n) {
    for (int i = n / 2; i >= 1; --i) {
        adjust(tree, i, n);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> tree;
    int num;
    tree.push_back(INT32_MAX);
    for (int i = 1; i <= n; ++i) {
        cin >> num;
        tree.push_back(num);
        // 调整tree[1..i]为大顶堆
        toMaxHeap(tree, i);
    }


    string st;
    for (int i = 0; i < m; ++i) {
        cin >> st;
        bool flag = false;
        int x = stoi(st);
        cin >> st;
        if (st == "is") {
            cin >> st >> st;
            if (st == "root")
                flag = x == tree[1];
            else if (st == "parent") { // x是y的父亲
                cin >> st >> st;
                int y = stoi(st);
                // 找到x和y的下标
                int ix = 1, iy = 1;
                while (ix <= n && tree[ix] != x) ix++;
                while (iy <= n && tree[iy] != y) iy++;
                if (ix * 2 == iy || (ix * 2 + 1 == iy)) flag = true;
                else flag = false;
            } else if (st == "left") { // x是y的左孩子
                cin >> st >> st >> st;
                int y = stoi(st);
                // 找到x和y的下标
                int ix = 1, iy = 1;
                while (ix <= n && tree[ix] != x) ix++;
                while (iy <= n && tree[iy] != y) iy++;
                if (iy * 2 == ix) flag = true;
                else flag = false;
            } else if (st == "right") { // x是y的右孩子
                cin >> st >> st >> st;
                int y = stoi(st);
                // 找到x和y的下标
                int ix = 1, iy = 1;
                while (ix <= n && tree[ix] != x) ix++;
                while (iy <= n && tree[iy] != y) iy++;
                if (iy * 2 + 1 == ix) flag = true;
                else flag = false;
            }
        } else if (st == "and") {
            cin >> st;
            int y = stoi(st);
            cin >> st >> st;
            // x和y是兄弟
            for (int j = 1; j <= n / 2; ++j) {
                int left = tree[j * 2];
                if ((j * 2 + 1) > n) break;
                int right = tree[j * 2 + 1];
                // x,y分别是left和right
                if ((x == left && y == right) || (x == right && y == left))
                    flag = true;
            }
        }
        if (flag) printf("1");
        else printf("0");
    }


}

4. 回收共享单车

基本上是个多源最短路径问题。要求从0点出发经过每个点，下个点是距离当前最近的点，得到这个序列，并且判断出哪些点不可达。

所以我选择了Floyd，先求出每两个点之间的最短距离，直接迭代n次，每次找出还没到过的点中最近的那个，如果找不到了就跳出循环，说明之后的点都无法到达了。
其他也没什么好说的，这道题也是一次AC。

/*
 * 1. 设计卡车的收集路线，总是去最近的点来收集单车。
 * 2. 如果最近的点不止一个，去id最小的点
 * 3. 管理中心位于0
 * 4. 首先输出拜访顺序，从0开始
 * 5. 如果不能收集所有的坏车，输出不能到达的点（升序）
 * 6. 如果顺序是最优的，输出总的移动距离
 * */
int G[210][210]{};
vector<vector<int>> minDt(210, vector<int>(210, INT32_MAX));


void calculateLine(int n) {
    for (int k = 0; k <= n; ++k) { // 分别以点k为中转点
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (minDt[k][i] != INT32_MAX && minDt[k][j] != INT32_MAX) {
                    int newDt = minDt[k][i] + minDt[k][j];
                    minDt[i][j] = min(minDt[i][j], newDt);
                }
            }
        }
    }
}

int main() {
    int n, m, u, v, w;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = w;
        minDt[u][v] = minDt[v][u] = w;
    }
    // 计算每两个点之间的最短距离
    calculateLine(n);
    vector<bool> visited(n + 1, false);
    vector<int> path;
    int cur = 0; // 当前位置
    int total = 0;
    for (int i = 0; i < n; ++i) { // 遍历n次，因为0点已经在了
        // 找出未到过的点，且距离当前位置的距离最近
        int tg = -1, tmpMin = INT32_MAX;
        for (int j = 1; j <= n; ++j) {
            if (!visited[j] && minDt[cur][j] < tmpMin) {
                tmpMin = minDt[cur][j];
                tg = j;
            }
        }
        // 如果找不到了，退出
        if (tg == -1) break;
        total += tmpMin;
        path.push_back(tg);
        visited[tg] = true;
        cur = tg;
    }

    // 看是否所有点都到了
    vector<int> noCome;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) noCome.push_back(i);
    }
    printf("0");
    for (const auto &e:path)
        printf(" %d", e);
    if (!noCome.empty()) {
        printf("\n");
        int len = noCome.size();
        for (int i = 0; i < len; ++i) {
            printf("%d", noCome[i]);
            if (i < len - 1) printf(" ");
        }
    } else printf("\n%d", total);
}

这次PAT的题目还是比较良心的，虽然自己的过程十分不顺利，好在最后的结果还不错，只能说一分耕耘一分收获，满打满算快两个月每天都有两个小时在PAT上，之后可能不会再碰了，圆满结束~
贴一下截图~