美团笔试20220910

题目来源：nowcoder.com/discuss/1047578

之前用删除线删除的是我自己凭代码回想的

数据范围和描述可能会有点差别，所以还是贴上原来的题目

第一题 AC

输入t表示接下来有t轮数据

接下来每行 n, x, y, k

其实n表示作业的份数

x表示小美每小时做x份作业

y表示小团每小时做y份作业

k表示小美需要从第一份作业做到第k份，小团需要从第n份作业做到第k份作业

如果小美快，输出"Win"，平局"Tie"，输掉"Lose"

Solution

小美需要的时间是k/x，小团是(n+1-k)/y

哪个更小哪个赢，为了避免浮点数误差，用乘法比较

t = int(input())
for _ in range(t):
    n, x, y, k = map(int, input().split())

    # k/x , (n-k)/y

    ans = k * y - x * (n + 1 - k)
    if ans < 0:
        print("Win")
    elif ans == 0:
        print("Tie")
    else:
        print("Lose")

第二题 AC

给你一个n，表示数组的长度

接下来给你一个数组a

你可以对数组中的任意元素进行+1操作

求要让数组中所有数的和不为0且所有数的积不为0 最少需要的次数

内存限制： 589824KB
题目描述：
某天，小美在调试她的神经网络模型，这个模型共有n个参数，目前这些参数分别为a1、a2、…、an，
为了让参数看起来更加随机而且增加训练效果，她需要调节参数使所有参数满足a1+a2+…+an≠0且a1a2…*an≠0，她每次可以选择一个参数ai并将其变为ai+1，小美请你帮她计算一下，最少需要几次操作才能使参数达到她的要求。

输入描述
第一行一个正整数n，表示参数个数。

第二行为n个正整数a1, a2,...... an，其中ai表示第i个参数初始值。

1 ≤ n ≤ 30000，-1000 ≤ ai ≤ 1000。

输出描述
输出一个正整数，表示最少需要的操作次数。

Solution

首先把0变成1,需要cnt[0]次

再检查数组的和是不是0，是0的话答案需要+1

from typing import Counter

n = int(input())
nums = list(map(int, input().split()))
cnt = Counter(nums)
res = cnt[0]
total = sum(nums) + res
print(res + (total == 0))

第三题 AC

有一个无限大的迷宫，标号为1,2,3,..,inf

x迷宫，可以单向通往2x或者2x+1

给定一个n，表示接下来宝藏数组的长度

一个数组p，表示第i个宝藏在p[i]个房间

一个数组w，表示第i个宝藏的价值为w[i]

你可以在任意一个迷宫的位置退出

求你能获得的最大宝藏值

数据范围

0 < n < 3e4

0 < p[i] < 2**32

0 < w[i] < 1e4

某天小美进入了一个迷宫探险，根据地图所示，这个迷宫里有无数个房间，序号分别为1、2、3、…、∞，入口房间的序号为1，任意序号为正整数x的房间都与序号2x和 2x+1的房间之间各有一条路径，但是这些路径是单向的，即只能从序号为x的房间去到序号为2x或2x+1的房间，而不能从序号为2x或2x+1的房间去到序号为x的房间。在任何时刻小美都可以选择结束探险并离开迷宫，但是离开之后将无法再次进入迷宫。小美还提前了解了迷宫中宝藏的信息，已知宝藏共有n个，其中第 i 个宝藏在序号为pi的房间，价值为wi，且一个房间中可能有多个宝藏。小美为了得到更多的宝藏，需要精心规划路线，她找到你帮忙，想请你帮她计算一下，能获得的宝藏价值和最大值为多少。

输入描述
第一行一个正整数n，表示宝藏数量。

第二行为n个正整数p1, p2,...... pn，其中pi表示第 i 个宝藏在序号为pi的房间。

第三行为n个正整数w1, w2,...... wn，其中wi表示第i个宝藏的价值为wi。

数字间两两有空格隔开

1 ≤ n ≤ 40000, 1 ≤ pi ＜2**30, 1 ≤ wi ≤ 1e6。

输出描述
输出一个正整数表示能获得的宝藏价值之和的最大值。

Solution

用哈希表存储每个房间的宝藏

注意x只能从x//2房间转移而来

