上周末, 2019年9月8日, 终于结束了我 PAT 甲级的首次考试, 成绩 37/100, 1246/3943 (分数,排名), 伤心之余, 记录并总结这次难得的经历与经验, 他日回首,方可对自己臭骂一句: 弱爆了.

贴出教育超市线上模拟后重新AC后的代码导出分析

7-1 Forever (20 分)

作者: 陈越, 单位: 浙江大学, 时间限制: 3000 ms, 内存限制: 64 MB

“Forever number” is a positive integer A with K digits, satisfying the following constrains:

the sum of all the digits of A is m

the sum of all the digits of A+1 is n; and

the greatest common divisor of m and n is a prime number which is greater than 2.

Now you are supposed to find these forever numbers.

Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤ 5). Then N lines follow, each gives a pair of K (3 < K < 10) and m (1 < m < 90), of which the meanings are given in the problem description.

Output Specification:
For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.

Sample Input:
2
6 45
7 80

Sample Output:
Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

这次的第一题坑了很多人, 以往的真题通常第一题都是十几分钟就能搞定的, 但是这次这个题的通过率是最低的. =_=!!

大致题意: 定义一个”永远数”, 满足以下条件: 一个正整数 A 有k 位, 其每一位相加和为 m, 而 A+1 的每一位相加和为 n, 并且 m 和 n 的 最大公约数 (这里把我坑惨了)是一个 大于2 的素数
答题过程: 开考后, 花一分钟读完第一题, 立马瞟了一眼时间限制, 给了3秒的时间, 那么长, 绝对是暴力法搞定. 立马把判定素数的函数先写出来
1
2
3
4
5
6
7
bool isPrime(int x) {
if (x <= 1) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
然后开始暴力枚举, 最初想的是k位, 假如是4位, 那么范围就是[1000, 9999], 用pow函数很轻松就得到
1
2
minValue = pow(10, k - 1);
maxValue = pow(10, k) - 1;
然后依次获得每个数的各位之和 m 和 n, 再之后看一眼第三个定义条件, 抠脚操作就在这里开始了, divisor, divide是除的意思好的, divisor 是除数. 然后用 m 和 n 中较大的除以较小的, 尝试提交样例测试代码,,,什么卵都没有, 错了, 哪错了, 从头到尾检查一遍代码, 难道不是 除数?, 余数是 remainder 啊, 不管了, 试试吧, 用大的数对小的数取余, 测试一次样例, 我去还是什么卵都没有, 难道是两数只差, 不可能, 但是也试试吧, 果不其然还是错. 放弃吧, 第一题用一个小时还没搞定我也是醉了. 然后第二题, 链表题, 噼里啪啦..对了, 终于AC了一道题, 心态好了些, 回到第一题, 再仔细读一遍题吧, 以前做真题因为没仔细读题错了好多次, public common divisor 最大公共除数不就是最大公约数吗, 换个叫法就不知道了我去. 这下恍然大悟, 但是又蒙了, 求最大公约数的代码好久没写过了, 怎么求? 突然脑子里想到大一学C语言的一个场景–”老冯说, 辗转相除法”, 我去就是这个, 但是怎么辗转呢哈哈, 一顿噼里啪啦推导了几分钟, 搞定了, 开心地提交代码. 只过了两个样例, 12分, 啊, 暴力法时间复杂度 O(n¹⁰·k) 相对时间限制太高了. 绝望了, 第一题死活搞不定吗. 计时器只剩下70+分钟, 最后两题都没做, 先做后面的题吧…

当时提交的代码:

#include <cstdio>
#include <cmath>
using namespace std;
int n, k, m;

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

int gcd(int a, int b) {
    if (b < a) swap(a, b);
    int c = b % a;
    while (c != 0) {
        b = a;
        a = c;
        c = b % a;
    }
    return a;
}

int getSum(int x) {
    int sum = 0;
    while (x != 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        printf("Case %d\n", i);
        scanf("%d%d", &k, &m);
        int minValue = pow(10, k - 1);
        int maxValue = pow(10, k) - 1;
        bool flag = false;
        for (int j = minValue; j <= maxValue; j++) {
            int dm = getSum(j), dn = getSum(j + 1);
            if (dm == m) {
                int div = gcd(dm, dn);
                if (isPrime(div) && div > 2) {
                    flag = true;
                    printf("%d %d\n", dn, j);
                }
            }
        }
        if (!flag) {
            printf("No Solution\n");
        }
    }
    return 0;
}

之后回来的第三天, 知乎上开始出现讨论 参加2019年9月8日秋季PAT测试是怎样的一种体验? 的话题, PAT的创始人兼主出题人陈越姥姥在里面回答各种问题, 大多都是吐槽最后二十分钟服务器崩掉不能提交和看题以及吐槽第一题暴力难AC的, 都被第一题难倒啦, 哈哈, 各种解法层出不穷: 暴力法, 打表, 排序, DFS… 但是姥姥说这题她的时间限制就是按照暴力解法定的, 今天我耐心的打表找一下规律, 每个满足条件的”Forever number”最后两位一定是 99, 考试的时候真的太蠢了, 如果不是99, 那么m和n差值为1, 最大公约数只能是1, 怎么可能大于2. 改进了局部代码试了一下:

int minValue = pow(10, k - 1 - 2);
int maxValue = pow(10, k - 2) - 1;
bool flag = false;
for (int j = minValue; j <= maxValue; j++) {
    int dm = getSum(j) + 18, dn = getSum(j * 100 + 99 + 1);
    if (dm == m) {
        int div = gcd(dm, dn);
        if (isPrime(div) && div > 2) {
            flag = true;
            printf("%d %d\n", dn, j);
        }
    }
}

既然最后两位一定是99, 那么一个 k 位数, 我只需要枚举 k-2 位数, 然后*100+99得到实际数值即可, 改进之后, 在 PTA拼题教育超市重新购买考试卷模拟考试之后, 重新提交代码, 有进步, 最后一个测试样例不超时了, 但是第三个样例显示错误, ~~这个问题到现在还没想明白, 也没看到哪个网友用暴力法最终解决了这个问题, 若有读者看到此处麻烦指点一二.~~ 就在刚刚(2019/09/15 18:38)想明白了, 题目最后说了这么一段话: If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution. 题目最后说按照 n 升序输出, 如果答案不唯一按照 A 升序输出, 马上告诉我朋友谷雨斌, 哈哈他和我一起破口大骂: 卧槽!!!, 因为他只差这一个测试点就能拿到满分, 这尼玛已经不是第一次做题栽在看题上了, 我的印象里只有按照 A 升序, 读文章只看首和尾, 卧槽.

试试方式二: DFS

考试结束我朋友说这题他用DFS做了两个小时, 虽然最后因为读题导致第三个测试点没通过, 但是这题用DFS的思路真的不会去想, 哪有第一题就用深度优先搜索的, 疯了, 静下来冷静思考, 确实DFS最容易解题啊, 然后 剪枝(用DFS的关键所在) 减少搜索深度.

思路: k 位数, 考虑枚举分别以[1-9]开头的所有数(排除以0开头的情况, 否则就会出现 k - 1 位数的情况), 因为要记录 当前数值, 位数, 各位数之和, 所以在DFS函数中加入 number, numDigit, sumD 作为参数, 得到以下代码:

void dfs(int number, int numDigit, int sumD) {
    if (sumD > m) return;
    if (sumD + 9 * (k - numDigit) < m) return;
    if (numDigit == k) {
        if (sumD != m) return;
        int n = getDigitSum(number + 1);
        int x = gcd(m, n);
        if (x > 2 && isPrime(x)) {
            ans.push_back({n,number});
        }
        return;
    }
    for (int i = 0; i <= 9; i++) {
        dfs(number * 10 + i, numDigit + 1, sumD + i);
    }
}

这段递归函数中有两个 死胡同 :

如果当前数值的各位之和已经大于m, 那么就没必要继续往下递归, 需要返回, 于是得到 if (sumD != m) return;
假设当前记录的位数已有5位, 那么剩余位数就为 k - 5 位, 如果这 k - 5 位数都取9, 且此时的各位之和加上 9 * (k - 5) 都不能达到m的话, 说明后面的情况均不能得到结果, 需要及时返回 (也就是所谓的回溯), 于是得到 if (sumD + 9 * (k - numDigit) < m) return;, 如果不做剪枝样例4仍然是超时的.

最后将符合的结果 push 进vector中, 因为排序有两个条件, 所以定义一个 node 结构体来表示一个正确结果, 最后sort函数排序即可. 今天刚AC的代码:

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    int n, v;
};
int n, k, m;
bool flag;
vector<node> ans;

