All for PAT秋考 | 可能是2016.3甲级

20 25 25 30

输入处理

• sstream

#include <iostream>
#include <sstream>

stringstream ss;
string str;
// ss.clear();
cin >> str;
ss << str;
if (str[0]!='-') {
    int a;
    ss >> a;
    cout << a;
}

• sprintf

#include <cstdio>

char curr_format[110], curr_num[110];; 
scanf("%s", curr_num);
sscanf(curr_num, "%lf", &curr_in);
sprintf(curr_format, "%.2lf", curr_in);

---

花里胡哨最短路的注意点

• 图的存储尽量用邻接矩阵（回溯方便）

• Dijkstra得最短路径长度，维护pre数组（set<int> pre[MAXN]或map<int, set<int>> pre），DFS回溯得到具体路径（注意传参，注意递归边界，注意路径维护）。

1108 Finding Average (20 分)

#include <cstdio>

int main() {
    int nn, cnt = 0;
    double total = 0.0;
    scanf("%d", &nn);
    char curr_num[110];
    while (nn--) {
        double curr_in;
        char curr_format[110];
        scanf("%s", curr_num);
        sscanf(curr_num, "%lf", &curr_in);
        sprintf(curr_format, "%.2lf", curr_in);
        int in_format = 1;
        for (int i = 0; curr_num[i]; ++i) {
            if (curr_num[i] != curr_format[i]) {
                in_format = 0;
                break;
            }
        }
        if (in_format) {
            if (curr_in < -1000 || curr_in > 1000) {
                in_format = 0;
            }
        }
        if (in_format) {
            total += curr_in;
            cnt++;
        } else {
            printf("ERROR: %s is not a legal number\n", curr_num);
        }
    }
    if (cnt == 0) {
        printf("The average of 0 numbers is Undefined\n");
    } else if (cnt == 1) {
        printf("The average of 1 number is %.2lf\n", total / cnt);
    } else {
        printf("The average of %d numbers is %.2lf\n", cnt, total / cnt);
    }
    return 0;
}

---

1109 Group Photo (25 分)

#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;
struct Person {
    string name;
    int HH;
} people[10001];

bool cmp(const Person &p1, const Person &p2) {
    if (p1.HH != p2.HH) return p1.HH > p2.HH;
    return p1.name < p2.name;
}

int main() {
    int form[10][10001];
    int nn, nrow;
    scanf("%d%d", &nn, &nrow);
    char name[10];
    for (int i = 0; i < nn; ++i) {
        scanf("%s%d", name, &people[i].HH);
        people[i].name = name;
    }
    sort(people, people + nn, cmp);
    int n_each = nn / nrow;
    int n_last = nn % n_each + n_each;
    int curr = 0;
    form[0][n_last / 2] = curr++;
    for (int i = 1; i <= n_last / 2; i++) {
        if (n_last / 2 - i >= 0)form[0][n_last / 2 - i] = curr++;
        if (n_last / 2 + i < n_last)form[0][n_last / 2 + i] = curr++;
    }
    for (int i = 0; i < n_last; ++i) {
        printf("%s", people[form[0][i]].name.data());
        printf(i == n_last - 1 ? "\n" : " ");
    }
    for (int i = 1; i < nrow; ++i) {
        form[i][n_each / 2] = curr++;
        for (int j = 1; j <= n_each / 2; ++j) {
            if (n_each / 2 - j >= 0) form[i][n_each / 2 - j] = curr++;
            if (n_each / 2 + j < n_each) form[i][n_each / 2 + j] = curr++;
        }
    }
    for (int k = 1; k < nrow; ++k) {
        for (int i = 0; i < n_each; ++i) {
            printf("%s", people[form[k][i]].name.data());
            printf(i == n_each - 1 ? "\n" : " ");
        }
    }
    return 0;
}

---

1110 Complete Binary Tree (25 分)

判断是否为完全二叉树（下标从0开始）

• 在读入时判断：若左孩子不存在且右孩子存在，则不是CBT，结束。若是，下一步。
  （读入时还要确定根结点）
• 递归建树时判断：若位置为pos的结点x左孩子存在，且左孩子结点位置2*pos + 1 >= 结点数，则不是CBT，结束。
• 返回，是。

若建树后再判断是否为完全二叉树，也可考虑下面的方法。

选择在建树时判断的原因是，使用了数组来实现二叉树，直接建树若形成一棵链条状的数，需要的空间将达到指数级⚠️。

#include <iostream>
#include <string>
#include <sstream>

using namespace std;
int NN, btree[101], child[21][2];
bool isRoot[21];

bool createTree(int pos, int key) {
    btree[pos] = key;
    int lc = child[key][0], rc = child[key][1];
    if (lc != -1 && 2 * pos + 1 >= NN) return false;
    if (rc != -1) { // lc rc
        if (!createTree(2 * pos + 1, lc))
            return false;
        if (!createTree(2 * pos + 2, rc))
            return false;
    } else if (lc != -1) { // lc -
        if (!createTree(2 * pos + 1, lc))
            return false;
    }
    return true;
}

