2019 秋季 PAT (Advanced Level) C++題解

考試拿到了滿分但受考場狀態和知識水平所限可能方法不夠簡潔，此處保留記錄，仍需多加學習。備考總結（筆記目錄）在這里

7-1 Forever (20 分)

"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

題目思路

• 要找到符合要求的數，給出的條件是 數的位數 K 和 各位的和 m
• 首先要找到滿足各位和為 m 的 K 位數，再檢查找到的數是否符合要求
• 用 DFS 找滿足各位和為 m 的 K 位數
  • 參數：這個函數內要填寫第幾位，要填寫什么數字，填好后目前所有位的和
  • 由主函數從 1-9 選填第 1 位
  • 進入 DFS 遞歸過程后，每次填好自己這一位，從 0-9 選填下一位
  • 遞歸終止條件：填完 K 位后各位之和剛好等于 m，調用函數檢查是否符合要求
  • 剪枝
    • 一開始只注意到若要填的位數超過所要求的位數，或目前各位之和已經超過要求的 m 應當停止遞歸，但這樣會運行超時
    • 注意當前幾位確定下來時，有很多后面幾位比較小的數已經不可能滿足各位之和為 m 的條件了，所以每次檢查，若 目前各位 + 剩余每位均填 9 都不能達到 m，此枝應當被剪掉
• 檢查找到的數是否符合要求
  • 記憶判斷素數和最小公約數函數
  • 每次取到 A 和 A+1，計算好各位之和并求出 gcd，判斷是否為素數且 > 2
  • 檢查函數返回值為 int，若符合要求返回 A+1 的各位和，若不符合返回 -1 便于調用方進行判斷

AC代碼

#include<iostream> #include<vector> #include<algorithm> using namespace std; int k, m; char s[10]; bool issolved; struct Data{int sumN;string data; }; vector<Data> result; bool cmp(Data a, Data b){ return a.sumN != b.sumN ? a.sumN < b.sumN : a.data < b.data; } bool isPrime(int n){if (n <= 1) return false;for (int i = 2; i * i <= n; i++)if (n % i == 0) return false;return true; } int gcd(int a, int b){ return !b ? a : gcd(b,a%b); } int checkF(){int A = stoi(s), B = A+1, sumA = 0, sumB = 0;string Bs = to_string(B);for (int i = 0; i < k; i++) sumA += s[i]-'0';for (int i = 0; i < k; i++) sumB += Bs[i]-'0';int d = gcd(sumA,sumB);if (d > 2 && isPrime(d)) return sumB;else return -1; } void DFS(int index, int digit, int sumD){if (index > k - 1 || sumD > m) return;if (sumD + 9 * (k - index - 1) < m) return;s[index] = digit + '0';if (sumD == m && index == k - 1){if (checkF() >= 0){issolved = true;string data = s;result.push_back({checkF(),data});}return;}for (int i = 0; i < 10; i++) DFS(index+1, i, sumD+i); }int main() {int n;scanf("%d", &n);for (int i = 1; i < n + 1; i++){scanf("%d%d", &k, &m);printf("Case %d\n", i);issolved = false;result.clear();for (int j = 1; j < 10; j++) DFS(0,j,j);if (issolved){sort(result.begin(), result.end(), cmp);for (int j = 0; j < result.size(); j++)cout << result[j].sumN << " " << result[j].data << endl;}else printf("No Solution\n");}return 0; }

7-2 Merging Linked Lists (25 分)

Given two singly linked lists \(L_1 = a_1 \to a_2 \to ... \to a_{n-1} \to a_n\) and \(L_2 = b_1 \to b_2 \to ... \to b_{m-1} \to b_m\). If \(n≥2m\), you are supposed to reverse and merge the shorter one into the longer one to obtain a list like \(a_1 \to a_2 \to b_m \to a_3 \to a_4 \to 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_1\) and \(L_2\) , plus a positive \(N (\le 10^5)\) 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^5\), 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 02233 2 34891 00100 6 00001 34891 3 10086 01000 1 02233 00033 5 -1 10086 4 00033 00001 7 -1

Sample Output

01000 1 02233 02233 2 00001 00001 7 34891 34891 3 10086 10086 4 00100 00100 6 00033 00033 5 -1

題目思路

• 靜態鏈表題
• 接收輸入鏈表后，分別遍歷兩條鏈，將結點按鏈表中的順序存儲在容器中
• 按壓入兩個長鏈表的結點就壓入一個短鏈表的結點的順序將結點壓入 result 容器
• 按要求輸出 result 容器中的結點
• 注意：讀題時想當然的以為要將短鏈表的結點均勻的并入長鏈表，其實就是題目里的兩長一短即可Orz

AC代碼