bool cmp(node a, node b) {
    if (a.n != b.n) return a.n < b.n;
    return a.v < b.v;
}

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

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int getDigitSum(int x) {
    int sumD = 0;
    while (x != 0) {
        sumD += x % 10;
        x /= 10;
    }
    return sumD;
}

void dfs(int number, int numDigit, int sumD) {
    if (sumD > m) return;
    if (sumD + 9 * (k - numDigit) < m) return;
    if (numDigit == k) {
        if (sumD != m) return;
        int n = getDigitSum(number + 1);
        int x = gcd(m, n);
        if (x > 2 && isPrime(x)) {
            ans.push_back({n,number});
        }
        return;
    }
    for (int i = 0; i <= 9; i++) {
        dfs(number * 10 + i, numDigit + 1, sumD + i);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        printf("Case %d\n", i);
        scanf("%d%d", &k, &m);
        ans.clear();
        for (int j = 1; j <= 9; j++) {
            dfs(j, 1, j);
        }
        if (ans.size() == 0) {
            printf("No Solution\n");
        } else {
            sort(ans.begin(), ans.end(), cmp);
            for (auto it : ans) {
                printf("%d %d\n", it.n, it.v);
            }
        }
    }
    return 0;
}

这是最快的方法的解法, 最耗时的样例也只用了 3ms, 最后, 有始有终, 把最初使用的暴力法也给AC了, 不过同样要优化枚举次数 (即限定最后两个数为 99), 代码如下:

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int n, k, m;
struct node {
    int n, v;
};
vector<node> ans;

