All for PAT秋考 | 2019.3PAT甲级

半年过去了，昨天终于重新面对这套题目（是的，206块➕11块），竟然还是没做完，重现了考场上的崩溃。那个倒计时跟当时考试一模一样，真是emmm

59 分

今天冷静下来，再看，似乎不是题目本身难，是我细节没有抓好啊！！！

7-1 Sexy Primes (20 分)

素数对，写的还不如3月在考场上写的。可能读题没当时认真吧。
👇考场上的AC代码

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

int main() {
    int nn;
    scanf("%d", &nn);
    if (is_prime(nn)) {
        if (nn > 6 && is_prime(nn - 6)) {
            printf("Yes\n%d\n", nn - 6);
            return 0;
        }
        if (is_prime(nn + 6)) {
            printf("Yes\n%d\n", nn + 6);
            return 0;
        }
    }
    printf("No\n");
    while (!is_prime(nn) || !(is_prime(nn + 6) || is_prime(nn - 6)))
        nn++;
    printf("%d\n", nn);
    return 0;
}

7-2 Anniversary (25 分)

查找➕排序，再次踏进同一个坑，导致了昨天的自闭。
写了一个结构体，存string id和int birth（从id中抽出来的生日），重载了小于号（小：出生较早的），忽略了一件重要的事情——⚠️这样就认为生日一样即为相等（同一人）了，即便再比较id也不行。set<结构体>就自带了顺序。然后就烂了呀……考场上错了1个5分的case……昨天第一遍写错的更多！就自闭了……
不要想太多，set<Person>给来宾按生日排个序，set<string>直接存校友id，挨个find()就完事儿了！

#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <iostream>

using namespace std;

struct Person {
    int birth;
    string id;

    bool operator<(const Person &p2) const {
        if (birth != p2.birth) return birth < p2.birth;
        return id < p2.id;
    }
} alu, com;

set<string> aluid;
set<Person> coms;

int main() {
    int nn, mm;
    cin >> nn;
    for (int i = 0; i < nn; ++i) {
        cin >> alu.id;
        int temp = 0;
        for (int j = 6; j < 14; ++j) {
            temp *= 10;
            temp += (alu.id[j] - '0');
        }
        alu.birth = temp;
        aluid.insert(alu.id);
    }
    int cnt = 0;
    cin >> mm;
    for (int i = 0; i < nn; ++i) {
        cin >> com.id;
        int temp = 0;
        for (int j = 6; j < 14; ++j) {
            temp *= 10;
            temp += (com.id[j] - '0');
        }
        com.birth = temp;
        if (aluid.find(com.id) != aluid.end()) {
            cnt++;
        }
        coms.insert(com);
    }
    cout << cnt << endl;
    if (cnt == 0) cout << coms.begin()->id << endl;
    else
        for (auto &item:coms) {
            if (aluid.find(item.id) != aluid.end()) {
                cout << item.id << endl;
                break;
            }
        }
    return 0;
}

7-3 Telefraud Detection

3月考场上一看，并查集啊，拿手！！结果错了一个6分的case…… 发现通常不是算法写错，而是把输入处理成算法开始时的数据的阶段出错了……题目描述已经这么多幺蛾子了！！！你就老老实实做呗！别给自己找事儿……（并查集——祖先标号大的和祖先标号小的合并，合并到小的，写法注意）

#include <cstdio>
#include <algorithm>
#include <set>
#include <map>

using namespace std;
int uf[1001];

int _find(int curr) {
    return uf[curr] < 0 ? curr : uf[curr] = _find(uf[curr]);
}

void _union(int a, int b) {
    a = _find(a);
    b = _find(b);
    if (a > b) {
        uf[b] += uf[a];
        uf[a] = b;
    } else if (a < b) {
        uf[a] += uf[b];
        uf[b] = a;
    }
}

int main() {
    int graph[1010][1010] = {0};
    bool isSuspect[1010] = {false};
    int KK, NN, MM;
    scanf("%d%d%d", &KK, &NN, &MM);
    for (int i = 0; i < MM; ++i) {
        int v1, v2, dur;
        scanf("%d%d%d", &v1, &v2, &dur);
        graph[v1][v2] += dur;
    }
    int call, call_back, cnt_suspect = 0;
    for (int i = 1; i <= NN; ++i) {
        call = call_back = 0;
        for (int j = 1; j <= NN; ++j) {
            if (graph[i][j] > 0 && graph[i][j] <= 5) {
                call++;
                if (graph[j][i] > 0)
                    call_back++;
            }
        }
        if (call > KK && call_back * 5 <= call) {
            isSuspect[i] = true;
            cnt_suspect++;
        }
    }
    if (cnt_suspect == 0) {
        printf("None\n");
        return 0;
    }
    fill(uf, uf + 1010, -1);
    for (int i = 1; i <= NN; ++i) {
        if (isSuspect[i]) {
            for (int j = 1; j <= NN; ++j) {
                if (isSuspect[j] && graph[i][j] && graph[j][i])
                    _union(i, j);
            }
        }
    }
    map<int, set<int>> res;
    for (int i = 1; i <= NN; ++i) {
        if (isSuspect[i]) {
            res[_find(i)].insert(i);
        }
    }
    for (auto &item:res) {
        int size = item.second.size();
        for (auto item1:item.second) {
            size--;
            printf("%d", item1);
            printf(size ? " " : "\n");
        }
    }
    return 0;
}

