[数据结构与算法][PAT]PAT甲级2021秋季——经验和总结、“尽人事，听天命！”

说在前面

• 其实博主最初想要考PAT的初衷就是为了抵浙大的机试，但是今年很不幸的是，PAT不能抵浙大的机试啦！（而且还是在不能退钱的后一天发的政策hhh）但是这仍然是一次模拟浙大机试的过程吧，而且能系统的学习一些机试相关的内容，虽然还上升不到能够去打比赛的程度，但是自己也在过程中收获了许多快乐，感觉写算法题学数据结构还是很快乐的！这或许是我仍在坚持cs的理由吧！
• 不知道是不是这次考试比较简单的缘故，我居然考了71分！我在考试前一天写往年模拟题的时候得了2分，然后还没有复习到树和图相关的内容，所以最终考了这个分数我真的是很惊喜的！虽然网上有很多大佬刷20题就能考满分，很遗憾我不是这样的大佬，但是就是想和大家说一下：一定要坚持，不要放弃，结果会让你很惊喜的！
• 以及这个考试能够抵一些企业的笔试~其实真情实感，我觉得笔试是企业面试最水的一个环节，总的来说我觉得算法小白拿这个PAT来系统的学一下机试，还是可以的，别的就没有什么体会啦。

准备过程

• 王道机试2021
• 晴神宝典
• PAT甲级题目索引(题目+解析+AC代码)
• PAT考试经验总结（甲乙级均适用）想满分的请看这里！
• PAT考试历年真题（可以买，也可直接上网搜，但网上搜可能只有代码，而且不能模拟考试现场）

我准备的程度大概就是王道刚写到第八章（大家看我的博客就知道。。），所以第九章搜索、第十章数据结构（树、优先队列、散列）、第十一章图论，我是没看的。解题的时候都是用数组来模拟树和图的数据结构，方法也很暴力。还有王道第十二章是动态规划，这一部分求职面试经常问。
写了一套真题（认真写、并总结分析了）
然后就直接考试了。
我觉甲级里面的题还是很套路的吧，你写题写多了，思路自然就会有了，当然有的人写的算法更有效率一些，这才是区别吧，我觉得大家认真复习认真写都是没什么问题的！！

如果你的目标是高分，直接刷历年真题并总结，基础不行就先看晴神宝典（PAT考试经验总结里博主总结的，有的章节不考，codeup上的题也不用刷），就这么简单！！！！

考研保研er准备机试也差不多是这个道理！！~（清北机试除外，没写过，别的学校的差不多，都没多难的题，毕竟不是acm，但是有的学校很奇葩考的特别，不是这种常规机试题，就不说了）

A题

• 简单模拟题，题目说啥你做啥就行

我看有很多人卡在A题，没拿满分，但是我拿满分了！！
我刚开始也只拿了11分，后来思考了一下，我是卡在了输出一共declare了多少个数组。刚开始我的计数方式是检索了哪个数组就+1，但是不是这样的！因为它的是$A_0$溢出了declare$A_1$，以此类推，所以要记录最大declare的数组数。

我写循环的方式很奇葩，大家可以忽略

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>

using namespace std;

int n, k;

struct block {
	long long start_add;
    int len;
	int used = false;
};

block blocks[10001];

long long GetAdd(int index) {
	int i_th = 0;
	index -= blocks[i_th].len;
	while (index >= 0) {
		i_th++;
		index -= blocks[i_th].len;
	}
	
	index += blocks[i_th].len;
	blocks[i_th].used = true;

	return blocks[i_th].start_add + index * (sizeof(int));
}

int main() {
	
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; ++i) {
		scanf("%lld %d", &blocks[i].start_add, &blocks[i].len);
	}

	int total_len = 0;
	for (int i = 0; i < n; ++i) {
		total_len += blocks[i].len;
	}

	for (int i = 0; i < k; ++i) {
		int index = 0;
		scanf("%d", &index);
		if (index > total_len - 1) {
			printf("Illegal Access\n");
		}
		else {
			printf("%lld\n", GetAdd(index));
		}
	}

	int index = 0;
	for (int i = n - 1; i >= 0; --i) {
		if (blocks[i].used) {
			index = i;
			break;
		}
	}

	printf("%d", index + 1);
	return 0;
}

B题

• 简单模拟题，题目说啥你做啥就行

从输入帽子列表的最后一个帽子开始分配帽子，找到对应体重的owner就可以了，还是很简单的，一下子就过了。

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <algorithm>

using namespace std;
int n;
int hats[10001];


struct owner {
	int weight;
	int index;
};

owner owners[10001];

bool Compare(owner a, owner b) {
	return a.weight < b.weight;
}