bool cmp(node a, node b) {
    if (a.n != b.n) return a.n < b.n;
    else return a.v < b.v;
}

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

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int getDigitSum(int x) {
    int sumD = 0;
    while (x != 0) {
        sumD += x % 10;
        x /= 10;
    }
    return sumD;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        printf("Case %d\n", i);
        scanf("%d%d", &k, &m);
        int minValue = pow(10, k - 1 - 2);
        int maxValue = pow(10, k - 2) - 1;
        ans.clear();
        for (int j = minValue; j <= maxValue; j++) {
            int dm = getDigitSum(j) + 18, dn = getDigitSum(j * 100 + 99 + 1);
            if (dm == m) {
                int div = gcd(dm, dn);
                if (isPrime(div) && div > 2) {
                    ans.push_back({dn, j * 100 + 99});
                }
            }
        }
        if (ans.size() == 0) {
            printf("No Solution\n");
        } else {
            sort(ans.begin(), ans.end(), cmp);
            for (auto it : ans) {
                printf("%d %d\n", it.n, it.v);
            }
        }
    }
    return 0;
}

7-2 Merging Linked Lists (25 分)

作者: 陈越, 单位: 浙江大学, 时间限制: 400 ms, 内存限制: 64 MB

Given two singly linked lists L₁ = a₁→a₂→⋯→a_n−1→a_n and L₂ = b₁→b₂→⋯→b_m−1→bm . If n ≥ 2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a₁→a₂→b_m→a₃→a₄→b_m−1⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

Input Specification:
Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L₁ and L₂ , plus a positive N (≤ 10⁵) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is a positive integer no more than 10⁵ , and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

Output Specification:
For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 01000 7
2233 2 34891
0100 6 00001
4891 3 10086
1000 1 02233
0033 5 -1
0086 4 00033
0001 7 -1

