TUNIVERSE

PAT甲级2016春真题

算法 字符串 数学模拟 完全二叉树 最短路径
字数统计: 3.9k阅读时长: 20 min
2023/08/21

PAT考试真题解析

[1108] Finding Average (20)

字符串处理，sscanf()和sprintf()的使用

题目

The basic task is simple: given N real numbers, you are supposed to calculate their average. But what makes it complicated is that some of the input numbers might not be legal. A legal input is a real number in $[−1000,1000]$ and is accurate up to no more than 2 decimal places. When you calculate the average, those illegal numbers must not be counted in.

注意点与解析

  • 这道题的难点是输入的字符串很难解析，不仅要判断输入的字符串是否是一个合法且符号要求在-1000到1000的数字，是否有小数点部分且小数点部分是否不超过两位。

  • 比较好的做法是使用sscanf 和sprintf

    • sscanf() 从一个字符串中读进与指定格式相符合的数据；
    • sprinf() 字符串格式化命令，主要功能是把格式化的数据写入某个空字符中。

    当sscanf读入的字符串没有与之匹配的数据类型的时候，返回的值会是浮点数的0，这样在sprintf将这个结果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
int main() {
  int n, cnt = 0;
  char a[50], b[50];
  double temp = 0.0, sum = 0.0;
  cin >> n;
  for(int i = 0; i < n; i++) {
    scanf("%s", a);
    sscanf(a, "%lf", &temp);
    sprintf(b, "%.2f",temp);
    int flag = 0;
    for(int j = 0; j < strlen(a); j++)
      if(a[j] != b[j]) flag = 1;
    if(flag || temp < -1000 || temp > 1000) {
      printf("ERROR: %s is not a legal number\n", a);
      continue;
    } else {
      sum += temp;
      cnt++;
    }
  }
  if(cnt == 1)
    printf("The average of 1 number is %.2f", sum);
  else if(cnt > 1)
    printf("The average of %d numbers is %.2f", cnt, sum / cnt);
  else
    printf("The average of 0 numbers is Undefined");
  return 0;
}

[1109] Group Photo (25)

数学模拟

题目

Formation is very important when taking a group photo. Given the rules of forming K rows with N people as the following:

  • The number of people in each row must be $N/K$ (round down to the nearest integer), with all the extra people (if any) standing in the last row;
  • All the people in the rear row must be no shorter than anyone standing in the front rows;
  • In each row, the tallest one stands at the central position (which is defined to be the position $(m/2+1)$, where $m$ is the total number of people in that row, and the division result must be rounded down to the nearest integer);
  • In each row, other people must enter the row in non-increasing order of their heights, alternately taking their positions first to the right and then to the left of the tallest one (For example, given five people with their heights 190, 188, 186, 175, and 170, the final formation would be 175, 188, 190, 186, and 170. Here we assume that you are facing the group so your left-hand side is the right-hand side of the one at the central position.);
  • When there are many people having the same height, they must be ordered in alphabetical (increasing) order of their names, and it is guaranteed that there is no duplication of names.

Now given the information of a group of people, you are supposed to write a program to output their formation.

Input Specification:

Each input file contains one test case. For each test case, the first line contains two positive integers $N (≤10^4)$, the total number of people, and $K (≤10)$, the total number of rows. Then N lines follow, each gives the name of a person (no more than 8 English letters without space) and his/her height (an integer in $[30, 300]$).

Output Specification:

For each case, print the formation – that is, print the names of people in $K$ lines. The names must be separated by exactly one space, but there must be no extra space at the end of each line.
Note: since you are facing the group, people in the rear rows must be printed above the people in the front rows.