#include<iostream> #include<vector> using namespace std; struct Node{int address, data, next; } node[100001]; int main() {int head1, head2, n, address, data, next;scanf("%d%d%d", &head1, &head2, &n);for (int i = 0; i < n; i++){scanf("%d%d%d", &address, &data, &next);node[address] = {address, data, next};}vector<Node> list1, list2, result;for (int p = head1; p != -1; p = node[p].next)list1.push_back(node[p]);for (int p = head2; p != -1; p = node[p].next)list2.push_back(node[p]);if (list1.size() > list2.size()){int j = list2.size() - 1;for (int i = 0; i < list1.size(); i = i + 2){result.push_back(list1[i]);if (i + 1 < list1.size()) result.push_back(list1[i+1]);if (j >= 0) result.push_back(list2[j--]);}}else{int j = list1.size() - 1;for (int i = 0; i < list2.size(); i = i + 2){result.push_back(list2[i]);if (i + 1 < list2.size()) result.push_back(list2[i+1]);if (j >= 0) result.push_back(list1[j--]);}}for (int i = 0; i + 1 < result.size(); i++)printf("%05d %d %05d\n", result[i].address, result[i].data, result[i+1].address);printf("%05d %d -1\n", result[result.size()-1].address, result[result.size()-1].data);return 0; }

7-3 Postfix Expression (25 分)

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)%))+)

題目思路

• 題庫 1130 Infix Expression (25 分)
• 輸入每個結點的左右孩子來建樹，用 bool 數組記錄結點是否在其他結點的孩子結點中出現過，都沒有出現過的即為根結點
• 在后序遍歷基礎上要添加括號來表示優先級
• 一般是每進入一個子樹，就用括號將這個子樹括起來，然后遞歸進入左子樹和右子樹，遞歸返回后輸出根節點內容
• 注意：表達式中會出現 正負號，此時不能在子結點返回后才輸出正負號——特判：當結點左子樹為空而右子樹不為空時，先輸出根節點內容，再進入右子樹

AC代碼

#include<iostream> using namespace std; struct Node{string data;int lchild, rchild; } node[21]; bool occured[21] = {false}; void postorder(int root){cout << "(";if (node[root].lchild == -1 && node[root].rchild != -1){cout << node[root].data;postorder(node[root].rchild);cout << ")";}else{if (node[root].lchild != -1) postorder(node[root].lchild);if (node[root].rchild != -1) postorder(node[root].rchild);cout << node[root].data << ")";} } int main() {int n, root;string data;scanf("%d", &n);for (int i = 1; i < n + 1; i++){cin >> node[i].data >> node[i].lchild >> node[i].rchild;if (node[i].lchild != -1) occured[node[i].lchild] = true;if (node[i].rchild != -1) occured[node[i].rchild] = true;}for (root = 1; root < n + 1 && occured[root]; root++);postorder(root);return 0; }

7-4 Dijkstra Sequence (30 分)

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(\le 10^3)\) and \(N_e(\le 10^5)\), 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

題目思路

• 注意審題 Orz：檢查序列是否為 Dijkstra 過程中 每次找到 距離原點最近 用于更新相鄰點 的 中介點 的 序列
• Dijkstra 每次找目前距原點最近的點，若有幾個距離相同的會取其中一個，但其實先檢查另外幾個點也可
• 整體模板還是用 Dijkstra，每次循環檢查 query 的一位
  • 查 當前距離原點最近 的 未訪問點 與原點的距離
  • 看 與當前位的 query 中的點 到原點的距離是否符合
  • 若符合，則以 query 當前點為中介 更新鄰接點距原點的距離
  • 若不符合，說明此時不應當以 query 當前點為中介繼續 Dijkstra，即此 query 非所要求的 Dijkstra sequence，返回 false

AC代碼

#include<iostream> using namespace std; const int INF = 0x3fffffff; int n, G[1001][1001], d[1001], query[1001]; bool Dijkstra(int root){fill(d, d+1001, INF);bool vis[1001] = {false};d[root] = 0;for (int i = 0; i < n; i++){int u, min = INF;for (int j = 1; j < n + 1; j++)if (d[j] < min && !vis[j])min = d[j];if (d[query[i]] == min) u = query[i];else return false;vis[u] = true;for (int j = 1; j < n + 1; j++)if (G[u][j] && !vis[j] && d[j] > d[u] + G[u][j])d[j] = d[u] + G[u][j];}return true; } int main() {int m, u, v, distance, k;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++){scanf("%d%d%d", &u, &v, &distance);G[u][v] = G[v][u] = distance;}scanf("%d",&k);for (int i = 0; i < k; i++){for (int j = 0; j < n; j++) scanf("%d", &query[j]);bool isD = Dijkstra(query[0]);printf("%s\n", isD ? "Yes" : "No");}return 0; }

轉載于:https://www.cnblogs.com/whale90830/p/11494161.html

總結

以上是生活随笔為你收集整理的2019秋季PAT甲级_C++题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。