Sample Output:
1000 1 02233
2233 2 00001
0001 7 34891
4891 3 10086
0086 4 00100
0100 6 00033
0033 5 -1

这道最常规的题成为这四道题里我唯一AC的题（┬＿┬）. 前面第一题因为最大公约数的原因, 我直接跳到了第二题, 看到这样的题, 就会莫名有亲切感, 链表, 最容易了, 哈哈.

大致题意: 有L1,L2两个链表, 如果L1的长度 >= 2倍的L2长度, 则把L2中的元素逆序插入L1中, 插入规则: 从L1的首结点开始, 每碰到两个结点就从L2的末尾取一个结点插入L1的当前位置之后.
思路: 这种题如果按照链表的做法思路就很清晰了, 因为PAT的链表题都是给定结点地址和后继结点地址的, 显然这不是内存地址, 所以一定是用静态链表来表示链表结构.
解题步骤:
1. 逆置链表L2, 因为所给的链表都没有头结点, 为了逆置链表, 必须自行添加一个头结点, 为了避免使用已有结点的地址, 所以头结点的指针(即数组中的索引)需要从 maxn - 1 往前取, 然后其后继指针指向链表的第一个元素.
2. 然后遍历设 p 指针, 遍历长链表, 遍历过程中通过 cnt 计数, 达到2, 则插入短链表的第一个结点, 然后重置 cnt 为 0.

当时提交的代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;

struct node {
    int data, address, next;
} Node[maxn];

int reverseList(int start) {
    int head = maxn - 1;
    Node[head].next = start;
    int last = Node[head].next, p = Node[last].next;
    while (p != -1) {
        Node[last].next = Node[p].next;
        Node[p].next = Node[head].next;
        Node[head].next = p;
        p = Node[last].next;
    }
    return Node[head].next;
}

void printList(int head) {
    int p = head;
    while (p != -1) {
        printf("%05d %d ", Node[p].address, Node[p].data);
        if (Node[p].next == -1) printf("-1\n");
        else printf("%05d\n", Node[p].next);
        p = Node[p].next;
    }
}

int getLen(int head){
    int p = head, len = 0;
    while (p != -1) {
        p = Node[p].next;
        len++;
    }
    return len;
}

int main() {
    int head1, head2, n, address;
    scanf("%d%d%d", &head1, &head2, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &address);
        scanf("%d%d", &Node[address].data, &Node[address].next);
        Node[address].address = address;
    }
    int len1 = getLen(head1), len2 = getLen(head2);
    if (len1 == 0) printList(head2);
    else if (len2 == 0) printList(head1);
    else {
        int q, p;
        if (len1 >= len2 * 2) {
            p = head1;
            q = reverseList(head2);
        } else if (len2 >= 2 * len1) {
            p = head2;
            q = reverseList(head1);
        }
        int cnt = 0;
        while (p != -1 && q != -1) {
            if (++cnt == 2) {
                int temp = Node[q].next;
                Node[q].next = Node[p].next;
                Node[p].next = q;
                p = Node[p].next;
                q = temp;
                cnt = 0;
            }
            p = Node[p].next;
        }
        printList(head);
    }
    return 0;
}

后来思考中间有一部分逻辑判断是无用, 但是考试的时候一看AC了也就没管了.

然而这就开心了吗, 哎, 做过PAT的所有真题, 链表题通常都不是用链表的方法做的, 考试的时候没想这么多, 虽然AC了, 但是这题做了四十多分钟, 今天教育超市重新模拟, 换了另一种常规解法: 因为, 提交代码后的测试样例只检验输出结果是否正确, 并不分析源码, 所以只需要所得一个结果而不是真的去改变链表的结构.

思路: 遍历L1, L2把结点分别 push 进vector中 (定义vecotr<node> l1, l2), 另外声明一个同样类型的变量 ans(解题的常规操作), 遍历较长的链表把其结点依次 push 进 ans 中, 每插入两个结点就从l2结尾取一个结点插入 ans.

