2020.08.02 拼多多笔试AC3 py题解

第一题

需要特判第N步时候k=0

if __name__=='__main__':
    k, n = map(int, input().split())
    nums = list(map(int, input().split()))
    cnt = 0
    if k == 0:
        print('paradox')
    else:
        i = 0
        for num in nums:
            i += 1
            if k > num:
                k -= num
            elif k == num:
                k -= num
                break
            else:
                k = num - k
                cnt += 1
        if k == 0 and i < n:
            print('paradox')
        else:
            print("{} {}".format(k, cnt))

第二题

把所有骰子转到1到上面,然后第二小的元素或者第三小的元素(第二小的元素在下面)转到前面:

from collections import defaultdict

if __name__ == '__main__':
    m = int(input())
    counter = defaultdict(int)
    u, d, l, r, f, b = 0, 1, 2, 3, 4, 5
    for _ in range(m):
        nums = list(map(int, input().split()))
        for idx, val in enumerate(nums):
            if val == 1:
                if idx == u:
                    break
                elif idx == d:
                    nums[u], nums[d] = nums[d], nums[u]
                    nums[f], nums[b] = nums[b], nums[f]
                elif idx == l:
                    nums[u], nums[r], nums[d], nums[l] = nums[l], nums[u], nums[r], nums[d]
                elif idx == r:
                    nums[u], nums[l], nums[d], nums[r] = nums[r], nums[u], nums[l], nums[d]
                elif idx == f:
                    nums[u], nums[b], nums[d], nums[f] = nums[f], nums[u], nums[b], nums[d]
                elif idx == b:
                    nums[u], nums[f], nums[d], nums[b] = nums[b], nums[u], nums[f], nums[d]
                break
        num2f = nums[u] + 1
        if num2f == nums[d]:
            num2f += 1
        for idx, val in enumerate(nums):
            if val == num2f:
                if idx == f:
                    break
                elif idx == b:
                    nums[f], nums[b] = nums[b], nums[f]
                    nums[l], nums[r] = nums[r], nums[l]
                elif idx == l:
                    nums[f], nums[r], nums[b], nums[l] = nums[l], nums[f], nums[r], nums[b]
                elif idx == r:
                    nums[f], nums[l], nums[b], nums[r] = nums[r], nums[f], nums[l], nums[b]
        counter[tuple(nums)] += 1
    ret = [v for k, v in counter.items()]
    ret.sort(reverse=True)
    print(len(ret))
    for v in ret:
        print(v, end= ' ')

第三题

Pyhton按照美味程度排序,然后删去一些用不到的元素:例如[热量, 美味度], [2, 5], [1, 10] 显然后者美味度高且热量小,直接把前者删掉就可以了。我感觉是暴力,Python可以过

from collections import defaultdict

if __name__ == '__main__':
    n, m, t = map(int, input().split())

    lunch = []
    dinner = []
    for _ in range(n):
        # 热量 美味值
        lunch.append(list(map(int, input().split())))
    for _ in range(m):
        dinner.append(list(map(int, input().split())))
    if t == 0:
        print(0)
    else:
        lunch.sort(key=lambda x: x[1])
        dinner.sort(key=lambda x: x[1])
        ll = []
        dd = []
        for idx, val in enumerate(lunch):
            while ll and val[0] <= ll[-1][0]:
                ll.pop()
            if ll and val[1] == ll[-1][1]:
                continue
            ll.append(val)

        for idx, val in enumerate(dinner):
            while dd and val[0] <= dd[-1][0]:
                dd.pop()
            if dd and val[1] == dd[-1][1]:
                continue
            dd.append(val)

        ret = float('inf')
        for val in ll:
            if val[1] >= t:
                ret = min(ret, val[0])
                break
        for val in dd:
            if val[1] >= t:
                ret = min(ret, val[0])
        for idx, val in enumerate(ll):
            if val[1] >= t:
                break
            for idx, d in enumerate(dd):
                if d[1] + val[1] >= t:
                    ret = min(ret, d[0] + val[0])
                    break
        if ret == float('inf'):
            print(-1)
        else:
            print(ret)

第四题不会,感觉是状压DP但是推不出来。另外想问下算法岗今年这么激烈么,简历挂到怀疑人生,面试机会都没有…

#笔试题目##拼多多#
全部评论
dp写不出来,写个DFS呗
点赞 回复
分享
发布于 2020-08-03 09:31
第四题就是插头dp。
点赞 回复
分享
发布于 2020-08-03 21:02
乐元素
校招火热招聘中
官网直投
第三题的分组背包有ac的吗?
点赞 回复
分享
发布于 2020-08-04 20:28

相关推荐

1 8 评论
分享
牛客网
牛客企业服务