米哈游笔试8.13后端题解

欢迎点赞交流讨论

T1

先后经过三个点，求最短距离；平面可连接扩展。

模拟即可，参考代码：

m, n = list(map(int, input().split()))
x1, y1 = list(map(int, input().split()))
x2, y2 = list(map(int, input().split()))
x3, y3 = list(map(int, input().split()))

def f(a, b, l):
    return min(abs(a-b), abs(min(a, b)+l - max(a, b)))
  
print(f(x1, x2, m)+f(y1, y2, n)+f(x2, x3, m)+f(y2, y3, n))

T2

向有根树的叶添加节点，使得距离根一定范围内的节点数最大。

只需要关心叶节点和它的深度即可，注意是无向图，不要被例题图片迷惑了，参考代码：

# Python默认的最大递归深度是1000，小于本题的范围，要设置下
import sys
sys.setrecursionlimit(1000000000)

n, k = list(map(int, input().split()))
G = [[] for i in range(n)]

for _ in range(n-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)
    
def dfs(cur, depth, parent):
    if depth>k:
        return 0
    ans = 1
    if len(G[cur])>1 or parent==-1:
        for child in G[cur]:
            if child!=parent:
                ans += dfs(child, depth+1, cur)
    else:
        ans += max(0, k-depth)
    return ans
  
print(dfs(0, 0, -1))

T3

抽卡题，规则不再赘述，玩过原的应该会熟悉些。跟实际游戏还是有点区别的，实际上89抽之前也会增大抽取概率，本题留了一手。

数据范围很小，维护一个第i抽出金的概率数组，二层循环模拟即可，最后期望就是抽数乘以概率的累加和。参考代码：

p = float(input())
tmp = [0]*181

def wai(cur, index):
    for i in range(1, 90):
        tmp[index+i] += cur*p
        cur = cur*(1-p)
    tmp[index+90]+= cur

cur = 1
for i in range(1, 90):
    tmp[i] += cur*p/2
    wai(cur*p/2, i)
    cur = cur*(1-p)
tmp[90] += cur/2
wai(cur/2, 90)
print(sum([i*tmp[i] for i in range(len(tmp))]))

个人认为整体难度很白给，没有任何难度算法和数据结构，比暑期实习的题简单多了