PAT练习题，共（13/167）题(持续更新中)

声明：此博客中提及到的所有题目均出自PTA平台的提供的PAT甲级练习题，不存在任何盗版行为

A+B Format

本题就是将计算结果按照英文的输出习惯(三位一逗号)进行输出，思路很简单就是直接将计算结果转成字符串，扭转，3位加一个逗号即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int a, b;
string res;
int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> a >> b;
	res = to_string(a + b);
	reverse(res.begin(), res.end());
	int t = 3;
	while (res.size() > t)
	{
		if ('0' <= res[t] && res[t] <= '9')
			res.insert(res.begin() + t, ',');
		t += 4;
	}
	reverse(res.begin(), res.end());
	cout << res;
	return 0;
}

A+B for Polynomials

用人话讲就是多项式加法

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
#include <bits/stdc++.h>
using namespace std;


const int N = 1e3+10;
double res[N];

int k,p,cnt,l = 2;
double a;

int main()
{
// 	freopen("1.txt","r",stdin);
	while(l--){
		cin>>k;
		while(k--){
			cin>>p>>a;
			res[p]+=a;
		}
	}
	for(int i = N-1;i>=0;i--)
		if(res[i] != 0.0)cnt++;
	cout<<cnt;
	for(int i = N-1;i>=0;i--)
		if(res[i]!=0.0)
			printf(" %d %.1lf",i,res[i]);
	return 0;
}

Emergency

就是带条件的dijkstra，看懂题目比什么都重要

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int n, m, c1, c2;
// 邻接表的节点和权重
vector<int> e[N], w[N];
// 从c1到i的最短距离
// 从c1到i的最大人数
// c1-c2每个节点的人数
// 从c1到i的最短路径数量
int dist[N], p[N], cites[N], cnt[N];
// 记录是否用过这个点
bool st[N];

// 添加a-b的一条边
int add(int a, int b, int c)
{
	e[a].push_back(b);
	w[a].push_back(c);
}


// 堆优化的dijkstra
void di(int start, int eee)
{
	// 初始化距离
	memset(dist, 0x3f, sizeof dist);
	// 建小根堆
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	// 距离是第一个值，点的序号是第二个值
	heap.push({0, start});
	// 初始化距离，人数，最短路数
	dist[start] = 0;
	p[start] = cites[start];
	cnt[start] = 1;
	while (heap.size())
	{
		// 取出堆顶
		PII t = heap.top();
		heap.pop();
		// 获取点的序号，用过就跳过
		int ver = t.second;
		if (st[ver])
			continue;
		st[ver] = true;
		// 遍历这个点所有可以到的边
		for (int i = 0; i < e[ver].size(); i++)
		{
			// 获取这个点
			int j = e[ver][i];
			// 如果到j的最短距离比先到ver再到j大，就替换
			if (dist[j] > dist[ver] + w[ver][i])
			{
				dist[j] = dist[ver] + w[ver][i];
				// 更新最大召集人数
				p[j] = p[ver] + cites[j];
				// 第一次遇到最短路
				cnt[j] = cnt[ver];
				// 距离和序号放入堆中
				heap.push({dist[j], j});
			}
			// 如果两个相等
			else if (dist[j] == dist[ver] + w[ver][i])
			{
				// 又能从另一个点实现最短路
				cnt[j] += cnt[ver];
				// 如果从这边走人数更多的话就直接加上
				if (p[j] < p[ver] + cites[j])
					p[j] = p[ver] + cites[j];
			}
		}
	}
	cout << cnt[eee] << " " << p[eee];
}

int main()
{
	// freopen("1.txt","r",stdin);
	// 输入输出没啥好说的，认真看题目好吗
	cin >> n >> m >> c1 >> c2;
	for (int i = 0; i < n; i++)
		cin >> cites[i];
	while (m--)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	di(c1, c2);
	return 0;
}

同类题：L3-1 直捣黄龙 (30 分)

放个题目，避免链接挂掉

image-20220418161236804

输入格式：

10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10

输出样例：

PAT->PTA->PDS->DBY
3 30 210

答案：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>

