3.19美团笔试代码记录
考试的时候心态容易崩，甚至不知道自己到底a了几道。。。。
现在静下心来写，每道题都很简单。。。。
第一题满减or折扣，用前缀就可；
第二题加密和解密模拟操作即可；
着重记录一下第三题和第四题吧
第三题：区间覆盖
同门说暴力是可以过的，当时以为过不了，就直接空着没写了555555555
现在补一个o(nlogn)的优化版本吧。思路就是：右端点排序+栈合并区间
n, m1, m2 = map(int, input().split()) machine1l = list(map(int, input().split())) machine1r = list(map(int, input().split())) machine2l = list(map(int, input().split())) machine2r = list(map(int, input().split())) machine1 = list(zip(machine1l, machine1r)) machine2 = list(zip(machine2l, machine2r)) intervals = sorted(machine1 + machine2, key = lambda x: x[1]) ans = 0 stack = [] ## 存放互不相交的区间 for interval in intervals: while stack and interval[0] <= stack[-1][1]: preinterval = stack.pop() ans += preinterval[1] - max(preinterval[0], interval[0]) + 1 interval = [min(preinterval[0], interval[0]), interval[1]] ##区间合并 stack.append(interval) print(ans)
第四题
给定n个元素的集合，从集合中选k个元素求和，使其和能被k1整除，不能被k2整除。（1 <= k <= n） 两种方法，回溯和动规，笔试的时候是用的动规
回溯法：
n ,k1, k2 = map(int, input().split())
nums = list(map(int, input().split()))
global maxsum, cnt
maxsum, cnt = float('-INF'), 0
def traceback(st, sumn, path):
if sumn % k1 == 0 and sumn % k2 != 0:
global maxsum, cnt
if sumn > maxsum:
maxsum = sumn
cnt = 1
elif sumn == maxsum:
cnt += 1
if st >= len(nums):
return
for i in range(st, len(nums)):
traceback(i+1, sumn+nums[i], path+[nums[i]])
traceback(0, 0, [])
print(maxsum, cnt) 动规法：dp[i][j][k] 代表到第i个球为止，选择球使得球之和 对k1余j，对k2余k且球之和最大的可选方案数量；dpsum[i][j][k] 代表到i个球为止，选择球使得球之和 对k1余j，对k2余k的方案中，球之和的最大值。
转移方程算一下就可以出来，
n ,k1, k2 = map(int, input().split())
nums = list(map(int, input().split()))
dp = [[[0]*k2 for _ in range(k1)] for _ in range(n+1)]
dpsum = [[[float('-INF')]*k2 for _ in range(k1)] for _ in range(n+1)]
dp[0][0][0] = 1
dpsum[0][0][0] = 0
for i in range(1, n+1):
num = nums[i-1]
for j in range(k1):
for k in range(k2):
c1, c2 = num%k1, num%k2
x, y = (k1+j-c1)%k1, (k2+k-c2)%k2 ## 计算转移方程
if dpsum[i-1][j][k] > dpsum[i-1][x][y]+num:
dp[i][j][k] = dp[i-1][j][k]
dpsum[i][j][k] = dpsum[i-1][j][k]
elif dpsum[i-1][j][k] < dpsum[i-1][x][y]+num:
dp[i][j][k] = dp[i-1][x][y]
dpsum[i][j][k] = dpsum[i-1][x][y]+num
else:
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][x][y]
dpsum[i][j][k] = dpsum[i-1][j][k]
ans1, ans2 = float('-INF'), 0
ans1 = max(dpsum[n][0][1:])
ans2 = dp[n][0][dpsum[n][0][1:].index(max(dpsum[n][0][1:]))+1]
print(ans1, ans2) 嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤，以后一定计时刷题⏲
查看8道真题和解析