int main() {
    fill(isRoot, isRoot + 21, true);
    bool isBT = true;
    cin >> NN;
    stringstream ss;
    for (int i = 0; i < NN; ++i) {
        string sl, sr;
        int lc = -1, rc = -1;
        cin >> sl >> sr;
        if (sl[0] != '-') {
            ss.clear();
            ss << sl;
            ss >> lc;
            isRoot[lc] = false;
        }
        if (sr[0] != '-') {
            ss.clear();
            ss << sr;
            ss >> rc;
            isRoot[rc] = false;
        }
        child[i][0] = lc, child[i][1] = rc;
        if (lc == -1 && rc != -1) isBT = false;
    }
    int root = 0;
    for (; root < NN; ++root) {
        if (isRoot[root]) break;
    }
    if (!isBT) {
        printf("NO %d\n", root);
        return 0;
    }
    if (createTree(0, root)) {
        printf("YES %d\n", btree[NN - 1]);
    } else printf("NO %d\n", root);
    return 0;
}

---

1111 Online Map (30 分)

• 分别按照路径长度，耗时进行一次Dijkstra，并分别建立前驱结点集合.
• 按照Dijkstra的前驱结点集合，分别DFS回溯。注意在递归时维护路径，在递归边界时，更新最佳路径。注意DFS的传参。
• ⚠️ 能用邻接矩阵，就别用邻接表（pre集合回溯时，邻接矩阵比邻接表方便不少）

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

using namespace std;
const int INF = 0x3fffffff;
int nn, mm, src, target;
struct Way {
    int len = INF, time = INF;
};
int mtime = INF, mdepth = INF;
vector<int> best_time_path, temp_time_path, shortest, temp_shortest;
Way graph[501][501];
int min_dist[501], min_time[501];
map<int, set<int> > dpre, tpre;

void Dijkstra_length(int root) {
    fill(min_dist, min_dist + 501, INF);
    bool visited[501] = {false};
    min_dist[root] = 0;
    for (int i = 0; i < nn; ++i) {
        int curr = -1, mmin = INF;
        for (int j = 0; j < nn; ++j) {
            if (!visited[j] && min_dist[j] < mmin) {
                mmin = min_dist[j];
                curr = j;
            }
        }
        if (curr != -1) {
            visited[curr] = true;
            for (int k = 0; k < nn; k++) {
                if (graph[curr][k].len != INF) {
                    int new_dist = min_dist[curr] + graph[curr][k].len;
                    if (new_dist < min_dist[k]) {
                        min_dist[k] = new_dist;
                        dpre[k].clear();
                        dpre[k].insert(curr);
                    } else if (new_dist == min_dist[k]) {
                        dpre[k].insert(curr);
                    }
                }
            }
        } else return;
    }
}

void Dijkstra_time(int root) {
    fill(min_time, min_time + 501, INF);
    bool visited[501] = {false};
    min_time[root] = 0;
    for (int i = 0; i < nn; ++i) {
        int curr = -1, mmin = INF;
        for (int j = 0; j < nn; ++j) {
            if (!visited[j] && min_time[j] < mmin) {
                mmin = min_time[j];
                curr = j;
            }
        }
        if (curr != -1) {
            visited[curr] = true;
            for (int k = 0; k < nn; k++) {
                if (graph[curr][k].len != INF) {
                    int newt = min_time[curr] + graph[curr][k].time;
                    if (newt < min_time[k]) {
                        min_time[k] = newt;
                        tpre[k].clear();
                        tpre[k].insert(curr);
                    } else if (newt == min_time[k]) {
                        tpre[k].insert(curr);
                    }
                }
            }
        } else return;
    }
}

void DFS(int root, int time_sum) { // according to dpre[root]
    if (root == src) {
        temp_shortest.emplace_back(root);
        if (time_sum < mtime) {
            shortest = temp_shortest;
            mtime = time_sum;
        }
        temp_shortest.pop_back();
        return;
    }
    temp_shortest.emplace_back(root);
    for (auto item:dpre[root]) {
        DFS(item, time_sum + graph[item][root].time);
    }
    temp_shortest.pop_back();
}

void DFS_depth(int root, int depth) { // according to tpre[]
    if (root == src) {
        temp_time_path.emplace_back(root);
        if (depth < mdepth) {
            best_time_path = temp_time_path;
            mdepth = depth;
        }
        temp_time_path.pop_back();
        return;
    }
    temp_time_path.emplace_back(root);
    for (auto item:tpre[root]) {
        DFS_depth(item, depth + 1);
    }
    temp_time_path.pop_back();
}

int main() {
    scanf("%d%d", &nn, &mm);
    int v1, v2, one_way, length, time;
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d%d%d%d", &v1, &v2, &one_way, &length, &time);
        graph[v1][v2].len = length, graph[v1][v2].time = time;
        if (one_way == 0) graph[v2][v1].len = length, graph[v2][v1].time = time;;
    }
    scanf("%d%d", &src, &target);
    Dijkstra_length(src);
    Dijkstra_time(src);
    DFS(target, 0); // get one path with min_time
    DFS_depth(target, 1); // get one path with min_intersection
    if (shortest == best_time_path) {
        printf("Distance = %d; Time = %d: ", min_dist[target], mtime);
        for (int i = mdepth - 1; i >= 0; --i) {
            printf("%d", shortest[i]);
            printf(i == 0 ? "\n" : " -> ");
        }
    } else {
        printf("Distance = %d: ", min_dist[target]);
        for (int i = shortest.size() - 1; i >= 0; --i) {
            printf("%d", shortest[i]);
            printf(i == 0 ? "\n" : " -> ");
        }
        printf("Time = %d: ", min_time[target]);
        for (int i = mdepth - 1; i >= 0; --i) {
            printf("%d", best_time_path[i]);
            printf(i == 0 ? "\n" : " -> ");
        }
    }
    return 0;
}