using namespace std;
const int N = 210;
typedef pair<int, int> PII;
// 节点数和边数
int n, m;
// 起点，重点，以及将点的数字映射回名称的数组
string s1, s2, point[N];
// 将名称映射回数字
unordered_map<string, int> mp;
// 从起点到这个点的最短距离
// 每个点的人数
// 当前点的上一个节点是哪一个
// 从起点到这个点杀人数
// 从起点到这个点有多少条路径
// 从起点到这个点一共有多少个点
int dist[N], city[N], pre[N], killer[N], cnt[N], counts[N];
// 当前点是否已经被使用了
bool st[N];
// 连接表的节点和权重
vector<int> e[N], w[N];

// 连接表添加节点
void add(int a, int b, int c)
{
	e[a].push_back(b);
	w[a].push_back(c);
}

void di(int a, int b)
{	
	// 初始化最短距离
	memset(dist, 0x3f, sizeof dist);
	// 经典对优化dijkstra
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	// 当前点的最短距离是0
	dist[a] = 0;
	// 到当前点有一条路径
	cnt[a] = 1;
	// 按照{距离，节点编号}放入堆中
	heap.push({0, a});
	// 遍历堆
	while (heap.size())
	{
		// 取出堆顶
		PII x = heap.top();
		heap.pop();
		// 获取节点
		int ver = x.second;
		// 用过了就跳过
		if (st[ver])
			continue;
		// 设置为用过了
		st[ver] = true;
		// 从这个点出发去看其他点
		for (int i = 0; i < e[ver].size(); i++)
		{
			// 下一个点
			int j = e[ver][i];
			// 如果到这个点的距离更短了
			if (dist[j] > dist[ver] + w[ver][i])
			{
				// 记录到这个点的路线数
				cnt[j] = cnt[ver];
				// 记录最短距离
				dist[j] = dist[ver] + w[ver][i];
				// 记录是从ver到j的
				pre[j] = ver;
				// 记录当前杀敌人数
				killer[j] = killer[ver] + city[j];
				// 记录到这个点一共经过了多少个点
				counts[j] = counts[ver] + 1;
				// 重新入堆
				heap.push({dist[j], j});
			}
			// 如果距离相等
			else if (dist[j] == dist[ver] + w[ver][i])
			{
				// 又有一种新方式过来
				cnt[j] += cnt[ver];
				// 如果沿途城市比新方式小的话
				if (counts[j] < counts[ver] + 1)
				{	
					// 更新沿途城市的数量
					counts[j] = counts[ver] + 1;
					// 更新路线
					pre[j] = ver;
					// 更新杀敌数
					killer[j] = killer[ver] + city[j];
				}
				// 如果相等
				else if (counts[j] == counts[ver] + 1)
				{
					// 并且杀敌数比新路线少
					if(killer[j] < killer[ver] + city[j])
					{
						// 更新路线
						pre[j] = ver;
						// 更新杀敌数
						killer[j] = killer[ver] + city[j];
					}
					
				}
			}
		}
	}
	// 获取最佳的最短路径
	stack<int> stt;
	stt.push(b);
	while (pre[stt.top()])
		stt.push(pre[stt.top()]);
	// 输出最短路径
	int t = stt.size();
	for (int i = 0; i < t; i++)
	{
		if (i)
			cout << "->";
		cout << point[stt.top()];
		stt.pop();
	}
	puts("");
	// 输出到B点的路线数，最短距离，和杀人数
	printf("%d %d %d", cnt[b], dist[b], killer[b]);
}

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n >> m >> s1 >> s2;
	// 因为起点不会做输入，索引要自己进行坐标和名字映射
	mp[s1] = 1;
	point[1] = s1;
	// 获取节点的人数，并进行坐标名字映射
	for (int i = 2; i <= n; i++)
	{
		string s;
		int x;
		cin >> s >> x;
		mp[s] = i;
		city[i] = x;
		point[i] = s;
	}
	// 获取边
	while (m--)
	{
		string a, b;
		int x;
		cin >> a >> b >> x;
		add(mp[a], mp[b], x);
		add(mp[b], mp[a], x);
	}
	// dijkstra
	di(mp[s1], mp[s2]);
	return 0;
}

