All for PAT秋考 | 1136 - 1139

涉及知识

• 1136 大整数加法（字符串，这次用了c++ string）
• 1137 筛选分类排序，取整注意+0.5
• 1138 给定先序、中序，求后序第一个结点（建树易超时，不要沉迷模板️）
• 1139 dfs易超时，可降维存边集（还是 不要沉迷模板！！！）

1136 A Delayed Palindrome (20 分)

之前没用c++的string写过大整数加法。
跟char数组相比，要注意res一开始的初始化 string res(len, '0')，否则是不可以直接给res[i]赋值的，因为没有分配空间。
也可以在res中直接顺着保存加法结果（低位在前），最后再reverse。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void getSum(string &str, string &rev) {
    int len = str.length();
    string res(len, '0');
    int extra = 0, tsum = 0;
    for (int i = len - 1; i >= 0; i--) {
        tsum = extra + rev[i] + str[i] - '0' - '0';
        extra = tsum / 10;
        tsum %= 10;
        res[i] = tsum + '0';
    }
    if (extra) res.insert(0, 1, char(extra + '0'));
    str = res;
    rev = str;
    reverse(rev.begin(), rev.end());
}

int main() {
    string ori_str, rev;
    cin >> ori_str;
    rev = ori_str;
    reverse(rev.begin(), rev.end());
    int i = 0;
    while (rev != ori_str) {
        cout << ori_str << " + " << rev << " = ";
        getSum(ori_str, rev);
        cout << ori_str << endl;
        i++;
        if (i >= 10) {
            puts("Not found in 10 iterations.");
            return 0;
        }
    }
    printf("%s is a palindromic number.\n", ori_str.data());
    return 0;
}

1137 Final Grading (25 分)

读入平时编程成绩，先滤掉这项不达标的。
读入期中期末成绩时，比较并计算grade，取整时注意+0.5再强制转int取整。

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

using namespace std;

struct Stu {
    string name;
    int gp = -1, gm = -1, gf = -1, g = -1;

    bool operator<(const Stu &s2) const {
        if (g != s2.g) return g > s2.g;
        return name < s2.name;
    }
};

int main() {
    int np, nm, nn;
    scanf("%d%d%d", &np, &nm, &nn);
    char name[22];
    map<string, Stu> recs;
    int grade;
    for (int i = 0; i < np; ++i) {
        scanf("%s%d", name, &grade);
        if (grade >= 200) {
            recs[name].name = name;
            recs[name].gp = grade;
        }
    }
    for (int i = 0; i < nm; ++i) {
        scanf("%s%d", name, &grade);
        if (recs.find(name) != recs.end()) {
            recs[name].gm = grade;
        }
    }
    for (int i = 0; i < nn; ++i) {
        scanf("%s%d", name, &grade);
        if (recs.find(name) != recs.end()) {
            if (recs[name].gm > grade) {
                recs[name].g = int(0.4 * recs[name].gm + grade * 0.6 + 0.5);
            } else recs[name].g = grade;
            recs[name].gf = grade;
        }
    }
    set<Stu> res;
    for (auto &item: recs) {
        if (item.second.g >= 60) {
            res.insert(item.second);
        }
    }
    for (auto &item: res) {
        printf("%s %d %d %d %d\n", item.name.data(), item.gp, item.gm, item.gf, item.g);
    }
    return 0;
}

• 📅Nov. 1st 更新
  昨天随手又刷这题竟然卡最后一个测试点死都过不了。现在终于冷静下来读题发现了错误= =
  两个final grade分清楚
  60分当然是指总评了= =
  另外，cmath的round函数取整好用。

#include <cstdio>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Grade {
    string name;
    int p = -1, md = -1, fi = -1, gra = -1;

    bool operator<(const Grade &g2) const {
        if (gra != g2.gra) return gra > g2.gra;
        return name < g2.name;
    }
};

map<string, Grade> total;

int main() {
    int n1, n2, n3;
    scanf("%d%d%d", &n1, &n2, &n3);
    char id[22];
    int sc;
    while (n1--) {
        scanf("%s%d", id, &sc);
        if (sc >= 200) {
            total[id].p = sc;
            total[id].name = id;
        }
    }
    while (n2--) {
        scanf("%s%d", id, &sc);
        if (total.find(id) != total.end())
            total[id].md = sc;
    }
    vector<Grade> res;
    while (n3--) {
        scanf("%s%d", id, &sc);
        if (total.find(id) != total.end()) {
            Grade g = total[id];
            g.fi = sc;
            if (g.md > g.fi) g.gra = round(g.md * 0.4 + g.fi * 0.6);
            else g.gra = g.fi;
            if (g.gra >= 60) res.emplace_back(g);
        }
    }
    sort(res.begin(), res.end());
    for (auto &item:res) {
        printf("%s %d %d %d %d\n", item.name.data(), item.p, item.md, item.fi, item.gra);
    }
    return 0;
}

1138 Postorder Traversal (25 分)

这题一上来先写了个由中序先序建树的模板，再后序遍历找第一个，然后超时了……
于是不得不冷静分析：
找后序序列的第一个，那它一定是一个叶子结点，不然它之前一定会有孩子先输出。
于是问题就变成：按照后序遍历「左 根 右」找第一个叶子。

• 若有左子树，在左子树中找叶子；
• 若无左子树，在右子树中找叶子；
• 若没有子树，那本身就是叶子，结束。

由此，可以写出循环、递归两种形式。

• 循环
  in_st，in_ed标示当前查找叶子的下标范围（中序）。

#include <cstdio>

int _pre[50001], _in[50001];

