3-22笔试记录 网易互娱(2.1/3)&360java方向(2/2)&美团第三场(2.2/3)
网易互娱
（1）第一题题目大意是每天可以选一个股票买，卖出之前买的，直接贪心找前一天买哪一个可以在今天赚的最多，亏钱前一天就不买
n, m, k = map(int, input().split())
ans = [[-1,-1] for _ in range(n)]
pre = []
from math import inf
for i in range(n):
now = list(map(float, input().split()))
if pre:
mxd = k
mxi = -1
for j in range(m):
if k / pre[j] * now[j] > mxd:
mxd = k / pre[j] * now[j]
mxi = j
# print(mxd, mxi)
k = mxd
ans[i - 1][1] = mxi
ans[i][0] = mxi
pre = now
print(k)
for i in range(n):
print(ans[i][0], ans[i][1])
（2）根据题意模拟就好了，问题是他这个题意不明确，看样例才知道只每次移动只能消一次
# 0上 1左 2下 3右
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
for _ in range(int(input())):
c = list(map(int, input().split()))
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, len(c)):
k = c[i]
if k == 0: # 上
st = set()
for x in range(n):
for y in range(m):
if not g[x][y]: continue
px, py = x, y
X = px + dx[k]
Y = py + dy[k]
while X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == 0:
g[X][Y], g[px][py] = g[px][py], g[X][Y]
px = X
py = Y
X = px + dx[k]
Y = py + dy[k]
if X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == g[px][py] and (X, Y) not in st:
g[px][py] = 0
g[X][Y] *= 2
st.add((X, Y))
if k == 1: # 左
st = set()
for y in range(m):
for x in range(n):
if not g[x][y]: continue
px, py = x, y
X = px + dx[k]
Y = py + dy[k]
while X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == 0:
g[X][Y], g[px][py] = g[px][py], g[X][Y]
px = X
py = Y
X = px + dx[k]
Y = py + dy[k]
if X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == g[px][py] and (X, Y) not in st:
g[px][py] = 0
g[X][Y] *= 2
st.add((X, Y))
if k == 2: # 下
st = set()
for x in range(n - 1, -1, -1):
for y in range(m):
if not g[x][y]: continue
px, py = x, y
X = px + dx[k]
Y = py + dy[k]
while X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == 0:
g[X][Y], g[px][py] = g[px][py], g[X][Y]
px = X
py = Y
X = px + dx[k]
Y = py + dy[k]
if X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == g[px][py] and (X, Y) not in st:
g[px][py] = 0
g[X][Y] *= 2
st.add((X, Y))
if k == 3: # 右
st = set()
for y in range(m - 1, -1, -1):
for x in range(n):
if not g[x][y]: continue
px, py = x, y
X = px + dx[k]
Y = py + dy[k]
while X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == 0:
g[X][Y], g[px][py] = g[px][py], g[X][Y]
px = X
py = Y
X = px + dx[k]
Y = py + dy[k]
if X >= 0 and Y >= 0 and X < n and Y < m and g[X][Y] == g[px][py] and (X, Y) not in st:
g[px][py] = 0
g[X][Y] *= 2
st.add((X, Y))
# print(*g, sep="\n")
for i in range(n):
print(*g[i])
（3）写这题还有两个小时，我一看以为只能用exgcd，当时相的是枚举两个，然后exgcd求另外两个，然后想了一下想不起来怎么写了，然后蒙了-1和全0的样例下机了。。。实际上这题还可以用map存两个，再枚举两个，还是O(n^2)的复杂度，对自己无语了
360
我先做的选择题，只能说无敌了，像是祖传的题库，什么jdbc，statement，execute。。。
然后是算法题
（1）第一题题意是每天给你一个数，然后从1开始，当你解锁i之后你才能继续解锁i+1，然后问所有数字解锁的时间，其实就是求mex，直接模拟就行了
n = int(input())
a = list(map(int, input().split()))
st = set()
mex = 0
ans = [0] * n
for i, x in enumerate(a,start = 1):
st.add(x)
while mex + 1 in st:
ans[mex] = i
mex += 1
print(*ans)
（2）第二题是按顺序给你一堆坐标，每当加一个坐标，如果这个坐标8个方向上有其他坐标，那么可以得到的总价值是这个连接的连通块数量的平方，然后问你每一次加坐标时的总价值是多少，连通块大小很自然想到并查集，但是因为是坐标，只能哈希表维护并查集感觉不太好，不知道正解是怎么样的
'''
八个方向
并查集
'''
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
n = int(input())
a = []
for i in range(n):
a.append(tuple(map(int, input().split())))
ans = 0
from collections import defaultdict
f = defaultdict(tuple)
mp = defaultdict(int)
def find(x):
if x in f:
if x != f[x]:
f[x] = find(f[x])
else:
f[x] = x
return f[x]
def union(x, y):
x = find(x)
y = find(y)
f[y] = x
sst = set()
for u, v in a:
res = 0
st = set()
sst.add((u, v))
for i in range(8):
x = u + dx[i]
y = v + dy[i]
if (x, y) in sst:
st.add(find((x, y)))
for x, y in st:
# print((u, v), x, y, mp[(x, y)])
ans -= mp[(x, y)] ** 2
res += mp[(x, y)]
union((u, v), (x, y))
# print(ans, res)
ans += (res + 1) ** 2
mp[find((u,v))] = (res + 1)
print(ans)
美团第三场
我申请的岗位已经结束了，但是还是收到了笔试，不知道什么意思，而且听说美团根本不看笔试，然后就想着随便乱写了
选择题很多ai相关的，完全看不懂，乱选根本没有心里负担
（1）第一题忘了，总之很简单
s = input()
n = len(s)
ans = 0
key = "AHIMOTUVWXY"
for l in range(n):
if s[l] not in key:continue
for r in range(l + 2, n + 1):
if s[r - 1] not in key:break
if s[l:r] == s[l:r][::-1]:
ans += 1
print(ans)
（2）第二题暴力，没想到过了，懒得证明为啥复杂度可以了
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = n
for i in range(1, n - 1):
l = i - 1
r = i + 1
gt = 0
lt = 0
while l >= 0 and r < n:
if a[r] > a[i] > a[l] or a[r] < a[i] < a[l]:
if gt == lt:
ans += 1
else:
if a[l] > a[i]:
gt += 1
else:
lt += 1
if gt == lt:
ans += 1
l -= 1
r += 1
print(ans)
（3）懒得看了，粘了一个暴力，过了20%
n, k = map(int, input().split())
s = input()
ans = [0] * n
mp = [k]
for i in s:
if i == 'L':
for j in range(len(mp)):
mp[j] -= 1
mp[j] = max(1, mp[j])
elif i == 'R':
for j in range(len(mp)):
mp[j] += 1
mp[j] = min(n, mp[j])
else:
st = set()
for j in range(len(mp)):
k = mp[j] - 1
k = max(1, k)
st.add(k)
for j in range(len(mp)):
k = mp[j] + 1
k = min(n, k)
st.add(k)
mp = list(st.copy())
for i in mp:
ans[i - 1] = 1
print("".join(str(c) for c in ans))
投递网易互娱等公司10个岗位 >