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 80Sample 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_