All for PAT秋考 | 2018.9PAT甲级题解

作者: zilla | 来源:发表于2019-08-10 13:26 被阅读0次

基本过了一遍算法笔记，昨天晚上第一次刷近年的整套题。🌀台风天玩了大半天小尤非常愉快，略略略～～～
趁心情8错，选择的去年的秋季考试，据说去年的秋考比较难，一上来第一题狼人杀就被搞懵了。写的时候emmmm有心理准备，就感觉还好（考试估计心态要炸、没玩过狼人杀啊！！！
因为这次的代码对我来说算写的还不错，所以梳理一下～～～

20 25 25 30~~~

1148 Werewolf - Simple Version (20 分)

暴力穷举，第一层是任取两个为狼人，第二层是任取两个作为liar（一个从狼人里取，一个从其他里取），若推不出矛盾，则找到一组解，结束。若穷举结束还没有合理的解，No Solution。这两层分别写成了一个函数，在第一层穷举中调用第二层穷举的函数。

#include <cstdio>

using namespace std;
int claims[101][2], nn; // claims: + 1/- -1, index
bool checkLiars(int l1, int l2, int w1, int w2) {
    int identity[101] = {0};
    identity[w1] = identity[w2] = -1;
    for (int i = 1; i <= nn; ++i) {
        int flag = (i == l1 || i == l2) ? -1 : 1, obj = claims[i][1];
        if (flag * claims[i][0] == -1 && obj != w1 && obj != w2) {
            return false;
        }
        if (identity[obj] == 0)
            identity[obj] = flag * claims[i][0];
        else if (identity[obj] != flag * claims[i][0])
            return false;
    }
    return true;
}

bool judgeWerewolf(int w1, int w2) {
    // w1/w2 is a liar
    for (int i = 1; i <= nn; ++i) {
        if (i == w1 || i == w2) continue;
        // i is a liar
        if (checkLiars(w1, i, w1, w2)) return true;
        if (checkLiars(w2, i, w1, w2)) return true;
    }
    return false;
}

int main() {
    scanf("%d", &nn);
    char ch;
    for (int i = 1; i <= nn; ++i) {
        scanf("\n%c%d", &ch, &claims[i][1]);
        if (ch == '+') claims[i][0] = 1;
        else claims[i][0] = -1;
    }
    for (int i = 1; i < nn; ++i) { // 2 wolves
        for (int j = i + 1; j <= nn; ++j) {
            if (judgeWerewolf(i, j)) {
                printf("%d %d\n", i, j);
                return 0;
            }
        }
    }
    puts("No Solution");
    return 0;
}

1149 Dangerous Goods Packaging (25 分)

一眼看上去incompatible goods以为是POJ2492 A Bug’s Life这样二分图染色的，快写完了发现不是，立刻不知所措😢……然后就想，不管它复杂度了，就用STL暴力吧！！！map套set一上，就这么AC了。。。。。。

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

using namespace std;
int npair, nlist;
map<int, set<int>> pairs;

int main() {
    scanf("%d%d", &npair, &nlist);
    int p1, p2;
    for (int i = 0; i < npair; i++) {
        scanf("%d%d", &p1, &p2);
        pairs[p1].insert(p2);
        pairs[p2].insert(p1);
    }
    for (int i = 0; i < nlist; ++i) {
        int cnt, id;
        bool flag = true;
        set<int> list;
        scanf("%d", &cnt);
        for (int j = 0; j < cnt; ++j) {
            scanf("%d", &id);
            list.insert(id);
        }
        for (auto item:list) {
            if (!flag) break;
            if (pairs[item].empty()) continue;
            for (auto item1:pairs[item]) {
                if (list.find(item1) != list.end()) {
                    flag = false;
                    break;
                }
            }
        }
        printf(flag ? "Yes\n" : "No\n");
    }
    return 0;
}

1150 Travelling Salesman Problem (25 分)

一看这么长的题面，开始慌了。看完？？？好像就是普通的按着题里流程走。。。。。。

路径连通吗？
不连通则Not a TS cycle，且dist为NA，结束。
若连通，下一步。
路径是连通的，累加计算dist，它首尾一样吗？
不一样，Not a TS cycle。
一样，下一步。
每个城市都到过吗？
有的城市没到过，Not a TS cycle。
都到过，下一步。
每个城市仅到了一次吗？（⚠️除了首尾：2次）
是， TS simple cycle。
否，TS cycle。
找dist最小的连通路径，结束。

#include <cstdio>
#include <vector>

using namespace std;
int graph[201][201] = {0};