代码如下:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100010;
struct node {
    int adr, data, next;
} Node[maxn];
vector<node> l1, l2, ans;
void generateList(vector<node> &L, int head) {
    int p = head;
    while (p != -1) {
        L.push_back(Node[p]);
        p = Node[p].next;
    }
}

void printList(vector<node> L) {
    if (L.size() == 0) return;
    for (int i = 0; i < L.size() - 1; i++) {
        printf("%05d %d %05d\n", L[i].adr, L[i].data, L[i + 1].adr);
    }
    printf("%05d %d -1\n", L[L.size() - 1].adr, L[L.size() - 1].data);
}

int main() {
    int h1, h2, n, adr;
    cin >> h1 >> h2 >> n;
    for (int i = 0; i < n; i++) {
        cin >> adr;
        cin >> Node[adr].data >> Node[adr].next;
        Node[adr].adr = adr;
    }
    generateList(l1, h1);
    generateList(l2, h2);
    if (l1.size() < l2.size()) {
        swap(l1, l2);
    }
    if (l1.size() >= l2.size() * 2) {
        int cnt = 0, pos = l2.size() - 1;
        for (auto it : l1) {
            ans.push_back(it);
            if (++cnt % 2 == 0 && pos >= 0) {
                ans.push_back(l2[pos--]);
            }
        }
    }
    printList(ans);
    return 0;
}

注意点: generateList 函数中的第一个参数 L 必须用引用类型.

用 vector 来解决链表问题是最常用的手段, 也能极大缩短编码时间. 这道题虽然AC了, 但是一开始用了蠢办法浪费了太多考试时间.

7-3 Postfix Expression (25 分)

作者: 陈越, 单位: 浙江大学, 时间限制: 400 ms, 内存限制: 64 MB

Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i -th line corresponds to the i -th node) in the format:

data left_child right_child

where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by −1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.

Output Specification:
For each case, print in a line the postfix expression, with parentheses reflecting the precedences of the operators.There must be no space between any symbols.

Sample Input 1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1

Sample Output 1:
(((a)(b)+)((c)(-(d))*)*)

Sample Input 2:
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1

Sample Output 2:
(((a)(2.35)*)(-((str)(871)%))+)

这道题目初次瞄到这两张Figure的时候, 看了一眼输入输出样例, 与我当初看过的一道计算器算法题尤为相似, 非递归求解非常复杂, 当时没细看, 心想: 我去, 怕什么来什么吗. 所以直接跳到了下题. 直到今天重新做题, 我太抓狂了, 这道题非常非常的简单, 十几分钟就能写完的题目, 我考试的时候连提交都没有提交啊.

题意: 后缀表达式, 通过输出括弧表示操作符的优先级.

思路: 给出的结构是二叉树(静态二叉树表示), 如果只是后缀表达的话, 就非常简单, 只用 递归的后序遍历 即可, 像这样:

void postOrder(int root) {
    if (root == -1) return;
    postOrder(Node[root].lchild);
    postOrder(Node[root].rchild);
    cout << Node[root].data;
}

用 Figure1 举例, 在后序遍历输出第一个数 a 的时候, 前面需要输出3个左括弧, 这实际上对应了 a 所在的层数(也就对应了递归调用 postOrder 的深度), 所以需要在当前结点向左孩子递归之前就输出这个 ( , 同时, 输出一个操作数之后需要立马输出一个 ) , 所以最后会得到这样的代码:

void postOrder(int root) {
    if (root == -1) return;
    cout << "(";
    postOrder(Node[root].lc);
    postOrder(Node[root].rc);
    cout << Node[root].v;
    cout << ")";
}

先运行一下代码测试第一个样例, 得到这样的输出:

1	(((a)(b)+)((c)((d)-)))

