没有合适的资源?快使用搜索试试~ 我知道了~
首页PAT 题目精解但(包括1000题)
资源详情
资源评论
资源推荐

1001. A+B Format (20) [字符处]
Calculate a + b and output the sum in standard format — that is, the digits must be separated into groups
of three by commas (unless there are less than four digits).
Input
Each input file contains one test case. Each case contains a pair of integers a and b where -1000000 <= a,
b <= 1000000. The numbers are separated by a space.
Output
For each test case, you should output the sum of a and b in one line. The sum must be written in the
standard format.
Sample Input
-1000000 9
Sample Output
-999,991
题意:计算A+B的和,然后以每三位加个”,” 的格式输出。
分析:把a+b的和转为字符s。除第位是负号的情况,只要当前位的下标i满(i + 1) % 3 == len %
3并且i是最后位,就在逐位输出的时候在该位输出后的后加上个逗号
1002. A+B for Polynomials (25) [模拟]
This time, you are supposed to find A+B where A and B are two polynomials.
Input
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information
of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial,
Ni and aNi (i=1, 2, …, K) are the exponents and coe!icients, respectively. It is given that 1 <= K <= 10,0
<= NK < … < N2 < N1 <=1000.
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
string s = to_string(a + b);
int len = s.length();
for (int i = 0; i < len; i++) {
cout << s[i];
if (s[i] == '-') continue;
if ((i + 1) % 3 == len % 3 && i != len - 1) cout << ",";
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Mail: 2583245026@qq.com UUID: 1d69577b-04f5-311c-972d-33f0d472160f

Output
For each test case you should output the sum of A and B in one line, with the same format as the input.
Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.
Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 2 1.5 1 2.9 0 3.2
题意:计算A+B的和,A和B都是多项式。
分析:设c数组,度为指数的最值,c[i] = j表示指数i的系数为j,接收a和b输的同时将对应指数
的系数加到c中,累计c中所有零系数的个数,然后从后往前输出所有系数为0的指数和系数~
1003. Emergency (25) [Dijkstra算法]
As an emergency rescue team leader of a city, you are given a special map of your country. The map
shows several scattered cities connected by some roads. Amount of rescue teams in each city and the
length of each road between any pair of cities are marked on the map. When there is an emergency call
to you from some other city, your job is to lead your men to the place as quickly as possible, and at the
#include <iostream>
using namespace std;
int main() {
float c[1001] = {0};
int m, n, t;
float num;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d%f", &t, &num);
c[t] += num;
}
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%f", &t, &num);
c[t] += num;
}
int cnt = 0;
for (int i = 0; i < 1001; i++) {
if (c[i] != 0) cnt++;
}
printf("%d", cnt);
for (int i = 1000; i >= 0; i--) {
if (c[i] != 0.0)
printf(" %d %.1f", i, c[i]);
}
return 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
Mail: 2583245026@qq.com UUID: 1d69577b-04f5-311c-972d-33f0d472160f

mean time, call up as many hands on the way as possible.
Input
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<=
500) – the number of cities (and the cities are numbered from 0 to N-1), M – the number of roads, C1 and
C2 – the cities that you are currently in and that you must save, respectively. The next line contains N
integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each
describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the
length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
Output
For each test case, print in one line two numbers: the number of di!erent shortest paths between C1 and
C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at
the end of a line.
Sample Input
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output
2 4
题意:n个城市m条,每个城市有救援组,所有的边的边权已知。给定起点和终点,求从起点
到终点的最短径条数以及最短径上的救援组数之和。如果有多条就输出点权(城市救援组
数)最的那个~
分析:遍dijkstra算法。救援组个数相当于点权,Dijkstra求边权最的最短径的条数,以及
这些最短径中点权最的值~
dis[i]:从出发点到i结点最短径的径度,num[i]:从出发点到i结点最短径的条数,w[i]:从出
发点到i点救援队的数之和。
当判定dis[u] + e[u][v] < dis[v]的时候,仅仅要新dis[v],还要新num[v] = num[u], w[v] = weight[v]
+ w[u]; 如果dis[u] + e[u][v] == dis[v],还要新num[v] += num[u],且判断下是否权重w[v],如
果就新w[v] = weight[v] + w[u];
#include <iostream>
#include <algorithm>
1
2
Mail: 2583245026@qq.com UUID: 1d69577b-04f5-311c-972d-33f0d472160f

1004. Counting Leaves (30) [BFS,DFS,树的层序遍历]
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who
have no child.
using namespace std;
int n, m, c1, c2;
int e[510][510], weight[510], dis[510], num[510], w[510];
bool visit[510];
const int inf = 99999999;
int main() {
scanf("%d%d%d%d", &n, &m, &c1, &c2);
for(int i = 0; i < n; i++)
scanf("%d", &weight[i]);
fill(e[0], e[0] + 510 * 510, inf);
fill(dis, dis + 510, inf);
int a, b, c;
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &a, &b, &c);
e[a][b] = e[b][a] = c;
}
dis[c1] = 0;
w[c1] = weight[c1];
num[c1] = 1;
for(int i = 0; i < n; i++) {
int u = -1, minn = inf;
for(int j = 0; j < n; j++) {
if(visit[j] == false && dis[j] < minn) {
u = j;
minn = dis[j];
}
}
if(u == -1) break;
visit[u] = true;
for(int v = 0; v < n; v++) {
if(visit[v] == false && e[u][v] != inf) {
if(dis[u] + e[u][v] < dis[v]) {
dis[v] = dis[u] + e[u][v];
num[v] = num[u];
w[v] = w[u] + weight[v];
} else if(dis[u] + e[u][v] == dis[v]) {
num[v] = num[v] + num[u];
if(w[u] + weight[v] > w[v])
w[v] = w[u] + weight[v];
}
}
}
}
printf("%d %d", num[c2], w[c2]);
return 0;
}
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
Mail: 2583245026@qq.com UUID: 1d69577b-04f5-311c-972d-33f0d472160f

Input
Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of
nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children,
followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to
be 01.
Output
For each test case, you are supposed to count those family members who have no child for every
seniority level starting from the root. The numbers must be printed in a line, separated by a space, and
there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence
on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should
output “0 1” in a line.
Sample Input
2 1
01 1 02
Sample Output
0 1
题意:给出棵树,问每层各有多少个叶结点。
分析:可以dfs也可以bfs。
dfs的话,维数组保存每个有孩结点的结点以及他们的孩结点,从根结点开始遍历,直到遇
到叶结点,就将当前层数depth的book[depth]++; 标记第depth层拥有的叶结点数,最后输出~
如果bfs,设两个数组,第个level,保存i结点的层数,为bfs的时候可以让当前结点的层数是
它的结点层数+1,第个数组book,保存i层所拥有的叶结点的个数。变maxlevel保存最的层
数~
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[100];
int book[100], maxdepth = -1;
void dfs(int index, int depth) {
if(v[index].size() == 0) {
book[depth]++;
maxdepth = max(maxdepth, depth);
return ;
}
for(int i = 0; i < v[index].size(); i++)
dfs(v[index][i], depth + 1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Mail: 2583245026@qq.com UUID: 1d69577b-04f5-311c-972d-33f0d472160f
剩余292页未读,继续阅读
















安全验证
文档复制为VIP权益,开通VIP直接复制

评论0