注意点与解析

  • 这题主要是进行模拟，找到排队的规律。注意“我”是面对拍照的人，所以最矮的在最后一行，从我的视角来看的话也是高的先插在左边，即和题意反过来。
  • 由于身高一样的时候要按字典序增加的顺序进行排，高到低、相同身高字典序小到大，所以字典序小的在左边；
  • 那么对于输入的人的身高和姓名，我们保存在一个数组里， 然后对他们进行一次排序，排序的规则如上，即 return a.height == b.height? a.name < b.name: a.height > b.height;
  • 计算出每行的人数 $N/K$，剩下的人放最后一排 $N-N/K*(K-1)$；题目告诉我们每行的中间，即第 $m/2+1$（$m$是每行的人数）是最高的人，对应数组下标就是$m/2$。在每一行里我们开一个 vector<string> 类型的临时变量用来存放本行的排队结果，先固定中间的人，然后有两种思路：
    • 比如对于一行 0 1 2 3 4，我们按照题目说的顺序按 21304 的顺序进行填充；
    • 例子同上，我们按照 2、10、34的顺序填充，也就是填完中间先填左边再填右边，或者先填右边再填左边；

代码

方案1

第一种方案只需要开一个变量i，初始化为1，代表距离中间位置的偏移距离；同时开一个计数器k判断目前这行是否排完，每排一个人计数器自增；外部的大计数器cnt用于从高到低、从名字小到大计人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cnt = 0;
for (int row = 0; row < k; row++) {
  if (!row) m = n - n / k * (k - 1);
  else  m = n / k;
  vector<string> col(m);
  col[m/2] = vec[cnt++].name;

  int k = 1;
  for (int i = 1; k < m; i++) {
    if (m / 2 - i >= 0) {
      col[m/2-i] = vec[cnt++].name;
      k++;
    }
    if (m / 2 + i < m) {
      col[m/2+i] = vec[cnt++].name;
      k++;
    }
  }
}

方案2

第二种方案是参考柳婼学姐的。先把中间位置的左边全填了，对应到排序好的学生数组里的位置就是从cnt+1后开始每次加2的距离，col数组则是m/2-1开始每次减1的距离（这里cnt在填人的循环里是不变的，都是学生数组里本行最高的那个人的索引，在本行全部填完之后再加上本行人数）；右边也是一样的，学生数组的初始位置是cnt+2，col数组的初始位置是m/2+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sort(vec.begin(), vec.end(), [&](Person a, Person b) {
  return a.height == b.height? a.name < b.name: a.height > b.height;
});

int cnt = 0;
for (int i = 0; i < k; i++) {
  if (!i)  m = n - n / k * (k-1);
  else  m = n / k;
  vector<string> columns(m);
  // 中间位置是m/2+1，数组下标就是m/2
  columns[m/2] = vec[cnt].name;

  int j = m / 2 - 1;
  for (int k = cnt + 1; k < cnt + m; k += 2)
    columns[j--] = vec[k].name;
  j = m / 2 + 1;
  for (int k = cnt + 2; k < cnt + m; k += 2)
    columns[j++] = vec[k].name;
}

[1110] Complete Binary Tree (25)

完全二叉树

题目

Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (≤20)$ which is the total number of nodes in the tree – and hence the nodes are numbered from $0$ to $N−1$. Then $N$ lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each case, print in one line YES and the index of the last node if the tree is a complete binary tree, or NO and the index of the root if not. There must be exactly one space separating the word and the number.

注意点与解析

  • 被一个很弱智的点给卡住了，输入的N大小不大于20，所以每个结点的左右结点有可能是11、16这样的两位数，变量不能开char要开string（因为经常用 a - '0' 这样的写法所以形成了惯性思维开成了char），转换的时候用 stoi() 就行；
  • 主要思路是利用完全二叉树的静态性质，dfs出最后一个结点应该在静态数组里的下标，判断其是否等于结点个数。
  • 下标初始为1，左结点为 2 * idx，右结点为 2 * idx + 1。注意dfs回溯的过程中idx的值可能会变小，要注意保存。
  • dfs函数两个参数一个是真实存储的下标这里也即结点的值（root->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
47
48
49
50
struct Node {
  int left, right;
};
vector<Node> node;
vector<bool> isRoot;
int ans, maxn = -1;