看着感觉像回事了, 但是发现 d 的后面的负号实际上不是空字符-d, 而是表示 d 是个负数, 所以如果某一个操作符如果 左子树为空, 右子树不为空, 就说明这个符号是用来表示正负号的, 不应该放到这个操作数的后面. 所以思路就变得清晰了: 操作符比操作数先输出, 对应到二叉树的结构中就是根节点先输出再输出孩子结点, 也就是 先序或中序遍历, 但是这里一定是从二叉树的最左侧结点开始输出, 所以不可能再是先序遍历了, 于是很容易就得到以下代码:

bool isOperator(string str) {
    return str == "-" || str == "/" || str == "*" || str == "+";
}

void postOrder(int root) {
    if (root == -1) return;
    cout << "(";
    postOrder(Node[root].lc);
    if (isOperator(Node[root].v) && Node[root].lc == -1) {
        cout << Node[root].v;
        postOrder(Node[root].rc);
    } else {
        postOrder(Node[root].rc);
        cout << Node[root].v;
    }
    cout << ")";
}

全部代码如下:

#include <iostream>
#include <string>
using namespace std;
const int maxn = 25;
bool vis[maxn];
struct node {
    string v;
    int lc, rc;
} Node[maxn];
int n;

void postOrder(int root) {
    if (root == -1) return;
    cout << "(";
    postOrder(Node[root].lc);
    if (Node[root].v == "-" && Node[root].lc == -1) {
        cout << Node[root].v;
        postOrder(Node[root].rc);
    } else {
        postOrder(Node[root].rc);
        cout << Node[root].v;
    }
    cout << ")";
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> Node[i].v >> Node[i].lc >> Node[i].rc;
        if (Node[i].lc != -1) vis[Node[i].lc] = true;
        if (Node[i].rc != -1) vis[Node[i].rc] = true;
    }
    int R;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            R = i;
            break;
        }
    }
    postOrder(R);
    return 0;
}

这道题从读题到完成AC只用了十几分钟, 但是考试的时候我没提交… 25分随之飘走.

7-4 Dijkstra Sequence (30 分)

作者: 陈越, 单位: 浙江大学, 时间限制: 1500 ms, 内存限制: 64 MB

Dijkstra’s algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let’s call it Dijkstra sequence, is generated by Dijkstra’s algorithm.

On the other hand, for a given graph, there could be more than one Dijkstra sequence. For example, both { 5, 1, 3, 4, 2 } and { 5, 3, 1, 2, 4 } are Dijkstra sequences for the graph, where 5 is the source. Your job is to check whether a given sequence is Dijkstra sequence or not.

Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N_v (≤ 10³) and N_e (≤ 10⁵), which are the total numbers of vertices and edges, respectively. Hence the vertices are numbered from 1 to N_v .

Then N_e lines follow, each describes an edge by giving the indices of the vertices at the two ends, followed by a positive integer weight (≤ 100) of the edge. It is guaranteed that the given graph is connected.

Finally the number of queries, K, is given as a positive integer no larger than 100, followed by K lines of sequences, each contains a permutationof the N_v vertices. It is assumed that the first vertex is the source for each sequence.

All the inputs in a line are separated by a space.

Output Specification:
For each of the K sequences, print in a line Yes if it is a Dijkstra sequence, or No if not.

Sample Input:
5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4

Sample Output:
Yes
Yes
Yes
No

考试的时候跳过第三题, 看到第四题 named Dijkstra 的时候我非常开心, 因为我对单源最短路径的Dijkstra算法非常非常熟悉, 以往的考过的真题大多都是与最短路径相关的实际应用题, 比如以下几道:

上面这几道题, 做法都是比较单一的, 通常都是用 Dijkstra + DFS 来解题, 即通过Dijkstra算法得到一个最短路径树(形成了树结构, 用vector存储), 既然用树来存放路径, 必定可以用DFS获得每一条路径(从根节点到每个叶子节点即为一条最短路径), 最后得出最优解(通常就是路径的点权值或者边权值).
但是, 这个题它并不是个常规题…. 我去

