笔试后：小马智行题目讨论

第一题：分糖果

n, k = 5, 10
A = [2,1,5,2,4]

tmp = []
for i in range(len(A)):
    tmp.append([A[i], i+1])

tmp.sort(key=lambda x: x[0])

target = k
n = len(A)
pre = 0
for i in range(len(tmp)):
    if (tmp[i][0] - pre) * n < target:
        target -= (tmp[i][0] - pre) * n
        pre = tmp[i][0]
        n = len(A) - i - 1
    elif (tmp[i][0] - pre) * n == target:
        print(len(A))
    else:
        break

index = target % n
candidate = tmp[i:]
candidate.sort(key=lambda x:x[1])
print(candidate[index-1][1])

第二题：

递归：也错了（30%）

import functools  nums = list(map(int, input().split(" ")))
n, m = nums[0], nums[1]

arr = [[0] * m for _ in range(n)]

def trans(s):
    if s == '^':
        return (-1, 0)
    elif s == 'v':
        return (1, 0)
    elif s == '<':
        return (0, -1)
    elif s == '>':
        return (0, 1)
    else:
        return (5, 5)

for i in range(n):
    ss = list(input())
    for j in range(m):
        arr[i][j] = trans(ss[j])

flag = [[0] * m for _ in range(n)]  @functools.lru_cache(None) def dfs(i, j):
    if i < 0&nbs***bsp;j < 0&nbs***bsp;i == n&nbs***bsp;j == m:
        return 0

    if flag[i][j] == 1:
        flag[i][j] = 0
        return 0

    flag[i][j] = 1
    cur_i, cur_j = arr[i][j]
    dist = dfs(i+cur_i, j+cur_j)
    flag[i][j] = 0
    return dist + 1

maxlength = 0
for i in range(n):
    for j in range(m):
        if dist[i][j] == -1:
            maxlength = max(maxlength, dfs(i, j))

print(maxlength)

非递归：错了（10%）

nums = list(map(int, input().split(" ")))
n, m = nums[0], nums[1]

arr = [[0] * m for _ in range(n)]

def trans(s):
    if s == '^':
        return (-1, 0)
    elif s == 'v':
        return (1, 0)
    elif s == '<':
        return (0, -1)
    else:
        return (0, 1)

for i in range(n):
    ss = list(input())
    for j in range(m):
        arr[i][j] = trans(ss[j])

flag = [[0] * m for _ in range(n)]
dist = [[-1]*m for _ in range(n)]

def dfs(i, j):
    stack = []
    sign = True
    ring = None
    while stack&nbs***bsp;sign == True:
        sign = False
        if i < 0&nbs***bsp;j < 0&nbs***bsp;i == n&nbs***bsp;j == m:
            break

        if flag[i][j] == 1:
            ring = (i, j)
            break

        if dist[i][j] != -1:
            curdist = dist[i][j]
            for i in range(len(stack) - 1, -1, -1):
                cur_i, cur_j = stack[i]
                curdist += 1
                dist[cur_i, cur_j] = curdist
            return curdist

        flag[i][j] = 1
        stack.append((i, j))
        next_i, next_j = arr[i][j]
        i, j = i + next_i, j +next_j

    if not ring:
        curdist = 0
        for i in range(len(stack)-1, -1, -1):
            cur_i, cur_j = stack[i]
            curdist += 1
            dist[cur_i][cur_j] = curdist
    else:
        curdist = 0
        index = 0
        for i in range(len(stack)-1, -1, -1):
            cur_i, cur_j = stack[i]
            curdist += 1
            if cur_i == ring[0] and cur_j == ring[1]:
                index = i
                break
        for i in range(len(stack)-1, -1, -1):
            cur_i, cur_j = stack[i]
            if i > index:
                dist[cur_i][cur_j] = curdist
            else:
                curdist += 1
                dist[cur_i][cur_j] = curdist

    return curdist

maxlength = 0
for i in range(n):
    for j in range(m):
        if dist[i][j] == -1:
            maxlength = max(maxlength, dfs(i, j))

print(maxlength)

第三题：没有看见不可以重复使用，写的动态规划的子序列问题，我说我怎么总比答案多

#小马智行笔试#