Fork me on GitHub

PAT-A-1005

PAT-A-1005

所有甲级题全解

原题链接

生僻词汇:

consecutive 连续的

题意

给定一个数 A,求各数位之和,格式化输出

知识点

整型范围判定

C/C++ 字符数组与字符串选择使用

ASCII 转整型

思路

$N$ 的范围是 $10^{100}$ ,显然远超 long long (约 $10^{18}$),考虑使用 string 接 ASCII 转数字

注意不要打错字,建议检查,或者直接复制粘贴

代码

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
#include <iostream>
#include <string>

using namespace std;
int sum = 0;
string num;
string str[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"
};

int main() {
//输入
cin >> num;

//各数位之和
for (int i = 0; i < num.length(); i++) {
sum += num[i] - '0';
}

//转字符串
string res = to_string(sum);
int i = 0;

//格式化输出,输出尾部不应有0
while (i != res.length()) {
if (i != res.length() - 1) {
cout << str[res[i] - '0'] << " ";
}
else {
cout << str[res[i] - '0'] << endl;
}
i++;
}
return 0;
}

免费博客制作教程

免费博客制作教程

本篇教程使用 Git + Github Page + hexo,服务器与框架均免费使用,可搭配域名。

获取 github page

参考 官方教程

申请仓库,注意仓库命名有硬性要求,一般为 username.github.io

Squ1rrel-K.github.io

Git 下安装 hexo

参考 官方文档

新建 username.github.io 文件夹

hexo init

npm install

安装主题 theme

官方主题区

找到适合自己的主题,按制作者要求处理即可

写作与上传

新建文章 hexo new post newTitle

进入 md 软件写作

渲染上传 hexo d -g

其它常用命令见官方文档

PAT-A-1003

PAT-A-1003

所有甲级题全解

原题链接

生僻词汇

scattered 分散的

题意

你是个救援队头子,要从 A 到 B 点去救人,路途城市的人手可以捎上,求最短路径数量,跟最短路情况下最多救援队人数

知识点

图的最短路径问题

多路径的第二权计算

思路

非负权最短路显然用 Dijkstra 算法

多解用 vector 储存

计算比较第二权,即点权:人手

代码

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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int maxN = 501;
const int INF = 0x3fffffff;
int n, m, c1, c2, p1, p2, l, minDis = INF, maxPeo = 0, numOfDis = 0;
int G[maxN][maxN], w[maxN], d[maxN];
bool vis[maxN] = {false};
vector<int> pre[maxN];
vector<int> tmp;

void Dij(int c) {
//重置距离
fill(d, d + maxN, INF);
d[c] = 0;

//找最近的结点 n 次
for (int i = 0; i < n; i++) {
//找下一个最近的结点 u
int u = -1, Min = INF;
for (int v = 0; v < n; v++) {
if (vis[v] == false && d[v] < Min) {
u = v;
Min = d[v];
}
}

//未找到最近结点 u
if (u == -1) return;

//访问 u
vis[u] = true;

//尝试更新最短距离 u -> v
for (int v = 0; v < n; v++) {
//未访问,可访问
if (vis[v] == false && G[u][v] != INF) {
//路径相等
if (d[u] + G[u][v] == d[v]) {
//更新前驱结点
pre[v].push_back(u);
}
//路径更短,更新
else if (d[u] + G[u][v] < d[v]) {
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}
}
}
}
}

void DFS(int v) {
//边界条件
if (v == c1) {
tmp.push_back(v);
int dis = 0, peo = 0;

//计算路径 - 边权
for (int i = 0; i < tmp.size() - 1; i++) {
int u1 = tmp[i], u2 = tmp[i + 1];
dis += G[u1][u2];
}

//计算人数 - 点权
for (int i = 0; i < tmp.size(); i++) {
int u = tmp[i];
peo += w[u];
}

//若为最短路径
if (dis < minDis) {
numOfDis = 1;
minDis = dis;
maxPeo = peo;
}

//若最短路径不唯一
else if (dis == minDis) {
numOfDis++;
if (peo > maxPeo) maxPeo = peo;
}
tmp.pop_back();
}

//递归式
tmp.push_back(v);
for (int i = 0; i < pre[v].size(); i++) {
DFS(pre[v][i]);
}
tmp.pop_back();
}

int main() {
//输入
scanf("%d%d%d%d", &n, &m, &c1, &c2);

//点权赋值
for (int i = 0; i < n; ++i) {
scanf("%d", &w[i]);
}

//关闭图
fill(G[0], G[0] + maxN * maxN, INF);

//边权赋值
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &p1, &p2, &l);
G[p1][p2] = G[p2][p1] = l;
}

Dij(c1);
DFS(c2);
printf("%d %d", numOfDis, maxPeo);
return 0;
}

PAT-A-1002

PAT-A-1002

所有甲级题全解

原题链接

生僻词汇

Polynomial 多项式

exponent 指数

coefficient 系数

题意

给 A,B 两个多项式,求和

知识点

变量类型合理选择

简单在线处理

数组下标模拟多项式指数

格式化输出

思路

$N$ 上界只有 $10^3$,400ms 时限,两个数组直接暴力检索显然可以接受,但是在线处理可以保证时间复杂度始终在 $O(n)$

代码

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
#include <cstdio>

const int maxN = 1005;
double arr[maxN] = {0};
int k, n, cnt = 0;
double an;

int main() {
int t = 2;

//循环2次,输入2个多项式
while (t--) {
scanf("%d", &k);

//在线处理
while (k--) {
scanf("%d%lf", &n, &an);
arr[n] += an;
}
}

//非零项数
for (int i = 0; i < maxN; i++) {
if (arr[i] != 0) cnt++;
}

//输出
printf("%d", cnt);
for (int i = maxN - 1; i >= 0; i--) {
if (arr[i] != 0) {
printf(" %d %.1f", i, arr[i]);
}
}
}
  • Copyrights © 2020-2023 Jack Kong
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信