所有我们要算f(x) 先算出f(x//2)

再根据f(x) 更新最大值即可

from collections import defaultdict

n = int(input())
dic = defaultdict(int)

p = list(map(int, input().split()))
w = list(map(int, input().split()))

for idx, val in zip(p, w):
    dic[idx] += val

limit = max(dic.values())

vis = set()

def dfs(x):
    if x == 0:
        return 0
    if x not in vis:
        dic[x] += dfs(x >> 1)
        vis.add(x)
    return dic[x]

for x in sorted(dic.keys()):
    dfs(x)

# print(dic)

print(max(dic.values()))

第四题 55% 其余超时

这是最难的一题

第一行，给你n，m

n表示接下来数组的长度

第二行，一个数组a，a[i] 是非负整数

你可以耗费一个时间把 a[i] 变成 a[i] + pow(10,k) 其中 0<=k<=9

如果a[i] 超过m 需要对m求余

输出答案数组 res

res[i] 为把a[i] 变成 0 的最小时间

数据范围

0<= a[i] < 3e4

a[i] < m < 3e4

Solution

首先把可以加的数 pow(10,k) 其中 0<=k<=9 处理一下

事实上，他们的贡献只有 pow(10,k,m) ，也就是对m求余

然后我们要通过加上 pow(10,k,m) 中的数把x变成m的倍数

这是一个背包问题，做的时候我偷懒用了bfs实现，结果果然超时

之后有时间的话，应该会再把这题实现一下

（确实是一个bfs问题，只是需要注意思考的方向）

from collections import deque
from functools import lru_cache

n, m = map(int, input().split())
nums = list(map(int, input().split()))
dic = set(pow(10, i, m) for i in range(0, 10))
if 0 in dic:
    dic.remove(0)
dic = list(dic)

@lru_cache(None)
def f(x):
    cnt = 0
    vis = set()
    q = deque([x])
    while True:
        cnt += 1
        tn = len(q)
        for _ in range(tn):
            s = q.popleft()
            vis.add(s)
            for add in dic:
                d = (s + add) % m
                if d == 0:
                    return cnt
                if d not in vis:
                    q.append(d)

for x in nums:
    if x == 0:
        print(0, end=" ")
        continue
    print(f(x), end=" ")

第四题更新

前面一样，重点在于如何最快从x到m

我们反过来考虑，建一个数组f，f[m] = 0

其他的全部初始化为无穷大，然后根据m和增量数组dic 去更新其他值

具体逻辑为，如果更新过说明之前已经访问过这个点，跳过

否则更新，并把该点加入队列

由于m最大为3e4，所以时间复杂度也就是3e4

from collections import deque
from functools import lru_cache
from math import inf

n, m = map(int, input().split())
nums = list(map(int, input().split()))
dic = set(pow(10, i, m) for i in range(0, 10))
if 0 in dic:
    dic.remove(0)
dic = list(dic)

f = [inf] * (m + 1)
f[m] = 0
q = deque([m])
while q:
    x = q.popleft()
    for d in dic:
        y = (x - d + m) % m
        if (ncnt := f[x] + 1) < f[y]:
            f[y] = ncnt
            q.append((y, ncnt))

for x in nums:
    print(f[x], end=" ")

第五题 AC

再来谈谈这道浪费了半个多小时的题

给你一个字符串s，其中0<=s[i]<=0 ，len(s) < 1e6

你可以把s分成任意段 ，输出最多有多少段可以整除7

时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美有一串项链，项链共由n颗宝石组成，每个宝石上都有一个数字。但是有一天项链不小心被弄断了，变成了一长串，此时可以看成一个只包含数字的字符串，于是她准备将项链从某些地方切开后再重新分成多段（每段都是原来字符串的连续子串，且不能再重新组合），因为小美特别喜欢7这个数字，所以她希望切开后每段的数字和都尽可能被7整除。
例如，假设项链表示为12457，可以切分为124|5|7，第一段和第三段的和能被7整除。她想请你帮她算一算 ，切开后最多能有多少段的数字和能被7整除。

输入描述
一行，一个字符串s，s的每位都是数字。

1 ≤ |s| ≤ 100000，|s| 表示s的长度。

输出描述
输出一个整数，表示切开后最多能有多少段的数字和是7的倍数。

Solution

你做题做多了就能看出来这是一个动态规划问题

假设dp[i] 为 s[:i]可以得到的最大段数

那么dp[i] 最少为dp[i-1]

如果s[i] 为0或7的话，dp[i] = dp[i-1]+1

否则，我们就需要从i-1开始往回找，希望能在不影响之前已经构建好的7的情况下构建出一个7的倍数

因为如果你破坏了之前的一个7，再构建出一个7也没有意义

来谈谈这题为什么卡了我半个多小时，问题就在于输入的每一行最后是会有一个空格的

而我一开始是这样写的 s = [int(x) for x in input()]

所以一直得到（RE）运行时错误，但是我一直以为是其他地方错了(WA)

我一直以为是往回找的时候越界了，调试了好久

最后在输入的那么去掉空格就行了

s = input().strip()
s = [int(x) for x in s]
# print(s)
n = len(s)
dp = [0] * (n + 1)
for i, v in enumerate(s, 1):
    if v == 0 or v == 7:
        dp[i] = dp[i - 1] + 1
        continue
    cnt = v
    for j in range(i - 1, 0, -1):
        if dp[j - 1] != dp[i - 1]:
            break
        cnt = (cnt + s[j - 1]) % 7
        if cnt == 0:
            dp[i] = dp[j - 1] + 1
            break
    dp[i] = max(dp[i], dp[i - 1])
# print(dp)
print(dp[-1])

总结

难度适中，赛码网体验良好，他给出的信息特别全

可以知道是WA，还是TLE，还是AC

当然我之前是一直在lc写代码，所以经常会忘了导包或者没有正确处理输入

第四题也是CE（编译错误）调了好久，后来才发现是忘了导lru_cache包

但归根结底还是我自己对acm模式的不熟练