int main() {
    int ncity, mroad, kpath;
    scanf("%d%d", &ncity, &mroad);
    int c1, c2, weight;
    for (int i = 0; i < mroad; ++i) {
        scanf("%d%d%d", &c1, &c2, &weight);
        graph[c1][c2] = graph[c2][c1] = weight;
    }
    scanf("%d", &kpath);
    int short_ts_index = -1, shortest = 0x3fffffff;
    for (int i = 1; i <= kpath; ++i) {
        int nc, kind = -1;
        // kind 0 simple tsc, 1 tsc, 2 c not ts,
        scanf("%d", &nc);
        if (nc <= ncity) kind = 2;
        vector<int> path;
        int curr;
        for (int j = 0; j < nc; ++j) {
            scanf("%d", &curr);
            path.emplace_back(curr);
        }
        if (kind == -1 && path[0] != path[nc - 1]) kind = 2;
        int dist = 0;
        bool visited[201] = {false}, un = false, repeat = false;
        visited[path[0]] = true;
        for (int k = 0; k < nc - 1; ++k) {
            if (graph[path[k]][path[k + 1]]) {
                dist += graph[path[k]][path[k + 1]];
                if (!visited[path[k + 1]]) visited[path[k + 1]] = true;
                else if (k + 1 != nc - 1) repeat = true;
            } else {
                un = true;
                kind = 2;
                break;
            }
        }
        if (kind != 2) {
            if (path[0] != path[nc - 1]) kind = 2;
            else {
                for (int j = 1; j <= ncity; ++j) {
                    if (!visited[j]) {
                        kind = 2;
                        break;
                    }
                }
                if (kind != 2) {
                    if (repeat) kind = 1;
                    else kind = 0;
                }
            }
        }
        printf("Path %d: ", i);
        if (un) printf("NA ");
        else {
            printf("%d ", dist);
            if (kind != 2 && dist < shortest) {
                shortest = dist;
                short_ts_index = i;
            }
        }
        switch (kind) {
            case 0:
                puts("(TS simple cycle)");
                break;
            case 1:
                puts("(TS cycle)");
                break;
            case 2:
                puts("(Not a TS cycle)");
                break;
        }
    }
    if (short_ts_index == -1) printf("Shortest Dist(NA) = NA\n");
    else
        printf("Shortest Dist(%d) = %d\n", short_ts_index, shortest);
    return 0;
}

1151 LCA in a Binary Tree (30 分)

这题是昨天自我感觉最好的一道题。就是不知道如果真在考场上，还能不能写成这个亚子。

建树
因为需要从孩子结点找祖先结点，所以在Node中加入Node* father （双向的二叉链表），在利用先序序列、中序序列建树时，就将lchild，rchild指向孩子，father指针指向父亲。
⚠️当孩子结点存在时，才root->child->father = root。（小心空指针！！！
查找结点，search用了递归的写法
找最深的共同祖先
这里利用了栈，从当前结点一层一层将祖先入栈。
那么两个栈的栈顶一定是相同的。
若栈顶相同，则出栈，一直到栈顶不同为止。
最后一个相同的栈顶元素则为最深公共祖先。

#include <cstdio>
#include <stack>

using namespace std;
struct Node {
    int key;
    Node *lchild = NULL, *rchild = NULL, *father = NULL;
};
int mpair, nn, in_order[10001], pre_order[10001];

Node *createBtree(int in_st, int in_ed, int pre_st, int pre_ed) {
    if (in_st > in_ed || pre_st > pre_ed) return NULL;
    Node *root = new Node;
    int rkey = pre_order[pre_st], pos = -1;
    for (int i = in_st; i <= in_ed; ++i) {
        if (in_order[i] == rkey) {
            pos = i;
            break;
        }
    }
    int lsize = pos - in_st;
    root->key = rkey;
    root->lchild = createBtree(in_st, pos - 1, pre_st + 1, pre_st + lsize);
    root->rchild = createBtree(pos + 1, in_ed, pre_st + lsize + 1, pre_ed);
    if (root->lchild) root->lchild->father = root;
    if (root->rchild) root->rchild->father = root;
    return root;
}

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

int main() {
    scanf("%d%d", &mpair, &nn);
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &in_order[i]);
    }
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &pre_order[i]);
    }
    Node *root = createBtree(0, nn - 1, 0, nn - 1);

    for (int j = 0; j < mpair; ++j) {
        int n1, n2;
        scanf("%d%d", &n1, &n2);
        Node *p1 = search(root, n1), *p2 = search(root, n2);
        if (!p1 && !p2) printf("ERROR: %d and %d are not found.\n", n1, n2);
        else if (!p1) printf("ERROR: %d is not found.\n", n1);
        else if (!p2) printf("ERROR: %d is not found.\n", n2);
        else {
            if (n1 == n2) {
                printf("%d is an ancestor of %d.\n", n1, n2);
                continue;
            }
            stack<int> fathers1, fathers2;
            Node *temp1 = p1, *temp2 = p2;
            while (temp1 != NULL) {
                fathers1.push(temp1->key);
                temp1 = temp1->father;
            }
            while (temp2 != NULL) {
                fathers2.push(temp2->key);
                temp2 = temp2->father;
            }
            int curr_a;
            while (!fathers1.empty() && !fathers2.empty()) {
                if (fathers1.top() == fathers2.top()) {
                    curr_a = fathers1.top();
                    fathers1.pop();
                    fathers2.pop();
                } else break;
            }
            if (curr_a == n1) {
                printf("%d is an ancestor of %d.\n", n1, n2);
            } else if (curr_a == n2) {
                printf("%d is an ancestor of %d.\n", n2, n1);
            } else printf("LCA of %d and %d is %d.\n", n1, n2, curr_a);
        }
    }
    return 0;
}

All for PAT秋考 | 2018.9PAT甲级题解

1148 Werewolf - Simple Version (20 分)

1149 Dangerous Goods Packaging (25 分)

1150 Travelling Salesman Problem (25 分)

1151 LCA in a Binary Tree (30 分)

建树

查找结点，search用了递归的写法

找最深的共同祖先

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读