All for PAT秋考 | 1144 - 1147

刷新了我最快满分的记录，75min。
一个原因是上午啥也没干➕中午吃的不错，另一个是主因：这套题确实偏简单，且码量很小……

75min

1144 The Missing Number (20 分)

找出未出现的最小正整数。
首先在输入时仅保留正数，用set（自带排序）存储并计数。
再从1遍历，若set中第i个数（从0开始）不是i+1，则输出i+1，return结束。
⚠️遍历结束，输出i+1。（一开始忘了这点

#include <cstdio>
#include <set>

using namespace std;

int main() {
    int nn, temp, cnt = 0;
    scanf("%d", &nn);
    set<int> mset;
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &temp);
        if (temp > 0) {
            mset.insert(temp);
            cnt++;
        }
    }
    int i = 1;
    for (auto item:mset) {
        if (item != i) {
            printf("%d\n", i);
            return 0;
        }
        i++;
    }
    printf("%d", i);
    return 0;
}

1145 Hashing - Average Search Time (25 分)

这个谜一样的平均查找次数……这种题记得先手动模拟一波，验证理解的对否。

• Tsize取不小于所给值的最小素数。
• ⚠️插入
  某个key的元素可能插入的位置是（key + i * i） % Tsize，i的范围[0, Tsize），i == Tsize的话mod Tsize就和 i = 0 一样了。
• ⚠️查找
  某个key的元素查找：（key + i * i） % Tsize，若找到空位或找到了这个元素就break，i的范围[0, Tsize]，Tsize也要算进去！！！

#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

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

int main() {
    int Msize, nn, mm, temp;
    scanf("%d%d%d", &Msize, &nn, &mm);
    while (!isPrime(Msize)) Msize++;
    vector<int> hash_table(Msize);
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &temp);
        int pos, j = 0;
        for (; j < Msize; ++j) {
            pos = (temp + j * j) % Msize;
            if (hash_table[pos] == 0) {
                hash_table[pos] = temp;
                break;
            }
        }
        if (j == Msize) printf("%d cannot be inserted.\n", temp);
    }
    int total = 0;
    for (int i = 0; i < mm; ++i) {
        scanf("%d", &temp);
        int pos, j = 0;
        for (; j <= Msize; ++j) {
            pos = (temp + j * j) % Msize;
            total++;
            if (hash_table[pos] == 0 || hash_table[pos] == temp) break;
        }
    }
    printf("%.1lf\n", total * 1.0 / mm);
    return 0;
}

1146 Topological Order (25 分)

验证是否是拓扑序列。
按照所给序列，检查入度是否为0，若是0，删它发出的边（只需改in_degree数组就好）, 检查后面一个点是不是入度为0……

#include <cstdio>

using namespace std;
int in_deg[1001] = {0};
bool graph[1001][1001] = {false};

int main() {
    int nn, mm, qq, v1, v2, temp;
    scanf("%d%d", &nn, &mm);
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d", &v1, &v2);
        graph[v1][v2] = true;
        in_deg[v2]++;
    }
    scanf("%d", &qq);
    bool hasAns = false;
    int cp_indeg[1001] = {0};
    for (int i = 0; i < qq; ++i) {
        for (int k = 1; k <= nn; ++k) {
            cp_indeg[k] = in_deg[k];
        }
        bool isTopo = true;
        for (int j = 0; j < nn; ++j) {
            scanf("%d", &temp);
            if (isTopo) {
                if (cp_indeg[temp] == 0) {
                    for (int k = 1; k <= nn; ++k) {
                        if (graph[temp][k])
                            cp_indeg[k]--;
                    }
                } else isTopo = false;
            }
        }
        if (!isTopo) {
            if (hasAns) printf(" ");
            printf("%d", i);
            hasAns = true;
        }
    }
    return 0;
}

1147 Heaps (30 分)

看见这题先紧张了一下，然后看见题目保证是完全二叉树，觉得稳了hhhhh

• 数组保存CBT，下标从0开始，则下标i的结点，左右孩子（若存在）下标分别为2i+1，2i+2。
• 题目保证结点1个以上，由下标0、1结点的大小关系判断可能是最大堆还是最小对。遍历所有非叶子结点[0，nn/2），跟孩子大小关系……注意check孩子下标是否小于结点数量。
• 后序遍历：递归

#include <cstdio>

using namespace std;
int btree[1010], nn, nt;

int HeapType() {
    int type = btree[1] > btree[0] ? 1 : -1;
    if (type == 1) { //min
        for (int i = 0; i < nn / 2; ++i) {
            if (btree[2 * i + 1] < btree[i]) return 0;
            if (2 * i + 2 < nn && btree[2 * i + 2] < btree[i]) return 0;
        }
    } else {
        for (int i = 0; i < nn / 2; ++i) {
            if (btree[2 * i + 1] > btree[i]) return 0;
            if (2 * i + 2 < nn && btree[2 * i + 2] > btree[i]) return 0;
        }
    }
    return type;
}

void post_traverse(int root) {
    if (2 * root + 1 < nn) post_traverse(2 * root + 1);
    if (2 * root + 2 < nn) post_traverse(2 * root + 2);
    printf("%d", btree[root]);
    printf(root == 0 ? "\n" : " ");
}

int main() {
    scanf("%d%d", &nt, &nn);
    for (int i = 0; i < nt; ++i) {
        for (int j = 0; j < nn; ++j) {
            scanf("%d", &btree[j]);
        }
        switch (HeapType()) {
            case -1:
                puts("Max Heap");
                break;
            case 1:
                puts("Min Heap");
                break;
            case 0:
                puts("Not Heap");
                break;
        }
        post_traverse(0);
    }
    return 0;
}