Counting Leaves

感觉读题还是有点苦难，翻译一下题目吧

第一行输入两个数，树的节点数量N，非叶子节点数量M，然后剩下M行输入非叶子节点的ID,其孩子数量K，每个孩子的编号aia_i

输出，这个树中每一层，没有孩子的节点(叶子节点)的数量

看懂题目就很简单了，不就是宽搜，记录每一层的叶子节点就行了么

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
65
66
67
#include <bits/stdc++.h>
using namespace std;

const int N = 110, FLAG = 103;
vector<int> e[N];
int n, m, k;

void bfs()
{
	queue<int> q;
	// FLAG是一层的结束标志
	q.push(1);
	q.push(FLAG);
	// cnt用于记录每一层的叶子节点数量
	int cnt = 0;
	// 用于空格输出
	bool flag = false;
	while (q.size())
	{
		int now = q.front();
		q.pop();
		// 碰到结束标志直接输出cnt，重置cnt
		if (FLAG == now)
		{
			if (flag)
				cout << " ";
			cout << cnt;
			flag = true;
			cnt = 0;
			// 如果还有下一层才加入结束标志
			if (q.size())
				q.push(FLAG);
			continue;
		}
		// 如果是叶子节点，就cnt++
		if (!e[now].size())
		{
			cnt++;
			continue;
		}
		// 把每个孩子加入到队列中
		for (int i = 0; i < e[now].size(); i++)
		{
			int j = e[now][i];
			q.push(j);
		}
	}
}

int main()
{
	// freopen("1.txt","r",stdin);
	cin >> n >> m;
	while (m--)
	{
		int id;
		cin >> id >> k;
		while (k--)
		{
			int a;
			cin >> a;
			e[id].push_back(a);
		}
	}
	bfs();
	return 0;
}

Spell It Right

题目翻译：计算一个非负数字每一位上的数字之和，然后用英语表示每一位数上的数字

取每一位数字，然后加，用哈希表(或字符串数组)映射对应的数字就行，有手就行

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
#include <bits/stdc++.h>

using namespace std;

string str;

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> str;

	int sum = 0;
	string mp[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
	if (str == "0")
		cout << mp[0];
	stack<string> st;
    // 计算每一位的加和
	for (char a : str)
		sum += a - '0';
    // 存储每一位数字
	while (sum)
	{
		st.push(mp[sum % 10]);
		sum /= 10;
	}
    // 输出英文
	while (st.size())
	{
		cout << st.top();
		st.pop();
		if (st.size())
			cout << " ";
	}
	return 0;
}

Sign In and Sign Out

题目翻译：输入一个n，表示一天有n条记录，每个记录分别表示人的ID，进入时间和退出时间。最早进的要开门，最晚出的关门，找出开门和关门的人

那不是很简单的字符串比较就行了吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	string in, out_time = "00000000", out, in_time = "::::::::";
	// freopen("1.txt", "r", stdin);
	cin >> n;
	while (n--)
	{
		string id, time1, time2;
		cin >> id >> time1 >> time2;
		if (in_time > time1)
			in = id, in_time = time1;
		if (out_time < time2)
			out = id, out_time = time2;
	}
	cout << in << " " << out;
	return 0;
}

Maximum Subsequence Sum

题目翻译：求出一个序列中，所有数加和最大的连续子序列，输出连续子序列的求和值，第一个数字和最后一个数字(不是坐标！)，如果全是负数，和为0，然后输出整个序列的第一个数字和最后一个数字(不是坐标！)。

读题很重要，我就是输出了坐标然后寄了，他给的测试用例对应的数字竟然和坐标一样，就给我绕进去了，很痛苦。

思路很简单，就是遍历序列，然后求加法，如果碰到了加和更大的就更新重点，如果加到负数了，就重置起点，然后继续加。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int n, x, a[N];

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n;
	int start = 0, eee = 0, sum = -0x3f3f3f3f, res = 0;
	bool flag = false;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (a[i] >= 0)
			flag = true;
	}
	for (int i = 0, j = 0; i < n && flag; i++)
	{
		res += a[i];
		if (sum < res)
		{
			start = a[j];
			eee = a[i];
			sum = res;
		}
		if (res < 0)
		{
			res = 0;
			j = i + 1;
			continue;
		}
	}
	if (!flag)
		sum = 0, start = a[0], eee = a[n - 1];
	printf("%d %d %d", sum, start, eee);
	return 0;
}

