B. The Tag Game

题意大意

有一颗以1为根,节点数为n的树,A在1号点,B在x号点,A,B交替行动,A的目标是行动次数尽量少,B的目标是行动次数尽量多,问在这种情况下,行动的次数.

经典学校oj过了cf过不了,我提交的只考虑了树的最大深度。

python

错误解答

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
n, x = map(int,input().split())
 
 
graph = {}
res = 0
 
def dfs(v,l):
    global res
    st[v] = True
     
    for i in graph[v]:
        if not st[i]:
            dfs(i,l+1)
    res = max(res, l)
    return
 
for i in range(n-1):
    a,b = map(int,input().split())
    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)
    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)
st = [False for _ in range(n+10)]
 
 
dfs(1,0)
 
print(res*2)

正确解答

  • 1.B一直往上走，直到与A相撞。
  • 2.B往上走，然后到某一个点拐弯，往下走到底。
  • 为什么采用dfs而不是bfs，因为从x到达y只有一种路径
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
import sys
sys.setrecursionlimit(100000)
input = lambda:sys.stdin.readline().strip()
n, x = map(int, input().split())

graph = {}
disa = [-1] * (n + 1)
disb = [-1] * (n + 1)

def dfsa(u, parent):
    disa[u] = disa[parent] + 1 
    for v in graph[u]:
        if v != parent:
            dfsa(v, u)

def dfsb(u, parent):
    disb[u] = disb[parent] + 1
    for v in graph[u]:
        if v != parent:
            dfsb(v, u)


for _ in range(n - 1):
    a, b = map(int, input().split())
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)

# Perform DFS from node 1 (Alice's starting point)

dfsa(1,0)

# Perform DFS from node x (Bob's starting point)

dfsb(x,0)

maxval = 0

for i in range(1, n + 1):
    if disb[i] < disa[i]:  # Bob can reach before Alice
        maxval = max(maxval, disa[i] * 2)

print(maxval)

F tram

题目大意

给你s,x1,x2,t1,t2,p,d,分别表示一段路的长度(从0~s),你的起点和终点,汽车每t1秒跑1m,你每t2秒跑1m，汽车刚开始在点p,方向是d(1表示向右,-1表示向左),汽车每次到达端点都会瞬间往回走,不断往返,你可以 在任何时候上车或者下车,问你到达终点需要最少多少时间

1