2019秋季PAT甲级考试总结：努力+策略+运气
鉴于这两天有很多网友联系我问这次考试的题解，所以我干脆就花点时间把C++题解整理出来了，见文末
经过一两个月的备战PAT，在今天终于画上了一个圆满的句号，取得了满分的成绩。
我是在南京的金陵科技学院考试的，三个月前就报好了名，256元报名费。考试时间是从下午13:30-16:30，共四个题目，分别是20分，25分，25分，30分。考试环境是线上考试，在PAT的桌面客户端提交代码，其实就是和https://pintia.cn网站的页面一样。编程环境Java是eclipse，C++是Dev和codeblocks。我选择使用codeblocks。打开codeblocks的第一件事就是开启C++11的编译选项，然后测试下C++11是否可以正常运行。之后就开始做题了。
看到第一题时，算是道数学题，我看了十分钟，发现没看懂，顿时心里是有点慌的，然后我就决定先去看后面的题吧。
第二题是个链表题，这种题我之前做过很多次，所以我一眼就觉得我能做出来，code十来分钟，把样例跑出来了，然后自己想了组例子，感觉代码没什么问题了，就提交了，一遍就AC了，呵呵，开森?。
紧接着看第三题，是个二叉树的后缀遍历，超简单啊，也是十来分钟就搞出来了，交了上去，又是一遍过?。 此时已经50分到手了，心情超级好，发现左右两边的男生还在做第一题，我的内心默默感慨自己的策略是对的，幸好没有死磕第一题。
我又开第四题了，是个Dijkstra算法的题，跟以往的有所不同，以前都是求最短路，这次是判断这个排列是否是一个dis数组。思考了一会，有思路，然后写了大半个小时，再调试调试，感觉写的没什么问题了，就交了，又是一遍就AC了，心情越来越好??
回过头来看第一题，此时离考试结束还剩一个半小时，时间绰绰有余，我看右边的男生第一题没做出来，在做第二题。我在草稿纸上推算第一题，算了一二十分钟，感觉有思路，可以下手写了，把样例跑出来了，交上去，就过了一组数据，还有三组数据没过，得了10分，此时总分已经有90分了呵呵。不过离考试结束还早得很，我觉得这道题还可以救一救，于是我又反复调试，但实在没发现什么问题。我看数据范围小，我就决定打印所有的数据范围看一看，说不定能一眼看出异样呢。果然，我看到当最后一位为9时，会增加一个9，这样结果就不对了，激动，感觉修改过来，让遍历的最后一位不能取9，再次提交，这次过了3组，得了17分。这时离考试结束就剩十分钟了，然而我没什么思路了，我不知道最后一组数据会错在哪儿了，我感觉代码很完美呀。我以为我这次就要定格在97分了，而且这个时候，PAT的服务器突然崩溃了，监考老师让我们先在本地调试，然后等服务器恢复了再提交，会给我们延时十五分钟，这个时候我就无聊的看了一下榜单排名（我居然到考试就剩十分钟才想起来去看榜单，也真是够蠢的了），我发现我的97分排116名，然在我前面的115个人都是100分，并列排第一名，也就是说，我只要这道题得了满分，我也就是100分跟他们并列第一名。我然后去看了下AC率，发现第一题果然是最难的，只有很少一部分人做出来。于是我就趁着服务器崩溃的时间继续看我的打印所有数据的结果，其实此时并不抱太大希望的，但当我看到一组数据中的n是由大到小输出时，我突然反应过来题目要求好像是要增序输出，为什么我的输出中会有降序，阔怕，我赶紧想看题目，可是服务器还没回复过来。于是我就先将降序改成了增序，然后等到服务器恢复了，我就赶紧再去看一遍题目，果然是增序输出n，其实这个坑很难找，因为绝大部分数据中，n只有一种，所以如果不打印所有的测试结果，根本发现不了n是降序的。当时我真是激动坏了，我感觉这里改过来应该就能AC了，可我提交时，发现时间已经截止了，不过监考老师说等着过会补时15分钟，这段时间真焦急，老师说可以交了，我就把这份最终代码交上去，发现前面还有1000多人等待评测，唉真是心累啊，等到还剩五百多等待评测的时候，突然网页又显示服务器异常了，然后提交页面就没有了。。。┭┮﹏┭┮我就问监考老师我提交到一半突然服务器异常了，我有没有交上去呢，要不要重新提交，然后老师说那你重新交一下吧，于是我就点进提交列表准备重新提交，发现我刚才居然已经提交上去了，并且显示得分20分，????，终于AC了，当时的心情真是开心到飞起。然后我就准备起身离开了，并且看了一下名次，是第一名，满分，监考老师在后面说了句满分啊，不容易。哈哈我笑了笑没说什么，不过内心已是特别激动。
本次考试的结果我很是满意。
本次考试结果归功于，努力+策略+运气
努力：
在考试前一个月里，我每天都在PAT网站上刷真题，每天都是刷2~6个小时，我不是很闲的哟，我现在已经在工作了，刷题的时间都是挤出来的。而且刷题也不是盲目，遇到不会的题会去找题解，会去总结，可以看我最近的博客，全都是PAT的题解。当然我只是觉得对我有价值的题解才会写到博客里，普通题解只上传到GitHub了。PAT甲级题库里共有155题，我做了一百多道题。在考前我还在复习这些我曾写过的题。我觉得难得题有：动态规划（背包部分），树状数组，平衡二叉树，我害怕考到这些。
策略：
一般情况下，20分的题都比较简单，但这次考试显然不是这样，我庆幸我没有死磕第一题，要不然这次就凉了。我是先做后面三道题的，非常顺利的做出了后三道题，然后再做第一道题，心态更好了，思路也更清晰了。
运气：
刚才说的我害怕的三种题，这次都没考到，如果考到了这三者我可能就不会这么顺利了。其次，多亏了最后服务器崩溃的补时十五分钟，要不然我没时间调试出我最后的bug拿到满分，所以补时对我来说影响是巨大的。虽然监考老师说往年也都是这样，但对我来说还算是运气好吧。
继续加油，再接再厉。当下定决心做一件事时，就要全力以赴！
感谢我的idol一博哥哥给我力量
2019秋季PAT甲级考试题解
由于我是重新写的，不记得题目的样例了，下面的代码仅代表我的思路，也许跟我在考场提交的源代码不完全一致。等到PAT网站上录入了这次的赛题，我再测试提交下，否则不敢保证下面的代码一定能AC，我只是凭记忆来复现当时提交的代码。
A题
A的长度为k，A的位和为m，A+1的位和为n，gcd(m,n)是大于2的素数。
给定k，m，求符合条件的n, A，增序输出。
可以看出n = m - 9 * i + 1，i 可以取[2, k]。然后就进行恶心的枚举即可。
#include<bits/stdc++.h>
using namespace std;
int k, m, n, len, sum, f = 0;
vector<int>out;
void dfs(int step){
if(step >= len){
if(sum == n){
f = 1;
cout << n << " ";
for(auto i: out){
cout << i;
}
for(int i = 1; i <= k-len; i++){
cout << 9;
}
cout << endl;
}
return;
}
for(int i = 0; i <= 9; i++){
if(step == 0 and i == 0)continue;// 最高位不能为0
if(step == len-1 and i == 9)continue;// 关键。第len-1位不能为9，否则A末尾则超过了k-len个9
out[step] = i;
sum += i;
dfs(step+1);
sum -= i;
}
}
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
bool prime(int n){
if(n <= 2)return false;// 此处把2也直接返回false。
for(int i = 2; i * i <= n; i++){
if(n % i == 0)return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
int T;
cin >> T;
for(int t = 1; t <= T; t++){
cin >> k >> m;
f = 0;
cout << "Case " << t << endl;
for(int i = k; i >= 2; i--){
n = m - 9 * i + 1;
if(prime(gcd(m, n))){// m,n的最大公约数为超过2的素数
len = k - i;
out.clear();
out.resize(len);
sum = 0;
dfs(0);
}
}
if(f == 0){
cout << "No solution" << endl;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
B题（25分）
给出两个链表，长链表的长度是短链表的至少两倍。将短链表翻转，然后每隔两个长链表元素后接一个短链表元素。
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int addr, val, next;
};
int main(){
int addr1, addr2, n;
scanf("%d %d %d", &addr1, &addr2, &n);// 怕T，用scanf
map<int, Node>M;
for(int i = 0; i < n; i++){
int addr, val, next;
scanf("%d %d %d", &addr, &val, &next);
M[addr] = {addr, val, next};
}
vector<Node>v1, v2, v3;// v1 v2表示两个链表，v3表示最后合并的结果链表
int p = addr1;
while(p != -1){
v1.push_back(M[p]);
p = M[p].next;
}
p = addr2;
while(p != -1){
v2.push_back(M[p]);
p = M[p].next;
}
// 使用用v1表示更长的那个链表，v2表示短的链表
if(v1.size() < 2*v2.size()){
swap(v1, v2);
}
reverse(v2.begin(), v2.end());// 翻转短链表
for(int i = 0; i < v2.size(); i++){
// 直接模拟插入到一个新链表即可。这样操作最简单不容易错
v3.push_back(v1[2*i]);
v3.push_back(v1[2*i+1]);
v3.push_back(v2[i]);
}
for(int i = 2*v2.size(); i < v1.size(); i++){
v3.push_back(v1[i]);
}
cout << v3.size() << endl;// 这里要输出长度吗，我也不记得了。。
for(int i = 0; i < v3.size()-1; i++){
printf("%05d %d %05d\n", v3[i].addr, v3[i].val, v3[i].next);
}
printf("%05d %d -1\n", v3.back().addr, v3.back().val);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
C题（25分）
赤裸裸的二叉树后序遍历问题
#include<bits/stdc++.h>
using namespace std;
struct Node
{
string op;
int left, right;
};
map<int, Node>M;
string dfs(int root){
if(M[root].left == -1 and M[root].right == -1){// 叶节点直接返回(a)这种形式
return "(" + M[root].op + ")";
}
if(M[root].left == -1){// 没有左子树，只有右子树，则M[root].op是一个+-符号，这是一个一元运算符。返回(-a)这种形式
return "(" + M[root].op + dfs(M[root].right) + ")";
}
return "(" + dfs(M[root].left) + dfs(M[root].right) + M[root].op + ")";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int>book(n+1);
for(int i = 1; i <= n; i++){
string op;
int left, right;
cin >> op >> left >> right;
M[i] = {op, left, right};
if(left != -1)book[left] = 1;
if(right != -1)book[right] = 1;
}
int root = -1;
for(int i = 1; i <= n; i++){
if(book[i]==0){// 题目中有说明parenless的节点为根节点
root = i;
break;
}
}
cout << dfs(root) << endl;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
D题（30分）
判断给定的数组是否是Dijkstra算法贪心过程的选取顺序。
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>>G(n+1);
for(int i = 1; i <= n; i++){
G[i].resize(n+1);
for(int j = 1; j <= n; j++){
if(i==j){
G[i][j] = 0;
}else{
G[i][j] = INT_MAX/2;
}
}
}
for(int i = 1; i <= m; i++){
int x, y, z;
cin >> x >> y >> z;
G[x][y] = min(G[x][y], z);
}
int q;
cin >> q;
while(q--){
bool f = true;
vector<int>v(n+1);
for(int i = 1; i<= n; i++){
cin >> v[i];
}
int source = v[1];
vector<int>dis(n+1), book(n+1);
for(int i = 1; i <= n; i++){
dis[i] = G[source][i];
}
book[source] = 1;
for(int i = 2; i < v.size(); i++){
int p = -1, MIN = INT_MAX;
for(int j = 1; j <= n; j++){
if(book[j]==0 and dis[j] < MIN){
MIN = dis[j];
p = j;
}
}
if(dis[v[i]] != MIN){// 核心部分
f = false;
cout << "No" << endl;
break;
}
p = v[i];
book[p] = 1;
for(int j = 1; j <= n; j++){
if(book[j] == 0 and dis[j] > dis[p] + G[p][j] ){
dis[j] = dis[p] + G[p][j];
}
}
}
if(f){
cout << "Yes" << endl;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/jal517486222/article/details/100637676
- 点赞
- 收藏
- 关注作者
评论（0）