int main() {
    int nn;
    scanf("%d", &nn);
    for (int i = 0; i < nn; ++i) scanf("%d", &_pre[i]);
    for (int i = 0; i < nn; ++i) scanf("%d", &_in[i]);
    int in_st = 0, in_ed = nn - 1, in_rpos, pre_rpos = 0;
    while (in_st < in_ed) {
        in_rpos = in_st;
        while (_in[in_rpos] != _pre[pre_rpos]) in_rpos++;
        if (in_rpos > in_st) { // lchild not null
            in_ed = in_rpos - 1;
        } else if (in_rpos < in_ed) { // lchild null && rchild not null
            in_st = in_rpos + 1;
        } else break; // is a leaf
        pre_rpos += 1;
    }
    printf("%d", _in[in_st]);
    return 0;
}

• 递归

#include <cstdio>

int _pre[50001], _in[50001];
bool flag = true;

void first_leaf(int in_st, int in_ed, int pre_st) {
    if (!flag || in_st > in_ed) return;
    int rpos = in_st;
    while (_in[rpos] != _pre[pre_st]) rpos++;
    first_leaf(in_st, rpos - 1, pre_st + 1);
    //没有左子树才会走到右子树这里 所以pre的起点是pre_st + 1（右子树根）
    first_leaf(rpos + 1, in_ed, pre_st + 1);
    if (flag) {
        printf("%d\n", _in[in_st]);
        flag = false;
    }
}

int main() {
    int nn;
    scanf("%d", &nn);
    for (int i = 0; i < nn; ++i) scanf("%d", &_pre[i]);
    for (int i = 0; i < nn; ++i) scanf("%d", &_in[i]);
    first_leaf(0, nn - 1, 0);
    return 0;
}

1139 First Contact (30 分)

自己写的DFS在超时的边缘反复试探呐……190ms真的️，我感觉已经做了剪枝了呀。。。。。。
于是参考liuchuo大佬的降维了一波，另外存了边集map<int, bool> edges，第一个int分高四位、低四位表示了两个顶点。
️同性之间也可以这么介绍的……
A想认识B，只需找到A的同性朋友C，B的同性朋友D，且C、D也是朋友就行了。
另外stl容器套在一起还是可以直接排序的，stl大概重载过比大小了，套几层都ok，省事。

• DFS

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> graph[10000], temp_path;
int gender[10000] = {0};
int nq, src, target;

int _info(char id[]) {
    int res;
    if (id[0] == '-') {
        sscanf(id, "-%d", &res);
        gender[res] = -1;
    } else {
        sscanf(id, "%d", &res);
        gender[res] = 1;
    }
    return res;
}

vector<vector<int>> res;

void DFS(int root, int step) {
    if (root == target || step >= 4) {
        if (root == target && step == 4)
            res.emplace_back(temp_path);
        return;
    }
    int curr = gender[src];
    if (step > 1) {
        if (gender[target] != gender[src]) curr = -gender[src];
        temp_path.emplace_back(root);
    }
    for (auto item:graph[root]) {
        if ((gender[item] == curr && step < 3 && item != src && item != target) || (step == 3 && item == target)) {
            DFS(item, step + 1);
        }
    }
    if (step > 1) temp_path.pop_back();
}

int main() {
    int nn, mm;
    scanf("%d%d", &nn, &mm);
    char sp1[6], sp2[6];
    for (int i = 0; i < mm; ++i) {
        scanf("%s%s", sp1, sp2);
        int p1 = _info(sp1), p2 = _info(sp2);
        graph[p1].emplace_back(p2), graph[p2].emplace_back(p1);
    }
    scanf("%d", &nq);
    for (int i = 0; i < nq; ++i) {
        scanf("%s%s", sp1, sp2);
        src = _info(sp1), target = _info(sp2);
        if (gender[target] == 0) {
            puts("0");
            continue;
        }
        DFS(src, 1);
        printf("%lu\n", res.size());
        sort(res.begin(), res.end());
        for (auto &item:res) {
            printf("%04d %04d\n", item[0], item[1]);
        }
        res.clear();
    }
    return 0;
}

• 降维存边集

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <unordered_map>

using namespace std;
vector<int> graph[10000];
unordered_map<int, bool> edges;
int gender[10000] = {0};
int nq, src, target;

int _info(char id[]) {
    int res;
    if (id[0] == '-') {
        sscanf(id, "-%d", &res);
        gender[res] = -1;
    } else {
        sscanf(id, "%d", &res);
        gender[res] = 1;
    }
    return res;
}

int main() {
    int nn, mm;
    scanf("%d%d", &nn, &mm);
    char sp1[6], sp2[6];
    for (int i = 0; i < mm; ++i) {
        scanf("%s%s", sp1, sp2);
        int p1 = _info(sp1), p2 = _info(sp2);
        graph[p1].emplace_back(p2), graph[p2].emplace_back(p1);
        edges[10000 * p1 + p2] = edges[10000 * p2 + p1] = true;
    }
    scanf("%d", &nq);
    for (int i = 0; i < nq; ++i) {
        scanf("%s%s", sp1, sp2);
        src = _info(sp1), target = _info(sp2);
        int g1 = gender[src], g2 = gender[target];
        set<int> f1, f2;
        for (auto item:graph[src]) {
            if (gender[item] == g1 && item != target)
                f1.insert(item);
        }
        for (auto item:graph[target]) {
            if (gender[item] == g2 && item != src)
                f2.insert(item);
        }
        vector<pair<int, int>> res;
        for (auto item: f1) {
            for (auto item1:f2) {
                if (edges[item * 10000 + item1])
                    res.emplace_back(item, item1);
            }
        }
        printf("%lu\n", res.size());
        for (auto item: res) {
            printf("%04d %04d\n", item.first, item.second);
        }
    }
    return 0;
}