Elevator

题目翻译：从0楼，按照给出的数据顺序去到对应的楼层，上楼6s，下楼4s，到了停5s，输出这个序列跑完要多久。

智商题，不说了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

int x;

int main()
{
	// freopen("1.txt","r",stdin);
	int now = 0, sum = 0;
	cin>>x;
	while (cin >> x)
	{
		if (x > now)
			sum += 6 * (x - now);
		else
			sum += 4 * (now - x);
		sum += 5;
		now = x;
	}
	cout << sum;
	return 0;
}

Product of Polynomials

题目翻译：多项式乘法

字面上意思，模拟就行

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
#include <bits/stdc++.h>

using namespace std;
int k, p;
double x;
// 存储多项式，其中greater是使其按照逆序的方式进行排序(从大到小)
map<int, double, greater<int>> A, B, C;
int main()
{
	// 输入第一多项式
	cin >> k;
	while (k--)
	{
		cin >> p >> x;
		A[p] = x;
	}
	// 输入第二个多项式
	cin >> k;
	while (k--)
	{
		cin >> p >> x;
		B[p] = x;
	}
	// 计算多项式乘法
	for (auto &i : A)
		for (auto &j : B)
			C[i.first + j.first] += i.second * j.second;
	// 计算多项式非0项的数量
	int cnt = 0;
	for (auto &i : C)
		if (i.second != 0)
			cnt++;
	cout << cnt;
	// 输出非0项
	for (auto &i : C)
		if (i.second != 0)
			printf(" %d %.1f", i.first, i.second);
	return 0;
}

Radix

题目翻译：给出两个任意进制的数，然后给出其中一个数的进制数，让你求另一个数是否存在一个进制与其对应，有就输出对应的进制数，没有输出Impossible

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
#include <bits/stdc++.h>
using namespace std;

unordered_map<char, int> mp;

long long get(string a, int b)
{
	// res是最终结果，t是每次乘以进制数的n次方，从0次方开始
	long long res = 0, t = 1;
	// 每次取出字符串的最后一位，取到没有为止
	while (a.size())
	{
		res = res + (mp[a.back()]) * t;
		t *= b;
		a.erase(a.size() - 1);
	}
	return res;
}

long long find(string a, long long b)
{
	// 取出目标中最大的那个字符
	char t = *max_element(a.begin(), a.end());
	// 字符转成数字，然后这个数字+1就是这个数的最小进制数的可能
	long long l = (isdigit(t) ? t - '0' : t - 'a' + 10) + 1;
	// 最大的话就是这个进制数或者给出的十进制数
	long long r = max(b, l);
	// 二分找到底是多少进制
	while (l <= r)
	{
		// 找到中间的进制
		long long mid = l + r >> 1;
		// 将其转化成十进制
		long long t = get(a, mid);
		// 如果大得越界了或者比目标值还大。更新右边界
		if (t < 0 || t > b)
			r = mid - 1;
		// 等就直接输出
		else if (t == b)
			return mid;
		// 小就更新左边界
		else
			l = mid + 1;
	}
	return -1;
}

int main()
{
	// freopen("1.txt", "r", stdin);
	for (int i = 0; i < 26; i++)
		mp['a' + i] = 10 + i;
	for (int i = 0; i < 10; i++)
		mp['0' + i] = i;
	string n1, n2;
	long long tag, radix, res;
	cin >> n1 >> n2 >> tag >> radix;
	res = tag == 1 ? find(n2, get(n1, radix)) : find(n1, get(n2, radix));
	if (res != -1)
		cout << res;
	else
		puts("Impossible");
	return 0;
}

World Cup Betting

题目翻译：玩一种游戏，有三个选择W,T,L,每个选择都有自己的一个赔率，会输入若干组这种赔率，每组选择最大的赔率，并输出赔率最大的选择。计算盈利计算方式为：（每组选的最大赔率的乘积*0.65-）*2

