PAT甲级 2022 夏题解

题目大意
给出两个人对于 “ 昨天、今天、明天 ” 的描述，其中，每个人仅提供一个正确信息。确定 “ 今天 ” 到底是星期几，并给出两人的正确信息是哪个维度。

这题我的方法很烂，虽然能过，但是有点费时

#include
#include
using namespace std;
int main() {
	int a[3], b[3];
	string ans[7] = { "Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday" };
	cin >> a[0] >> a[1] >> a[2] >> b[0] >> b[1] >> b[2];
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (a[i] - b[j] == i - j || a[i] - b[j] + 7 == i - j || a[i] - b[j] - 7 == i - j) {
				int flag = 0;
				for (int p = 0; p < 3; p++)
					if (p != i && (a[p] - a[i] == p - i || a[p] - a[i] + 7 == p - i || a[p] - a[i] - 7 == p - i)) flag = 1;
				for (int p = 0; p < 3; p++)
					if (p != j && (b[p] - b[j] == p - j || a[p] - a[j] + 7 == p - j || a[p] - a[j] - 7 == p - j)) flag = 1;
				if (!flag) {
					int ret = a[i];
					if (i == 2) ret = (ret + 6) % 7;
					else if (!i) ret = (ret + 1) % 7;
					printf("%sn", ans[ret].c_str());
					if (!i) printf("yesterdayn");
					else if (i == 1) printf("todayn");
					else printf("tomorrown");
					if (!j) printf("yesterdayn");
					else if (j == 1) printf("todayn");
					else printf("tomorrown");
					return 0;
				}
			}
}

题目大意
模拟操作系统中的LRU机制，即最近最少使用（Least Recently Used），选择最近最久未使用的页面予以替换。

出于个人习惯，我很喜欢使用stl。这题直接用map进行

#include
#include
#include
#include
#include
#include
#include
using namespace std;
vectorans;
mapmp, pm;//pm和mp记录的键值相反
int main() {
	int n, m;
	cin >> n >> m;
    //map自带排序功能
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		if (!mp[x]) {//x是新入队的
			mp[x] = i;
			pm[i] = x;
			if (mp.size() > n) {
				ans.push_back(pm.begin()->second);
				mp.erase(pm.begin()->second);
				pm.erase(pm.begin());
			}
		}
		else {//x原本已经在队列中
			pm.erase(mp[x]);
			pm[i] = x;
			mp[x] = i;
		}
	}
	printf("%d", ans[0]);
	for (int i = 1; i < ans.size(); i++) printf(" %d", ans[i]);
	return 0;
}

题目大意
给出一个有向图，询问某序列是否能够通过dfs该图得到。注意，每个节点仅被遍历一次，非连通图中可以有多个dfs起点。

这题我一开始以为不能够写dfs递归求解，害怕会爆栈www 结果是我想多了

不过我在做的时候还是写的循环。方法依赖于出度和stack以及dfs的过程。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n, m, k, e[1010][1010], t[1010], outd[1010], out[1010];
vectorfrom[1010];
int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int c1, c2;
		cin >> c1 >> c2;
		outd[c1]++;//记录出度
		from[c2].push_back(c1);//记录c2是从哪儿来的
		e[c1][c2] = 1;//单向图
	}
	for (int j = 0; j < k; j++) {
		for (int i = 1; i <= n; i++)
			out[i] = outd[i];//copy
		int flag = 1, x;
		cin >> x;//第一个点特殊处理 ps:好像多此一举了？
		mapmp;
		stacksta;
		if (out[x]) sta.push(x);//如果x的出度不为0 那么访问了x之后就还能往下访问
		mp[x] = 1;
		for (int j = 0; j < from[x].size(); j++)
			out[from[x][j]]--;//x已被访问 来路减少
		for (int i = 1; i < n; i++) {
			cin >> x;
			if (!flag) continue;//不是yes直接退出 但是这里还要继续输入x 不能立刻break
			mp[x] = 1;
			if (!sta.empty() && out[sta.top()] && !e[sta.top()][x]) {//判断是否可行
				flag = 0;
				continue;
			}
			for (int j = 0; j < from[x].size(); j++)
				out[from[x][j]]--;
			while (!sta.empty() && out[sta.top()] == 0) sta.pop();//出发点的出度为0了 
                                                                 //那就舍去			
            if (out[x]) sta.push(x);//x的出度>0 将会作为新的出发点
		}
		if (flag && mp.size() == n) printf("yesn");//合理且没有重复才是yes
		else printf("non");
	}
	return 0;
}

题目大意
有一棵完全d叉树，给出前序遍历，构造该树的层次遍历和父子关系。

这题相对比较简单？一开始理解错了degree的含义，后来猜到是完全d叉树之后，先预处理了一下每行会有多少个节点，然后就是直接建树求解了。

初始代码：

#include
#include
#include
#include
using namespace std;
int a[60], n, m, k, pre[110], root, need[10];
vectorlevel[10], ans;
void Pre(int x, int t) {
	for (int i = 0; i < min(m, need[t]); i++) {
		int p;
		cin >> p;
		level[t].push_back(p);
		pre[p] = x;//pre记录父节点
		Pre(p, t + 1);
		need[t + 1] -= m;//m叉树嘛..
	}
}
int main() {
	cin >> n >> m;
	n--;
	need[0] = 1;//记录每一层总共会有多少个节点
	for (int i = 1;n; i++) {
		if (need[i - 1] * m < n)
			need[i] = need[i - 1] * m;
		else need[i] = n;
		n -= need[i];
	}
	cin >> root;
	ans.push_back(root);
	Pre(root,1);//第一层开始 第0层已经输入了
	for (int i = 1; i < 10; i++)
		for (int j = 0; j < level[i].size(); j++)
			ans.push_back(level[i][j]);
	for (int i = 0; i < ans.size(); i++)
		if (i != ans.size() - 1) printf("%d ", ans[i]);
		else printf("%dn", ans[i]);
	cin >> k;
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		x = ans[x];
		while (x != root) {
			printf("%d ", x);
			x = pre[x];
		}
		printf("%dn", root);
	}
	return 0;
}

后来优化之后的代码：

#include
#include
using namespace std;
const int N = 110;
int pre[N], a[N], n, m, k, x;

void init(int p,int pos) {
	if (pos >= n) return;
	int t;
	cin >> t;
	pre[t] = p;
	a[pos] = t;
	for (int i = 1; i <= m; i++) init(t, pos * m + i);
}
int main() {
	cin >> n >> m;
	init(-1,0);//初始化 先序遍历顺带输入数据并配对好父节点以及处理层序遍历的结果
	for (int i = 0; i < n; i++)
		if (i != n - 1) printf("%d ", a[i]);//a数组里存的就是层序遍历的结果
		else printf("%dn", a[i]);
	cin >> k;
	while (k--) {
		cin >> x;
		x = a[x];
		while (x != a[0]) printf("%d ", x), x = pre[x];
		printf("%dn", x);
	}
	return 0;
}

总结：

感觉这次的难度有点小低? 比模拟题难度低

PAT甲级 2022 夏 题解

C/C++/C#相关栏目本月热门文章

PAT甲级 2022 夏题解