void dfs(int root, int idx) {
  if (idx > maxn) {
    // maxn用来记录当前位置下标，等会用于比较是否大于结点个数来判断是否是完全二叉树
    // ans用来记录最后一个最后一个结点的值
    // idx > maxn的条件是用来防止覆盖的
    maxn = idx;
    ans = root;
  }
  if (node[root].left != -1)
    dfs(node[root].left, 2 * idx);
  if (node[root].right != -1)
    dfs(node[root].right, 2 * idx + 1);
  return;
}

int main () {
  int n;
  cin >> n;
  node.resize(n);
  isRoot.resize(n, true);
  for (int i = 0; i < n; i++) {
    string a, b;
    cin >> a >> b;
    if (a == "-")  node[i].left = -1;
    else {
      node[i].left = stoi(a);
      isRoot[stoi(a)] = false;
    }
    if (b == "-")  node[i].right = -1;
    else {
      node[i].right = stoi(b);
      isRoot[stoi(b)] = false;
    }
  }
  int root = 0;
  while (!isRoot[root])  root++;
  dfs(root, 1);
  if (maxn == n)
    cout << "YES " << ans;
  else
    cout << "NO " << root;
  return 0;
}

[1111] Online Map (30)

题目

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers $N (2≤N≤500)$, and $M$, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

1
V1 V2 one-way length time

where V1 and V2 are the indices (from 0 to $N−1$) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format:

1
Distance = D: source -> v1 -> ... -> destination

Then in the next line print the fastest path with total time T:

1
Time = T: source -> w1 -> ... -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:

1
Distance = D; Time = T: source -> u1 -> ... -> destination

注意点与解析

  • 好像是第一次用邻接表写Dijkstra算法，刚好想试一下就这么写了，后来听网上的朋友们说最后一个测试点会超时，可能是用了邻接矩阵的问题；这道题没什么特别的，考试遇到会笑醒的程度，就是两个最短路径搜索，耐心做就行。
  • 用spfa又做了一遍结果遇到一个bug一直没法解决，后来发现吧，是 set<Node> 出了问题，由于Node是自定义的结构体，应该要给一个排序规则，重载一下 operator< 给个排序规则就行。
  • 感觉代码冗余有点多，有空可以封装一下dijkstra、spfa、dfs函数（有空再说）。

代码

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
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
const int MAXN = 0x3fffffff;
int n, m, s, e;
int minTime = MAXN, ansNum = MAXN;
vector<vector<Node>> Adj, pre;
vector<int> d, vis;
vector<Node> ansPath_1, ansPath_2, tempPath;

void Dijkstra_1(int s) {
  d[s] = 0;
  for (int i = 0; i < n; i++) {
    int u = -1, mx = MAXN;
    for (int j = 0; j < n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)  return;
    vis[u] = true;
    for (auto p: Adj[u]) {
      if (vis[p.v] == false) {
        if (d[u] + p.dis < d[p.v]) {
          d[p.v] = d[u] + p.dis;
          pre[p.v].clear();
          pre[p.v].push_back(Node(u, p.dis, p.time));
        } else if (d[u] + p.dis == d[p.v]) {
          pre[p.v].push_back(Node(u, p.dis, p.time));
        }
      }
    }
  }
  return;
}

void dfs_1(Node cur) {
  tempPath.push_back(cur);
  if (cur.v == s) {
    int tempTime = 0;
    for (int i = tempPath.size() - 1; i > 0; i--)
      tempTime += tempPath[i].time;
    if (tempTime < minTime) {
      minTime = tempTime;
      ansPath_1 = tempPath;
    }
    tempPath.pop_back();
    return;
  }
  for (auto p: pre[cur.v])
    dfs_1(p);
  tempPath.pop_back();
  return;
}