有手就行好吧(看懂题目的话)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

double w, t, l, sum = 1;

int main()
{
	// freopen("1.txt", "r", stdin);
	while (cin >> w >> t >> l)
	{
		char res = 'W';
		double res_num = w;
		if (res_num < t)
			res = 'T', res_num = t;
		if (res_num < l)
			res = 'L', res_num = l;
		cout << res << " ";
		sum *= res_num;
	}
	sum = (sum * 0.65 - 1) * 2;
	printf("%.2lf", sum);
	return 0;
}

The Best Rank

翻译题目：会输入N和M，表示总共学生数，和要查询的学生数。接着N行输入学生的ID，C语言，数学，英语的成绩，剩下M行输入学生的ID。

对于输出应该有M行，输出对应ID的最佳排名和这个排名对应的科目(A,C,M,E分别对应学生平均成绩，C语言，数学，英语，优先级为A>C>M>E)，如果ID不存在输出N/A

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
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>

using namespace std;

const int N = 2010;
unordered_map<string, int> mp;
struct Person
{
	string id;	  // 学生id
	char best;	  // 最佳排名的科目
	int br;		  // 最佳排名数值
	int score[4]; // 平均成绩，C，数学，英语的分数
	int rank[4];  // ACME的排名
} students[N];
char ranks[5] = {'A', 'C', 'M', 'E'}; // 对应学生结构体的rank
int n, m, flag = -1;				  // flag用于控制按照哪一个排序
// 排序函数
bool cmp1(Person a, Person b) { return a.score[flag] > b.score[flag]; }

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		// 将学生id和CME的分数进行存储
		cin >> students[i].id >> students[i].score[1] >> students[i].score[2] >> students[i].score[3];
		// 计算平均分，四舍五入加个0.5
		students[i].score[0] = (students[i].score[1] + students[i].score[2] + students[i].score[3]) / 3.0 + 0.5;
	}
	// 对四个分数分别排名
	for (flag = 0; flag < 4; flag++)
	{
		// 排序
		sort(students, students + n, cmp1);
		// 学生的排序如果有并列应该是1134而不是1123
		students[0].rank[flag] = 1;
		for (int i = 1; i < n; i++)
		{
			students[i].rank[flag] = i + 1;
			if (students[i].score[flag] == students[i - 1].score[flag])
				students[i].rank[flag] = students[i - 1].rank[flag];
		}
	}
	for (int i = 0; i < n; i++)
	{
		
		int idx = 0, r = students[i].rank[0];
		// 记录每个学生id对应结构体数组的下标
		mp[students[i].id] = i + 1;
		// 计算最佳排名
		for (int j = 1; j < 4; j++)
			if (students[i].rank[j] < r)
				idx = j, r = students[i].rank[j];
		students[i].best = ranks[idx];
		students[i].br = r;
	}
	// 接收输入
	while (m--)
	{
		string id;
		cin >> id;
		if (mp.count(id))
		{
			int idx = mp[id] - 1;
			cout << students[idx].br << " " << students[idx].best << endl;
		}
		else
			cout << "N/A" << endl;
	}
	return 0;
}

Battle Over Cities

题目翻译：先输入n,m,k表示有n个城市，m条通路，k次查询。对于m条通路会输入a，b表示两个城市之间有一条双向边，对于k次查询，表示当前输入的城市已经坏掉了，到这个城市以及从这个城市出发的线路都寄了，为了保证其他城市都能互相连通，最少需要多少条线路

这题就是一个去掉输入点找最大连通域的题，首先模拟去掉这个点后的图，在这个图中找出最大连通域的数量，输出这个数量-1就可以了。BFS就可以做了

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
65
66
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
vector<int> e[N]; // 邻接表
bool st[N];		  // 是否使用过
int n, m, k;	  // 节点数，边数，查询数