7-4 Structure of a Binary Tree

考场上写到这儿还有将近一个半小时 = = ，然而前面case还有大分没拿，看了看输入那么麻烦（当时没记住C++ string的几个重要函数，也不会用sscanf），竟然就这么放弃了……

• 输入处理
  利用string的find函数查找子串（找不到返回-1），结合sscanf就非常简单了！
• Node结构体中包括key，lchild，rchild，father，depth字段。由中序、后序序列递归建树时，就把这些字段都填上。然后就，so easy了。。。
• ⚠️root->child->father要先判断child不是NULL， root->child->key之类也要判断是否可能是空指针！！！

#include <iostream>
#include <string>

using namespace std;
int post_seq[32], in_seq[32], nn, nq;
bool isFull = true;

struct Node {
    int key, depth;
    Node *father = NULL, *lchild = NULL, *rchild = NULL;
};

Node *createBTree(int post_st, int post_ed, int in_st, int in_ed, int depth) {
    if (post_st > post_ed || in_st > in_ed) {
        return NULL;
    }
    Node *root = new Node;
    int rkey = post_seq[post_ed], pos = -1;
    for (int i = in_st; i <= in_ed; ++i) {
        if (in_seq[i] == rkey) {
            pos = i;
            break;
        }
    }
    root->key = rkey;
    root->depth = depth;
    int lsize = pos - in_st;
    root->lchild = createBTree(post_st, post_st + lsize - 1, in_st, pos - 1, depth + 1);
    root->rchild = createBTree(post_st + lsize, post_ed - 1, pos + 1, in_ed, depth + 1);
    if (isFull && (root->lchild || root->rchild) && (!(root->lchild && root->rchild))) isFull = false;
    if (root->lchild) root->lchild->father = root;
    if (root->rchild) root->rchild->father = root;
    return root;
}

Node *searchKey(Node *root, int x) {
    if (root == NULL) return NULL;
    if (root->key == x)
        return root;
    Node *temp = searchKey(root->lchild, x);
    if (temp) return temp;
    return searchKey(root->rchild, x);
}

int main() {
    cin >> nn;
    for (int i = 0; i < nn; ++i) {
        cin >> post_seq[i];
    }
    for (int i = 0; i < nn; ++i) {
        cin >> in_seq[i];
    }
    Node *root = createBTree(0, nn - 1, 0, nn - 1, 1);
    cin >> nq;
    getchar(); // !!!!!!
    string str;
    bool res;
    int A, B;
    for (int i = 0; i < nq; ++i) {
        getline(cin, str);
        if (str.find("root") != -1) {
            sscanf(str.data(), "%d is the root", &A);
            res = (root->key == A);
        } else if (str.find("siblings") != -1) {
            sscanf(str.data(), "%d and %d are siblings", &A, &B);
            res = (searchKey(root, A)->father == searchKey(root, B)->father);
        } else if (str.find("parent") != -1) {
            sscanf(str.data(), "%d is the parent of %d", &A, &B);
            Node *pp = searchKey(root, A);
            int lk, rk;
            lk = (pp->lchild != NULL ? pp->lchild->key : -1);
            rk = (pp->rchild != NULL ? pp->rchild->key : -1);
            res = (lk == B || rk == B);
        } else if (str.find("child") != -1) {
            if (str.find("left") != -1) {
                sscanf(str.data(), "%d is the left child of %d", &A, &B);
                Node *pp = searchKey(root, B);
                if (pp->lchild == NULL) res = false;
                else res = (pp->lchild->key == A);
            } else {
                sscanf(str.data(), "%d is the right child of %d", &A, &B);
                Node *pp = searchKey(root, B);
                if (pp->rchild == NULL) res = false;
                else res = (pp->rchild->key == A);
            }
        } else if (str.find("level") != -1) {
            sscanf(str.data(), "%d and %d are on the same level", &A, &B);
            res = (searchKey(root, A)->depth == searchKey(root, B)->depth);
        } else if (str.find("full") != -1)
            res = isFull;
        puts(res ? "Yes" : "No");
    }
    return 0;
}