大致题意:
1. 人话描述一下Dijkstra算法, Dijkstra是单源最短路径算法之一, 也就是求一个图中的某一个顶点到所有其他顶点的最短路径的算法. 一般要先给出一个 源点, 这个源点会最先被包含到集合中, 然后从这个点出发, 找到图中离它最近的邻接点(如果是无向图就是与之相邻的顶点, 如果是有向图就是该顶点所指向的顶点), 通常通过边权来判断距离大小, 也就是两顶点之间弧的权值, 然后把找到的最近邻接点加入到集合中, 并标记这个顶点已经被包含进集合, 然后再去寻找下一个离当前顶点最近的邻接点再加入集合, 在此过程中会声明一个 dist 数组用来记录从源点到各个顶点的最短距离并优化, 而在寻找最近邻接点的过程可能会存在多个邻接点与当前顶点距离最近, 这个时候就产生了多个获得最短路径的访问序列, 这个序列就被称之为 Dijkstra序列, 而为什么最后得到的最短路径是唯一的, 就是因为无论从哪个邻接点再次出发, 记录最短路径值的 dist 数组都会逐步做出优化. 所以Dijkstra实际上是个贪心算法, 从局部最优得到整体最优.
2. 题目要求: 最后给出 k 个序列, 需要通过程序判断这是不是一个Dijkstra序列. 并假设第一个顶点是这个序列的源点.

解题思路: (考试的时候没想到呀….), Dijkstra算法实现的第一个核心部分是 找到当前顶点的最近邻接点 , 这里比较适合先贴出全部代码:
Sample 1: Graph

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1010;
const int INF = 0x7FFFFFFF;
int G[maxn][maxn], d[maxn], number[maxn];
bool vis[maxn];
int n, m, k;