int bfs(int u)
{
	// 初始化使用情况
	memset(st, false, sizeof st);
	// 先标记这个点已经用过了，即不包括这个点
	st[u] = true;
	// 记录结果
	int ans = 0;
	// 遍历每一个点
	for (int i = 1; i <= n; i++)
		if (!st[i]) // 如果这个点没有被用过
		{
			ans++; // 连通分量+1
			queue<int> q;
			q.push(i);	  // 将这个连通分量存在队列里，与这个点相连的其他点全部标记为用过了
			st[i] = true; // 这个点用过了
			while (q.size())
			{
				int x = q.front();
				q.pop();
				// 遍历这个点可以到的点
				for (int j = 0; j < e[x].size(); j++)
				{
					int t = e[x][j]; // 取出下一个点的坐标
					if (!st[t])		 // 如果这个点被用过了就直接跳过
					{
						q.push(t); // 否则加入到队列中
						st[t] = true;
					}
				}
			}
		}
	return ans;
}

int main()
{
	// freopen("1.txt","r",stdin);
	cin >> n >> m >> k;
	while (m--)
	{
		// 记录邻接表和邻接矩阵
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	while (k--)
	{
		int u;
		cin >> u;
		// 计算去掉这个点后还有多少个连通分量
		int ans = bfs(u);
		cout << ans - 1 << endl;
	}
	return 0;
}

Waiting in Line

题目翻译：有N个窗口，每个窗口最多排队M个人，然后在第N*M+1个人及以后，需要全部排成一列，优先选择队伍较短的排。上班时间是8点钟，17点下班，等待实现超过后就不能排队了。给出K个人，每个人会有他的工作时间，然后给出Q个查询，查询每个人服务的事件点

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
#include <bits/stdc++.h>

using namespace std;

const int N = 25;
int w[N];
unordered_map<int, int> mp;
queue<int> q[N];
int n, m, k, qq;

int main()
{
	// freopen("1.txt","r",stdin);
	cin >> n >> m >> k >> qq;
	// 读取每一个人
	for (int i = 1; i <= k; i++)
	{
		int x;
		cin >> x;
		// 记录当前最佳的队伍
		int tmp = 0;
		// 遍历每一个窗口
		for (int j = 0; j < n; j++)
		{
			// 如果还在可以接受范围内
			if (i <= n * m)
			{
				// 比较哪个队伍最短
				if (q[j].size() < q[tmp].size())
					tmp = j;
			}
			else
			{
				// 如果满了，比较谁最先空出位置
				if (q[j].front() < q[tmp].front())
					tmp = j;
			}
		}
		// 记录这个窗口下一个可以服务的时间
		w[tmp] += x;
		// 如果超过了可接受范围，那么这个窗口的第一个人可以走了
		if (i > n * m)
			q[tmp].pop();
		// 将新人入队
		q[tmp].push(w[tmp]);
		// 如果这个人的等待时没有超过5点，就记录下塔的服务结束时间
		if (w[tmp] - x < 540)
			mp[i] = w[tmp];
	}
	while (qq--)
	{
		int x;
		cin >> x;
		// 如果没有记录，说明不能进行服务
		if (!mp.count(x))
			puts("Sorry");
		else
			printf("%02d:%02d\n", 8 + mp[x] / 60, mp[x] % 60);
	}
	return 0;
}

Reversible Primes

题目翻译：翻转质数，如果一个质数N在转化成D进制后进行翻转，其结果还是质数的话就称为这是一个翻转质数。题目每行会给出N和D，请你判断这个是不是翻转质数。

思路：首先肯定需要有一个函数判断是不是质数，接着就是有一个函数实现反转。

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
#include <bits/stdc++.h>

using namespace std;
int n, d;

// 是否为质数
bool is_prime(int x)
{
	if (x < 2)
		return false;
	for (int i = 2; i <= x / i; i++)
		if (x % i == 0)
			return false;
	return true;
}

// 翻转质数
int reverse_prime(int x, int r)
{
	// 这里用短除法进行进制转换，但是短除法的结果是从下往上看的，所以这里直接用queue就能从上往下看(即翻转后的质数)了
	queue<int> q;
	while(x){
		q.push(x%r);
		x/=r;
	}
	// 再将这个数字从r进制转化为10进制
	int res = 0;
	while(q.size()){
		res = res*r+q.front();
		q.pop();
	}
	return res;
}

int main()
{
	// freopen("1.txt","r",stdin);
	while (cin >> n >> d)
	{
		if (!is_prime(n))
			puts("No");
		else
		{
			n = reverse_prime(n, d);
			if(!is_prime(n)) puts("No");
			else puts("Yes");
		}
	}

	return 0;
}

PTA的一部分题(与PAT难度相似，中文题目，可以看看，但不包含在167题内)

题目详情 - L2-4 哲哲打游戏 (25 分) (pintia.cn)

image-20220419102716149

输入：

10 11
3 2 3 4
1 6
3 4 7 5
1 3
1 9
2 3 5
3 1 8 5
1 9
2 8 10
0
1 1
0 3
0 1
1 2
0 2
0 2
2 2
0 3
0 1
1 1
0 2

输出：

1
3
9
10

思路：很简单的，就是建棵树，然后按照他的操作模拟就行

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int n, m, save[N];
vector<int> e[N];

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n >> m;
	// 建树
	for (int i = 1; i <= n; i++)
	{
		int k;
		cin >> k;
		while (k--)
		{
			int x;
			cin >> x;
			e[i].push_back(x);
		}
	}

	int now = 1;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		// 0就往下走
		if (a == 0)
			now = e[now][b-1];
        // 1就存档和输出
		else if (a == 1)
		{
			save[b] = now;
			cout << now << endl;
		}
        // 2是读档
		else
			now = save[b];
	}
	cout << now;
	return 0;
}