int Getorder(int i) {
	int count = 0;
	for (int j = 0; j < n; ++j) {
		if (hats[j] < hats[i]) {
			count++;
		}
	}
	return count;
}

int main() {

	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &hats[i]);
	}

	for (int i = 0; i < n; ++i) {
		scanf("%d", &owners[i].weight);
		owners[i].index = i + 1;
	}

	sort(owners, owners + n, Compare);

	for (int i = n - 1; i >= 0; --i) {
		printf("%d", owners[Getorder(i)].index);
		if (i != 0) {
			printf(" ");
		}
	}

	return 0;
}

C题

• 图

遍历图，不重复遍历，每次选择index小的结点，不知道有没有什么算法可以实现，但我属于不知道算法，只能暴力遍历hhh

写完代码测试发现WA，debug发现卡在了起始点为8时的遍历，我原本写的i == n && playground[current][i] == 0跳出条件当start=9，current=5的时候会卡在死循环里永远跳不出去哈哈哈啊哈然后稍微改了一下，但是我觉得又合理又不合理的ovo

我变量取名是不是很可爱哈哈哈哈！

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>

using namespace std;

int n, m;
int playground[110][110];
bool visit[110] = { 0 };

int SearchPlayground(int start) {
	bool visit[110] = { 0 };
	visit[start] = true;
	int current = start;
	int count = 1;
	while (count != n) {
		for (int i = 1; i <= n; ++i) {
			if ((playground[current][i] == 1)&&(!visit[i])) {
				current = i;
				count++;
				visit[i] = true;
				break;
			}
			if (i == n && playground[current][i + 1] == 0) { // 这个判断条件有待商榷 and 优化
				return count;
			}
		}
	}
	return count;
}

int FindStart() {
	int start = 1;
	for (int i = 1; i <= n; ++i) {
		if (SearchPlayground(i) > SearchPlayground(start)) {
			start = i;
		}
	}
	return start;
}


int main() {

	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; ++i) {
		int start, end;
		scanf("%d %d", &start, &end);
		playground[start][end] = 1;
		playground[end][start] = 1;
	}



	int begin = FindStart();


	printf("%d %d", begin, SearchPlayground(begin));
	return 0;
}

D题

• 树的建立、小顶堆

在头一天总结了一套试卷，有大顶堆，然后这道题大概的思路就有了。
but，前序建树我不会啊55555肠子都悔青了，要是头一天晚上没有被那套考了2分的模拟卷（写了一会写不出来直接交卷了）打击了自信心，已经抱着做慈善的心态去面对转天的考试了！

没建树，而且按照大顶堆的方式建立的小顶堆。后期看到题目我会重写一遍所以不要参考！

#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <algorithm>

using namespace std;

struct node {
	int key;
	int priority;
};

node nodes[31];

void up(int index) {
	for (int i = index; nodes[i / 2].priority > nodes[i].priority && i > 1; i /= 2){
		swap(nodes[i], nodes[i / 2]);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d %d", &nodes[i].key, &nodes[i].priority);
	}

	for (int i = n; i >= 1; i--) {
		up(i);
	}

	for (int i = 1; i <= n; ++i) {
		printf("%d", nodes[i].key);
		if (i != n) {
			printf(" ");
		}
	}


	printf("\n");


	for (int i = 1; i <= n; ++i) {
		printf("%d", nodes[i].priority);
		if (i != n) {
			printf(" ");
		}
	}

	return 0;
}

最后的一点点感想

so，不要着急，要有耐心，不要急于求成，模拟不考100分就不行，我觉得人生大多数事情，都是努力了就会有好结果的，这是我坚信不疑的。
虽然现在大家都想躺平，觉得努力了也不如天龙人身份（北京户口），甚至努力工作都是在被资本家压榨，打工就是被压榨，所以躺平就是最好的选择。（行业需要整改，但绝对不是以所有人都躺平的方式来抗击的，这价值观就很危险）hhh，所以一定要记住一件事
“收获只会出现在你努力的方向上”
努力学习复习功课考试，你会收获好的分数高绩点，保研资格，但你不一定能收获好的工作，保去最好的学校。
努力准备算法题、面经、积累项目经历，你会收获好的工作offer，但不一定就是谷歌微软BAT。
拿到offer努力工作，你会收获高薪，但不一定能赚够北京一套房，还钱多事少离家近。

你这么努力奋斗，你在过程中认识自我、实现自我，找到热爱的事情、最想过的生活、最想成为的自己，活得独立、体面、有尊严，这还不够有意义吗？如果非要和那些不努力但是出生就决定他/她的起点注定是你的终点的人比，然后觉得努力没用，就丧了，躺平了。
难道就没有考虑过，这完全就是两条赛道吗，完全不相关呀。收获只会出现在努力的方向上！所以xdm冲呀！