美团算法综合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求解答！！！

#美团笔试##笔试题目##美团#