题目详情 - L2-3 浪漫侧影 (25 分) (pintia.cn)

image-20220419115254131

输入

8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1

输出：

R: 1 2 3 4 5
L: 1 6 7 8 5

思路：

题目的意思是每层的最左元素放入left，最右元素放入right

建树：

后续的最后一个节点就是根节点
在中序中找到根节点，左边是左子树，右边是右子树

然后这题有一个测试样例没过，2分的，不要紧，错误信息是段错误，思路应该没有问题的。

N开到30出现越界，40越界，80A了？

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

using namespace std;

const int N = 80, FLAG = -1;
int mid[N], back[N];
int e[N][2];
int n;
vector<int> lefts, rights, q;

int find_mid(int x)
{
	for (int i = 0; i < n; i++)
		if (x == mid[i])
			return i;
	return -1;
}
// lb,rb后序数组的上界和下界
// lm,rm中序数组的上界和下界
int create_tree(int lb, int rb, int lm, int rm)
{
	// 后续的最后一个节点就是根节点
	// 在中序中找到根节点，左边是左子树，右边是右子树
	if (lb > rb)
		return -1;
	int root = back[rb];
	int pos = find_mid(root);
	// 获取左节点
    // 左子树有pos-lm个节点，右子树有rm-pos个节点
	int left = create_tree(lb, lb + pos - lm - 1, lm, pos - 1);
	// 获取右节点
	int right = create_tree(rb - rm + pos, rb - 1, pos + 1, rm);
	if (left > 0)
		e[root][0] = left;
	if (right > 0)
		e[root][1] = right;
	return root;
}

// 获取每层的第一个元素和最后一个元素
void bfs(int u)
{
	lefts.push_back(u);
	q.push_back(u);
	q.push_back(FLAG);
	int hh = 0, tail = 2;
	while (hh < q.size())
	{
		int t = q[hh++];
		if (t == FLAG)
			if (hh < q.size() && q[hh] != FLAG)
			{
				lefts.push_back(q[hh]);
				q.push_back(FLAG);
				tail++;
				continue;
			}
		if (q[hh] == FLAG)
			rights.push_back(t);
		if (e[t][0])
			q.push_back(e[t][0]), tail++;
		if (e[t][1])
			q.push_back(e[t][1]), tail++;
	}
	cout << "R:";
	for (int a : rights)
		cout << " " << a;
	puts("");
	cout << "L:";
	for (int a : lefts)
		cout << " " << a;
}

int main()
{
	// freopen("1.txt", "r", stdin);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> mid[i];
	for (int i = 0; i < n; i++)
		cin >> back[i];
	int root = create_tree(0, n - 1, 0, n - 1);
	bfs(root);
	return 0;
}

END