美团算法综合8.15：1，0.5，1，0.18
四道题目分别是1,0.5,1,0.18，求解2,4解顺便贴出自己的代码。
1，四倍回文，如果一个数字的四倍和自己的回文相同那就是我们要找的回文，求1~n范围有多少这样的回文，数据是10^7除4之后是10^6，直接暴力。
def f1(n): r = [] c = n // 4 for i in range(1, c + 1): if str(4*i) == str(i)[::-1]: r.append(i) return r while True: try: n = int(input()) r = f(n) print(len(r)) for i in r: print(str(i), ' ', str(i)[::-1]) except: break
2，给一个车票记录的列表，列表的每个元素是做过的一趟车的起点和终点，如果一次出行完整的从车票起点走到了终点那就算做一次旅行，求总共有多少次旅行，0.55渣渣求解答
0.55的渣渣明白了，如果一趟旅行的起点和终点是一样的那也算一次旅行，就是坐车从北京到北京也算，原地TP。。。 def f2(ts): if len(ts) == 1: u, v = ts[0][0], ts[0][1] if u == v: return 1 elif u != v: return 0 res = 0 curr, last = '', '' for t in ts: u, v = t if curr == '' and last == '': curr, last = u, v elif curr == v and last == u: res += 1 curr, last = '', '' elif last == u and curr != v: last = v return res while True: try: n = int(input()) ts = [] for _ in range(n): temp = input().split() ts.append(temp) print(f(ts)) except: break
3，并查集解决，模板直接套，具体题目的描述记不清了，反正只要熟练掌握并查集就可以做。
import collections
def f3(hs, n):
roots = {}
res = collections.defaultdict(set)
def findroot(node):
nonlocal roots
if node not in roots:
roots[node] = node
elif roots[roots[node]] != roots[node]:
roots[node] = findroot(roots[node])
return roots[node]
for h in hs:
u, v = h
if u not in roots:
roots[u] = findroot(v)
elif v not in roots:
roots[v] = findroot(u)
else:
roots[findroot(u)] = findroot(v)
for i in range(1, n + 1):
curr = findroot(i)
res[curr].add(i)
ks = []
for k in res:
ks.append(sorted(res[k]))
ks.sort(key = lambda k: k[0])
return ks
while True:
try:
n, m = list(map(int, input().split()))
hs = []
for _ in range(m):
temp = list(map(int, input().split()))
hs.append(temp)
ks = f(hs, n)
print(len(ks))
for k in ks:
print(' '.join(map(str, k)))
except:
break 4，最后一道也是最难的一题，有n辆车和ab两个城市，a、b两个城市分别需要a、b辆车（a + b < n）,然后给出n辆车每辆去往a城市或者b城市的收益，求合满足ab城市调度需求下能得到的最大收益，想的是通过dp（i，j，k）代表k辆车已经使用同时ab两地分别已经有i、j辆车的情况下得到的最大收益，但是三维动态规划没法得到解，求指点：
def f4(ps, a, b, n): dp = [[[0] * (n + 1) for _ in range(b + 1)] for _ in range(a + 1)] for i in range(a): for j in range(b): for k in range(n): if i == a: dp[i + 1][j + 1][k + 1] = max(dp[i + 1][j][k] + ps[k][1], dp[i][j][k]) if j == b: dp[i + 1][j + 1][k + 1] = max(dp[i][j + 1][k] + ps[k][0], dp[i][j][k]) else: dp[i + 1][j + 1][k + 1] = max(dp[i][j][k],dp[i][j + 1][k] + ps[k][0], dp[i + 1][j][k] + ps[k][1]) print(dp) return dp[-1][-1][-1]情急之下直接深搜一波，加上lru缓存过了0.18，估计是11个测试用例的2个吧
import functools
def f(ps, a, b, n):
res = 0
@functools.lru_cache def dfs(i, j, tmp, cur):
nonlocal res, ps
if i == 0 and j == 0:
res = max(res, tmp)
return
if cur == len(ps):
return
if i == 0:
dfs(i, j - 1, tmp + ps[cur][1], cur + 1)
dfs(i, j, tmp, cur + 1)
if j == 0:
dfs(i - 1, j, tmp + ps[cur][0], cur + 1)
dfs(i, j, tmp, cur + 1)
else:
dfs(i - 1, j, tmp + ps[cur][0], cur + 1)
dfs(i, j - 1, tmp + ps[cur][1], cur + 1)
dfs(i, j, tmp, cur + 1)
dfs(a, b, 0, 0)
return res 2,4求解答！！！
