首页 > 网易互娱 9.5 算法笔试
头像
插科打诨小组长
编辑于 2020-09-05 17:41
+ 关注

网易互娱 9.5 算法笔试

第一题 AC
思路:维护N个stack,统计每个人拿在手里和包里的商品价值

N, M = list(map(int, input().strip().split(' ')))
prices = list(map(int, input().strip().split(' '))) # 单价
stack = [[prices[i]] * 10000 for i in range(N)]
ans = [0] * M
for _ in range(M):
    operation = int(input().strip())
    temp_prices = {'left': 0, 'right': 0}
    for i in range(operation):
        inp = input().strip().split(' ')
        if inp[1] == 'take':
            temp_prices[inp[0]] = stack[int(inp[2]) - 1][-1]
            stack[int(inp[2]) - 1].pop(-1)
        elif inp[1] == 'return':
            stack[int(inp[2]) - 1].append(temp_prices[inp[0]])
            temp_prices[inp[0]] = 0
        elif inp[1] == 'keep':
            ans[_] += temp_prices[inp[0]]
            temp_prices[inp[0]] = 0
    ans[_] += temp_prices['left'] + temp_prices['right']

for a in ans:
    print(a)
第二题 AC
思路:移动角色,判断字符是否改变,需要注意的是,移动完角色,要对非角色部分进行修正,还原成背景
def print_matrix(m):
    for mm in m:
        print(''.join(mm))
    print('===')


T = int(input().strip())
for _ in range(T):
    W, H = list(map(int, input().strip().split(' ')))
    ori_bg = []
    bg = []
    for i in range(H):
        bg.append(list(input().strip()))
        ori_bg.append(bg[-1][:])
    P, Q = list(map(int, input().strip().split(' ')))
    person = []
    for i in range(Q):
        person.append(list(input().strip()))
    i, j, a, b = list(map(int, input().strip().split(' ')))
    # 第i行第j列,从1开始计数
    # 向右移动a列,向下移动b行
    # i,j和a,b都可能是负数,所以是上下左右都可能移动

    # 行:H, i, b, Q
    # 列:W, j, a, P
    ans = 0
    while not ((i + Q - 1 < 1 and b < 0)&nbs***bsp;(j + P - 1 < 1 and a < 0)&nbs***bsp;(i > H and b > 0)&nbs***bsp;(j > W and a > 0)):
        for ii in range(i, i + Q):
            for jj in range(j, j + P):
                if ii < 1&nbs***bsp;ii > H:
                    continue
                if jj < 1&nbs***bsp;jj > W:
                    continue
                if bg[ii - 1][jj - 1] != person[ii - i][jj - j]:
                    bg[ii - 1][jj - 1] = person[ii - i][jj - j]
                    ans += 1
        # print(ans)
        # print_matrix(bg)

        
        for ii in range(1, H + 1):
            for jj in range(1, W + 1):
                if ii >= i and ii < i + Q and jj >= j and jj < j + P:
                    continue
                if bg[ii - 1][jj - 1] != ori_bg[ii - 1][jj - 1]:
                    bg[ii - 1][jj - 1] = ori_bg[ii - 1][jj - 1]
                    ans += 1
        # print(ans)
        # print_matrix(bg)
        # 更新
        i += b
        j += a
        # print(ans)
        # print('============')
        # ans = 0
    for ii in range(1, H + 1):
        for jj in range(1, W + 1):
            if bg[ii - 1][jj - 1] != ori_bg[ii - 1][jj - 1]:
                bg[ii - 1][jj - 1] = ori_bg[ii - 1][jj - 1]
                ans += 1
    print(ans)


'''
1
4 4
....
....
....
....
3 3
.O.
/|\
./\
0 0 -1 -1
'''
第三题:50% 超时
思路:邻接表构图,bfs跑最短路
def pos(now):
    return (now[0], now[1])

T = int(input().strip())
# 0, 1, 2, 3: 上,下,左,右
direction = {'0': [-1, 0], '1': [1, 0], '2': [0, -1], '3': [0, 1]}
for _t in range(T):
    N = int(input().strip())
    graph = {}
    now = [0, 0]
    for _n in range(N):
        x, y = input().strip().split(' ')
        d = direction[x]
        if y == '-1':
            continue
        new = [now[0] + d[0], now[1] + d[1]]
        pos_now = pos(now)
        pos_new = pos(new)
        if pos_now not in graph.keys():
            graph[pos_now] = set()
        graph[pos_now].add(pos_new)
        if pos_new not in graph.keys():
            graph[pos_new] = set()
        graph[pos_new].add(pos_now)
        for k, v in direction.items():
            temp_new = [new[0] + v[0], new[1] + v[1]]
            pos_temp_new = pos(temp_new)
            if pos_temp_new in graph.keys():
                graph[pos_new].add(pos_temp_new)
                graph[pos_temp_new].add(pos_new)
        now = new[:]

    start = (0, 0)
    end = pos(now)

    queue = [start]
    queue_set = set()
    queue_set.add(start)
    dis = 0
    vis = set()
    end_node = None
    last_end_node = start
    while queue:
        node = queue.pop(0)
        queue_set.remove(node)
        vis.add(node)
        flag = False
        for v in graph[node]:
            if v == end:
                flag = True
                break
            if v in vis&nbs***bsp;v in queue_set:
                continue
            queue.append(v)
            queue_set.add(v)
            end_node = v
        if flag:
            break
        if last_end_node == node:
            last_end_node = end_node
            dis += 1
    print(dis + 1)

'''
1
9
0 1
3 1
3 1
1 1
2 1
1 1
3 1
3 1
0 1
'''

'''
1
10
0 1
0 -1
1 1
1 1
1 -1
0 1
2 1
2 -1
3 1
3 1

1
2
3 1
3 1


1
8
0 1
0 1
3 1
3 1
1 1
1 1
2 1
0 1
'''




全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