网易互娱 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
''' 