void Dijkstra_2(int s) {
  d[s] = 0;
  for (int i = 0; i < n; i++) {
    int u = -1, mx = MAXN;
    for (int j = 0; j < n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)  return;
    vis[u] = true;
    for (auto p: Adj[u]) {
      if (vis[p.v] == false) {
        if (d[u] + p.time < d[p.v]) {
          d[p.v] = d[u] + p.time;
          pre[p.v].clear();
          pre[p.v].push_back(Node(u, p.dis, p.time));
        }
        else if (d[u] + p.time == d[p.v]) {
          pre[p.v].push_back(Node(u, p.dis, p.time));
        }
      }
    }
  }
  return;
}

void dfs_2(Node cur) {
  tempPath.push_back(cur);
  if (cur.v == s) {
    if (tempPath.size() < ansNum) {
      ansNum = tempPath.size();
      ansPath_2 = tempPath;
    }
    tempPath.pop_back();
    return;
  }
  for (auto p: pre[cur.v])
    dfs_2(p);
  tempPath.pop_back();
  return;
}

int main() {
  cin >> n >> m;
  Adj.resize(n);
  pre.resize(n);
  vis.resize(n, false);
  d.resize(n, MAXN);

  int v1, v2, flag, len, tt;
  for (int i = 0; i < m; i++) {
    cin >> v1 >> v2 >> flag >> len >> tt;
    Adj[v1].push_back(Node(v2, len, tt));
    if (flag != 1)
      Adj[v2].push_back(Node(v1, len, tt));
  }
  cin >> s >> e;
  int ansDis = 0, ansTime = 0;
  Dijkstra_1(s);
  dfs_1(Node(e, 0, 0));
  for (int i = ansPath_1.size() - 1; i > 0; i--)
    ansDis += ansPath_1[i].dis;

  fill(d.begin(), d.end(), MAXN);
  fill(vis.begin(), vis.end(), false);
  for (auto p: pre)  p.clear();
  tempPath.clear();

  Dijkstra_2(s);
  dfs_2(Node(e, 0, 0));
  for (int i = ansPath_2.size() - 1; i > 0; i--)
    ansTime += ansPath_2[i].time;

  // .........
}

SPFA

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
struct Node {
  int v;
  int dis;
  int time;
  Node(int _v, int _dis, int _time): v(_v), dis(_dis), time(_time) {}
};
bool operator< (const Node & x, const Node & y) {
  return x.v < y.v;
}

const int MAXN = 0x3fffffff;
int n, m, s, e;
vector<int> vis, d, inq;
vector<vector<Node>> Adj;
vector<set<Node>> pre;
vector<Node> tempPath, ansPath_1, ansPath_2;

void spfa_for_distance(int s) {
  d.resize(n, MAXN);
  inq.resize(n, false);
  d[s] = 0;
  queue<int> q;
  q.push(s);
  inq[s] = true;

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (auto p: Adj[u]) {
      if (d[u] + p.dis < d[p.v]) {
        d[p.v] = d[u] + p.dis;
        pre[p.v].clear();
        pre[p.v].insert(Node(u, p.dis, p.time));
        if (!inq[p.v]) {
          q.push(p.v);
          inq[p.v] = true;
        }
      } else if (d[u] + p.dis == d[p.v]) {
        pre[p.v].insert(Node(u, p.dis, p.time));
      }
    }
  }
  return;
}

int minTime = MAXN;
void dfs_for_distance(Node cur) {
  tempPath.push_back(cur);
  if (cur.v == s) {
    int curTime = 0;
    for (int i = tempPath.size() - 1; i > 0; i--)
      curTime += tempPath[i].time;
    if (curTime < minTime) {
      minTime = curTime;
      ansPath_1 = tempPath;
    }
    tempPath.pop_back();
    return;
  }
  set<Node>::iterator it;
  for (it = pre[cur.v].begin(); it != pre[cur.v].end(); it++)
    dfs_for_distance(*it);
  tempPath.pop_back();
  return;
}

