AtCoder abc148

C题
求GCD

D题
顺序遍历

E题
trailing zero只与5的个数有关，因此算一下5/25/125…的倍数

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100050)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n = int(fp.readline())
    if n & 1:
        print(0)
    else:
        t = 5 * 2
        ans = 0
        while t <= n:
            ans += n // t
            t *= 5
        print(ans)


if __name__ == "__main__":
    main()

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

F题
首先对每个点分别求到A和到T的最短路径。记为da与dt数组，接下来稍微要动一下脑子。
需要找到T能“躲藏”的最长路径，也就是da[i] > dt[i]的i。A只需要等待在前一个格子让T遇上A即可。

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100050)


def bfs(g, u):
    n = len(g)
    dist = [-1] * n
    qu = deque()
    dist[u] = 0
    qu.append(u)
    while qu:
        cur = qu.popleft()
        for v in g[cur]:
            if dist[v] == -1:
                dist[v] = dist[cur] + 1
                qu.append(v)
    return dist


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n, u, v = map(int, fp.readline().split())
    u, v = u - 1, v - 1
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        x, y = map(int, fp.readline().split())
        x, y = x - 1, y - 1
        g[x].append(y)
        g[y].append(x)
    du, dv = bfs(g, u), bfs(g, v)

    ans = 0
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i] - 1)
    print(ans)


if __name__ == "__main__":
    main()

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