bool Dijkstra(int s) {
    fill(vis, vis + maxn, false);
    fill(d, d + maxn, INF);
    d[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, MIN = INF;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1 || d[u] != d[number[i]]) return false;
        u = number[i];
        vis[u] = true;
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                }
            }
        }
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    fill(G[0], G[0] + maxn * maxn, INF);
    int u, v, w;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        scanf("%d", &G[u][v]);
        G[v][u] = G[u][v];
    }
    scanf("%d", &k);
    while (k--) {
        for (int i = 1; i <= n; i++) {
            cin >> number[i];
        }
        if (Dijkstra(number[1])) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

上述的核心代码在 17-23 行, vis 数组用来标记某顶点是否被访问过, 实际上就是所述抽象出来的是否被存入集合中, MIN 被定义为一个无穷大的数INF(即infinite, 在C++中用可以用十六进制表示最大整型0x7FFFFFFF), 这代码要找出未被存入集合, 且离当前顶点最近的邻接点, 实际这个点就是题目中对应需要被判定的点. 考试的时候, 虽然可以 存在多个满足条件的邻接点,但是上述代码中因为 d[j] < MIN, 实际上只能取得第一个满足条件的邻接点, 当时我没想明白只取到一个邻接点该如何跟多个序列做对比, 这个问题把我给想傻掉了, 实际上可以记录所有的最短路径, 然后与给定的序列依次比较, 但是这种做法显然非常愚蠢. 根据题目给定的极端数据量和序列长度, 这个解法一定会有多个样例超时.

唉, 其实这个问题非常简单, 上述代码每次得到的邻接点是唯一的, 但是最短距离也是唯一, 判定最近邻接点的根本依据仍旧是边长, 所以通过给定的序列去做匹配, 如果当前顶点到序列中对应的顶点距离与之前得到的最短距离是相同的, 说明序列中的这个顶点也是最近的邻接点, 那么就可以把该点作为下一个出发源点, 如果出现距离不相等立马就可以判定这个序列是不合法的, 随即 return false. 最终今天AC通过的代码, 与考试时候提交的答案只差了两行关键代码.0分与30分只有两行代之差
以下是考试时的提交代码:

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1010;
const int INF = 0x7FFFFFFF;
int G[maxn][maxn], d[maxn], number[maxn];
bool vis[maxn] = {false};
int n, m, k;

void Dijkstra(int s) {
    fill(vis, vis + maxn, false);
    fill(d, d + maxn, INF);
    d[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, MIN = INF;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        // 解题代码应贴在此处..............
        if (u == -1) return;
        vis[u] = true;
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    fill(G[0], G[0] + maxn * maxn, INF);
    int u, v, w;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        scanf("%d", &G[u][v]);
        G[v][u] = G[u][v];
    }
    scanf("%d", &k);
    while (k--) {
        for (int i = 1; i <= n; i++) {
            cin >> number[i];
        }
    }
    return 0;
}

总结

看自己以如此欢快的口气写完了所有代码的总结, 实际上因为我已经难过了一阵子了, 哈哈. 这次的考试经历, 对自己算是个不小的打击, 总结几点经验:

考试前一天太过激动(不是紧张), 一晚上没睡着呀, 肾上腺素指数上升.
心理素质不行呀, 坐上考场, 脑子一片嗡嗡的, 思考问题完成没平时做题淡定.
终归问题是能力不行, 对”较大”场合适应能力不强, 得多经历一些类似的场合.
…. 下一回考前必须要有足够的睡眠以保证头脑清晰.

这次考试结束, 知乎上许多人都是最后三题只花一个小时, 这点真是非常遗憾, 是非常简单的题目, 但是我答的像屎一样, 尤其是第三道送分题, 我还回去了25分. 对于这次认为应该是最简单但却最坑的第一题, 死磕了一个多小时还是没AC, 太死板了, 心态也崩坏了, 阿斌说这题他看了几分钟立马跳到后面的题, 哈哈, 这都是经验呀.
最后, 为什么说是一次遗憾的考试, 没考出水平是一方面, 另一方面, 暑假大把时间地通刷真题, 本想是一次开心的检验性考试, 但是走出考场确实很失落, 以致于没等到拿PAT证书就走了, 这真是遗憾啊, 毕竟没有电子证书, 只有一人一章一份的浙大证书.
同时, 暑假这段刷题的经历, 不但了解了ACM相关竞赛的知识, 也终于让我体会到了编程的真正乐趣: 写程序不是简单的 if ... else ... 判断, 而且说把一个实际问题抽象建模, 寻找能表示问题的最佳模型(即数据结构), 再找到能够解决问题的方法(即算法), 从解决问题从最慢到最快(改进算法时间复杂度, 回溯法), 从理解局部最优到整体最优等, 这个学习过程真是很难, 但是确实很有乐趣. 考前一天我私信姥姥问她以后PAT出题是否会越来越难, 她说:”不会, 一如既往地简单.”, 同时引用姥姥近期在知乎上关于数据结构到底难在哪里? 的一个回答:

对其他重点高校的学生来说, 在OJ平台上做一道编程题可能就像我写一句 print "Hello World!" 这么简单, 就比如说, 这次的PAT甲级最快AC四道题的时间是1小时15分, 而PAT考试历史最快是45分钟AC四题, 我自己也深有感触, 从最开始刷 PAT甲级题目的寸步难行到现在大部分题的解题方法步骤几乎可以不经思考地默写(然后这次考地一塌糊涂), 长期的练习才能孰能生巧, 但是和上面这些大牛还是相差甚远啊. 看到其他学校OJ平台上的C/C++的课后习题就是PAT乙级的难度了, 别人在初学之时就接受了比我难的多的训练. 这点遗憾已经不能回到从前去补救了, 只能后起直追.

最后: 哈哈哈, 看到这条姥姥发的微博, 我赶紧搜了一下我们学校, 我笑了
2019 年 PAT 秋季考试 - 学校加权总成绩排名
顶级分数 x 1.5 + 甲级分数 + 乙级分数 / 1.5
我们学校就我一人参加甲级, 37分撑到了第314名, 后面还有一百多个学校, 哈哈, 他们真的是去划水的呀.

再接再厉…

PAT甲级2019秋季 - 初考总结篇

PAT甲级2019秋季 - 初考总结篇

7-1 Forever (20 分)

7-2 Merging Linked Lists (25 分)

7-3 Postfix Expression (25 分)

7-4 Dijkstra Sequence (30 分)

总结