9.10美团笔试
又是凌晨做笔试的一天，心累+1
4个编程。
1. 两个人分别以1/x和1/y的速度从左往右和从右往左工作，规定做到第k个的时候小丽获胜，判断是否获胜输出Tie/Win/Lose
思路：不要用分数去计算，把分数的分母交换一下方便计算，小丽速度为y，另外一个人速度为x，小丽时间为k*y，另外一个人时间为（n-k+1）*x，比较时间长短即可。
def judge(n, k, x, y): s1, s2 = y, x t1, t2 = k * s1, (n - k + 1) * s2 if t1 == t2: return "Tie" elif t1 < t2: return "Win" else: return "Lose" t = int(input()) for i in range(t): n, x, y, k = map(int, input().split()) res = judge(n, k, x, y) print(res)
2. n长度的数组，一次操作为使一个数+1。问最小操作次数，使得数组和不为0，乘积也不为0。
思路：计算一下数组的和与数组中0的个数，分情况讨论。和不为0且没有0的情况下输出0；和为0且没有0的情况下输出1；和不为0但是有0的情况下输出0的个数；和为0但是也有0的情况下也输出0的个数。
可能分情况讨论最后有点问题，过了82%的case
n = int(input().strip()) arr = list(map(int, input().split())) suma = 0 cnt_0 = 0 for num in arr: suma += num if num == 0: cnt_0 += 1 if suma != 0 and cnt_0 == 0: print(0) elif suma == 0 and cnt_0 == 0: print(1) elif suma != 0 and cnt_0 != 0: print(cnt_0) else: print(cnt_0)
3. 完全二叉树的路径上最大值。长度为1至正无穷的结点，然后有n个宝藏，给出了对应结点位置和宝藏价值多少，每次只能从根节点到子节点，求可以获得的最大价值和。
思路：先用一个数组存储每个位置的宝藏价值，在类似于dp一样遍历，每次判断为奇数或者偶数加上根节点的价值，同时记录最大值。
这个不知道什么问题，也是过了82%的case
n = int(input().strip()) p = list(map(int, input().split())) w = list(map(int, input().split())) maxi = max(p) arr = [0]*(maxi+1) res = -1 for i in range(n): ind = p[i] val = w[i] arr[ind] += val for j in range(maxi+1): if j % 2 == 0: prev = arr[j // 2] else: prev = arr[(j - 1) // 2] arr[j] += prev res = max(res, arr[j]) print(res)
4. 给一个长度为n的数组，和一个除数m。每次可以选择数组中的一个数加上10的k次幂再对m取余数，k取0~9。输出数组每个位置的数变成0的最小次数。
思路：首先用一个dic存储了10的所有次幂对m取余数的结果。然后遍历数组，当可以整除的时候对应结果为0，当不能够整除的时候需要计算m-这个数的差可以被dic中的余数加起来的次数。
这里我写了一个find函数去计算次数，但是细节有问题，导致用例没有过。
def find(dic, num):
res = -1
values = dic.values()
for v in values:
if v == 0:
continue
elif v == num:
return 1
elif num % v == 0:
res = max(res,v)
else:
continue
return num//res
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dic = {}
for j in range(10):
dic[j] = pow(10, j) % m
nums = [0] * n
for i in range(n):
val = arr[i] % m
if val == 0:
nums[i] = 0
else:
dif = m - val
print(dif)
times = find(dic, dif)
nums[i] = times
print(" ".join(nums)) 选择：HDFS，attention,，数据转换
，是要切换模式吗？？