void spfa_for_time(int s) {
  fill(d.begin(), d.end(), MAXN);
  fill(inq.begin(), inq.end(), false);
  fill(vis.begin(), vis.end(), false);
  for (auto p: pre) p.clear();
  tempPath.clear();

  d[s] = 0;
  queue<int> q;
  q.push(s);
  inq[s] = true;

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (auto p: Adj[u]) {
      if (d[u] + p.time < d[p.v]) {
        d[p.v] = d[u] + p.time;
        pre[p.v].clear();
        pre[p.v].insert(Node(u, p.dis, p.time));
        if (!inq[p.v]) {
          q.push(p.v);
          inq[p.v] = true;
        }
      } else if (d[u] + p.time == d[p.v]) {
        pre[p.v].insert(Node(u, p.dis, p.time));
      }
    }
  }
  return;
}

int minNum = MAXN;
void dfs_for_time(Node cur) {
  tempPath.push_back(cur);
  if (cur.v == s) {
    if (tempPath.size() < minNum) {
      minNum = tempPath.size();
      ansPath_2 = tempPath;
    }
    tempPath.pop_back();
    return;
  }
  set<Node>::iterator it;
  for (it = pre[cur.v].begin(); it != pre[cur.v].end(); it++)
    dfs_for_time(*it);
  tempPath.pop_back();
  return;
}

int main() {
  cin >> n >> m;
  Adj.resize(n);
  pre.resize(n);
  vis.resize(n, false);

  int ansDis = 0, ansTime = 0;
  int v1, v2, flag, len, tt;
  for (int i = 0; i < m; i++) {
    cin >> v1 >> v2 >> flag >> len >> tt;
    Adj[v1].push_back(Node(v2, len, tt));
    if (flag != 1)
      Adj[v2].push_back(Node(v1, len, tt));
  }
  cin >> s >> e;
  spfa_for_distance(s);
  dfs_for_distance(Node(e, 0, 0));
  for (int i = ansPath_1.size() - 1; i > 0; i--)
    ansDis += ansPath_1[i].dis;
  spfa_for_time(s);
  dfs_for_time(Node(e, 0, 0));
  for (int i = ansPath_2.size() - 1; i > 0; i--)
    ansTime += ansPath_2[i].time;

  // ........
}
CATALOG
  1. 1. [1108] Finding Average (20)
    1. 1.1. 题目
    2. 1.2. 注意点与解析
    3. 1.3. 代码
  2. 2. [1109] Group Photo (25)
    1. 2.1. 题目
      1. 2.1.1. Input Specification:
      2. 2.1.2. Output Specification:
    2. 2.2. 注意点与解析
    3. 2.3. 代码
      1. 2.3.1. 方案1
      2. 2.3.2. 方案2
  3. 3. [1110] Complete Binary Tree (25)
    1. 3.1. 题目
      1. 3.1.1. Input Specification:
      2. 3.1.2. Output Specification:
    2. 3.2. 注意点与解析
    3. 3.3. 代码
  4. 4. [1111] Online Map (30)
    1. 4.1. 题目
      1. 4.1.1. Input Specification:
      2. 4.1.2. Output Specification:
    2. 4.2. 注意点与解析
    3. 4.3. 代码
      1. 4.3.1. Dijkstra
      2. 4.3.2. SPFA
Total : 68
2024
2023
2022
2021
2020
计算机视觉 三维重建 深度学习 动态规划 查找 教程 MongoDB 数据库 Neo4j MySQL 机器学习 GNN 随笔 故障诊断 Greenplum操作 Linux磁盘扩容 debug记录 环境问题 托福 多维索引 磁盘故障 列存分区 迁移学习 链表 LeetCode 双指针 剪枝 素数 逻辑题 并查集 树的遍历 字符串 数学模拟 完全二叉树 最短路径 哈希 排序 二叉搜索树 贪心 图论 图模拟 Set AVL树 DFS 栈 拓扑排序 递推 快乐模拟 图的遍历 前端 React Webpack Eslint top
华科课程 算法 学习笔记 年末总结 腾讯AI训练营 英语 database