PAT甲级

发表于 更新于 分类于 ， 本文字数： 5.1k 阅读时长 ≈ 5 分钟

前言

记录一下自己写的代码，可能有些比较粗糙，部分会参考一下网上的思路。

不定期更新，闲的时候会刷一题。

代码用python或者C++编写，python占大部分。

1001 A+B Format (20分)

大概意思是标准化输出两数之和，每三位加一个逗号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a,b = map(int,input().split())
he = str(a + b)
if he[0]=='-':
    print('-',end='')
    he = he[1:]
y = len(he)%3
if y:
    print(he[:y],end='')
else:
    print(he[:3],end='')
    y=3
for i in range(int((len(he)-y)/3)):
    l = i*3+y
    print(',',end='')
    print(he[l:l+3],end='')

1002 A+B for Polynomials (25分)

题目大意是输出多项式A+B的和

思路是用一个大数组来存所有系数，对应相加输出非零系数

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
#include<iostream>
using namespace std;
int main(){
    int n,m,t;
    float f;
    float c[1001] = {0};
    scanf("%d",&n);
    for(int i = 0; i < n;i++){
        scanf("%d%f",&t,&f);
        c[t] += f;
    }
    scanf("%d",&m);
    for(int i = 0; i < m;i++){
        scanf("%d%f",&t,&f);
        c[t] += f;
    }
    int cot=0;
    for(int i = 0; i<1001; i++){
        if(c[i]!=0){
            cot++;
        }
    }
    printf("%d",cot);
    for(int i = 1000; i>=0; i--){
        if(c[i]!=0.0){
            printf(" %d %.1f",i,c[i]);
        }
    }
    return 0;
}

1003 Emergency (25分)

题目大意是你作为医疗队队长需要在任务中选取最短路径方案，并尽可能多的人手。

这题可以使用迪杰斯特拉算法(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
# N number of cities
# M number of roads
# C1 strart
# C2 end
# team_num number of rescue teams 
# adjacent 连接矩阵


def Dijkstra(C1,C2):
    dist = [Max for i in range(N)]                              # 标记距离长度
    dist[C1] = 0
    flag_node = [-1 for i in range(N)]                          # 标记已经确定最短路径的列表
    flag_node[C1] = 1
    res = [[] for i in range(N)]                                # 记录需要的答案
    res[C1] = [1,team_num[C1]]
    p = C1                                                 # 指针节点
    for i in range(N):                                          # 循环直到所有节点都被标记
        if flag_node[C2] == 1:                                   # 如果C2已经被确定，退出循环
            break
        # 如果C2未被确定，从当前路径开始寻找下一节点
        for i in range(N):
            temp_dist = adjacent[p][i]
            if (flag_node[i] == -1) and (temp_dist != Max):  # 查询该节点未确定的通路
                if dist[i] > (dist[p] + temp_dist): # 判断是否需要更新
                    dist[i] = dist[p] + temp_dist
                    res[i] = [res[p][0],res[p][1]+team_num[i]]
                elif dist[i] == (dist[p] + temp_dist):
                    res[i][0] += res[p][0]
                    if res[i][1] < (res[p][1]+team_num[i]):
                        res[i][1] = res[p][1]+team_num[i]
        #寻找最小值进行标记
        mini = Max
        for i in range(N):
            if flag_node[i] == -1:
                if dist[i] < mini:
                    mini = dist[i]
                    p = i
        flag_node[p] = 1
    return res[C2]
    

Max = 1000000
#接收数据
N,M,C1,C2 = map(int,input().split())
team_num = list(map(int,input().split()))
# 建立连接矩阵
adjacent = [ [Max for i in range(N)] for i in range(N) ]
for i in range(M):
    a,b,l = map(int,input().split())
    adjacent[a][b] = l
    adjacent[b][a] = l


# 使用Dijkstra算法
# num 总共医疗数量
# long 总路程
answer = Dijkstra(C1,C2) # 如有多个结果res会返回多个列表
print(answer[0],answer[1])


1004 Counting Leaves (30分)

题目是根据家族树找每一代的无后代人数。先将家族谱按树状结构存储，然后使用 深度优先搜索遍历。当然广度优先算法也应是可以的。两者的复杂度相同。

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
# 深度优先遍历搜索
def dfs(ID, depth):
    global max_depth
    max_depth = max(max_depth,depth)    # 判断最大深度
    visited[ID] = True                  # 标记节点
    if ID not in tree:
        res[depth] += 1
        return
    else:
        for child in tree[ID]:
            if child not in visited:
                dfs(child, depth + 1)   # 递归


N,M = map(int,input().split())
tree = {}                   # 树
res = [0 for i in range(N)] # 记录答案列表
visited = {}                # 标记访问过的节点
max_depth = 0               # 最大树深度

# 构建树结构
for i in range(M):
    node_id , k, *child_id = list(input().split())
    tree[node_id] = child_id
    
dfs('01', 0) # 输入初始节点
# 按格式输出
for i in range(max_depth):
    print(res[i],end = ' ')
print(res[max_depth])

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
# 广度优先搜索
class treenode():
    """定义节点类"""
    def __init__(self, depth, child_number=0, child_id=[]):
        """初始化类
            depth 深度
            child_number 子节点数量
            child_id 字节点id
        """
        self.depth = int(depth)
        self.child_number = int(child_number)
        self.child_id = child_id
        
class queqe():
    """定义队列类"""
    def __init__(self):
        """初始化队列"""
        self._ls = []
        
    def add_item(self,treenode):
        """添加元素"""
        self._ls.append(treenode)

    def get_item(self):
        """弹出第一个值"""
        r, self._ls = self._ls[0],self._ls[1:]
        return r
        
    def empty(self):
        """判断是否为空"""
        return len(self._ls) == 0

def bfs(ID):
    global max_depth
    visited[ID] = True
    queqe.add_item(treenode(0,tree[ID][0],tree[ID][1]))
    while not queqe.empty():
        v = queqe.get_item()
        nowdepth = v.depth
        max_depth = max(nowdepth,max_depth)
        for i in v.child_id:
            if i not in visited:
                visited[i] = True
                if i not in tree:
                    res[nowdepth+1] += 1
                else:
                    queqe.add_item(treenode(nowdepth+1,tree[i][0],tree[i][1]))
        
    
    
    

N,M = map(int,input().split())

if N == 1:
    print(1)
else:
    tree = {}       # 树字典
    res = [0 for i in range(N)] # 记录答案列表
    visited = {} # 标记访问过的节点
    max_depth = 0 # 最大树深度
    # 构建树结构
    for i in range(M):
        node_id , k, *child_id = list(input().split())
        tree[node_id] = [k,child_id]
        
    queqe = queqe()
    bfs('01')
    max_depth += 1
    for i in range(max_depth):
        print(res[i],end = ' ')
    print(res[max_depth])

1005 Spell It Right (20分)

1
2
3
4
5
6
7
8
9
10
11
N = input()
s = 0
dic = ["zero","one","two","three","four",\
	"five","six","seven","eight","nine"]

for i in N:
    s += int(i)
    
for i in str(s)[:-1]:
    print(dic[int(i)],end=" ")
print(dic[int(str(s)[-1])])

1006 Sign In and Sign Out (25分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
M = int(input())
ID, intime, outtime = input().split()
unl_id = ID
unl_time = intime
l_id = ID
l_time = outtime
for i in range(M-1):
    ID, intime, outtime = input().split()
    if intime < unl_time:
        unl_id = ID
        unl_time = intime
    if outtime > l_time:
        l_id = ID
        l_time = outtime
print(unl_id, l_id)