前言

今年美团最多可以参加三次笔试，三次取最佳成绩。可以做下参考下难度。

第三题，当时脑子坏了，没做出来…
然后第二题我用的两个for，超时了…
最后做了2.5道题，看来是无了…

这周六继续申请第二次笔试

Q1、烤串

问题类型：其实就是类似两个数组排序，属于送分题

题目描述：
小团想要自己来烤串！不过在烤串之前，需要串好烤串。小团有n个荤菜和n个素菜，他想按顺序分别一个荤菜一个素菜串起来，想请你帮他串好！
给出两个长度分别为n的仅包含小写英文字母的串A和B，分别代表荤菜和素菜的种类（用字母来表示菜的种类）。请你以从左到右的顺序依次串好他们！例如对于荤菜串A1、A2…An
和素菜串B1、B2…Bn，串好应该是A1、B1、A2、B2…An、Bn

输入：

1. 第一行一个正整数n，表示烤串长度
2. 第二行为一个长度为n的字符串A，表示荤菜按次序都是哪些菜
3. 第三行为一个长度为n的字符串B，表示素菜按次序都是哪些菜
4. 对于80%的数据，n≤1000，对于20%的数据，n≤50000，对于所有数据，A和B为仅包含小写英文字母的字符串

输出：输出一行，包含2n个字符串表示串好的烤串

def solver(A, B, m, n):
    res = ['a' for _ in range(m+n)]
    while m or n:
        res[m+n-1] = B[n-1]
        n -= 1
        res[m+n-1] = A[m-1]
        m -= 1
    return res

if __name__ == '__main__':
    n = int(input())
    A = list(map(str, input()))
    B = list(map(str, input()))
    res = solver(A, B, n, n)
    print(''.join(res))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Q2、曼哈顿距离定位

问题类型：其实就是正常的遍历，但是如果直接两层for循环，50000x50000必会超时，所以要想办法把时间复杂度降到O(n)，想办法用空间换时间：可以把abs(y1 - i)存储起来

这道题，如果直接两层for循环求三个集合的交集，必会超时；

题目描述：
小团在地图上放了三个定位装置，想依赖他们来进行定位！
小团的地图是一个n×n的一个棋盘，他在(x1,y1),(x2,y2),(x3,y3) xi,yi ∈ Z ∩ [1,n] 这三个位置分别放置了一个定位装置（两两不重叠）；
然后小团在一个特定的位置(a,b)a,b ∈ Z ∩ [1,n]放置了一个信标。每个信标会告诉小团它自身到那个信标的曼哈顿距离，即对i=1,2,3 小团知道(|xi-a|+|yi-b|)；
现在小团想让你帮他找出信标的位置！注意，题目保证最少有一个正确的信标位置；
因为小团不能定位装置确定出来的信标位置是否唯一，如果有多个，输出字典序最小的那个。(a,b)的字典序比(c,d)小，当且仅当 a

输入：

1. 第一行一个正整数n，表示棋盘大小
2. 第二行两个整数，分别表示x1与y1，即第一个定位器的位置
3. 第三行两个整数，分别表示x2与y2，即第二个定位器的位置
4. 第四行两个整数，分别表示x3与y3，即第三个定位器的位置
5. 第五行三个整数，分别表示第一、二、三个定位器到信标的曼哈顿距离。第i个定位器到信标的曼哈顿距离即(|xi-a|+|yi-b|)
6. 数字间两两有空格隔开，对于所有数据， n≤50000, 1≤xi,yi≤n

输出：两个整数 代表信标的位置

if __name__ == '__main__':
    n = int(input())                    # 棋盘nxn
    x1, y1 = map(int, input().split())  # 第一个定位器的位置
    x2, y2 = map(int, input().split())  # 第二个定位器的位置
    x3, y3 = map(int, input().split())  # 第三个定位器的位置
    z1, z2, z3 = map(int, input().split())  # 信标距定位器1、定位器2、定位器3的距离

    # 分别记录三个定位器各种满足的位置
    mapp1, mapp2, mapp3 = dict(), dict(), dict()
    for i in range(1, n+1):
        # 用数学表达式来代替第二个for循环
        temp1 = abs(x1 - i)
        if z1 - temp1 >= 0:
            temp2 = y1 - (z1 - temp1)
            if temp2 >= 1:
                mapp1[(i, temp2)] = 1
            temp2 = y1 + (z1 - temp1)
            if temp2 <= n:
                mapp1[(i, temp2)] = 1

        temp1 = abs(x2 - i)
        if z2 - temp1 >= 0:
            temp2 = y2 - (z2 - temp1)
            if temp2 >= 1:
                mapp2[(i, temp2)] = 1
            temp2 = y2 + (z2 - temp1)
            if temp2 <= n:
                mapp2[(i, temp2)] = 1

        temp1 = abs(x3 - i)
        if z3 - temp1 >= 0:
            temp2 = y3 - (z3 - temp1)
            if temp2 >= 1:
                mapp3[(i, temp2)] = 1
            temp2 = y3 + (z3 - temp1)
            if temp2 <= n:
                mapp3[(i, temp2)] = 1
    common = dict(mapp1.items() & mapp2.items() & mapp3.items())
    res = []
    for key, val in common.items():
        res.append(key)
    x, y = res[0]
    print(x, y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

Q3、复习题目

问题类型：贪心

问题描述：
期中考试，有n道题，对于第i道题，有pi的几率做对，获得ai的分值，还有(1-pi)的概率做错，得0分。总分是每道题获得的分数之和。因为时间有限，最多复习m道题，复习后的试题正确率为100%。如果以最佳方式复习，能获得期望最大总分是多少？

输入描述：

1. 第一行两个正整数n和m，表示总试题数和最多复习试题数；
2. 第二行n个整数，分别为p1 p2…pn，表示小美有pi%的概率，即pi=pi/100的概率做对第i个题；
3. 第三行n个整数，分别表示a1 a2…an，分别表示第 i 个题做对的分值；
4. 数字间两两有空格隔开，对于所有数据，1≤m≤n≤50000,0≤pi≤100,1≤ai≤1000

if __name__ == '__main__':
    n, m = map(int, input().strip().split())
    P = list(map(int, input().strip().split()))
    scores = list(map(int, input().strip().split()))

    res = 0
    mapp = []
    for i in range(len(P)):
        # mapp[i][0] 这道题100%做错会丢掉多少分
        # mapp[i][1] 这道题100%做对会得到多少分
        mapp.append([(1-P[i])/100 * scores[i], scores[i]])
    # 按照做错的时候丢分大小进行降序排序
    mapp.sort(key=lambda x: x[0], reverse=True)

    for j in range(len(P)):
        if j < m:  # 复习前面丢分多 100%会做这些题 拿到全部的分
            res += mapp[i][1]
        else:     # 丢分不多的就拿正常的分
            res += mapp[i][1] - mapp[i][0]
            
    print('%.2f'%res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Q4、两个数列相同的最少代价

经典DP：类似编辑距离

问题描述：
小团生日收到妈妈送的两个一模一样的数列作为礼物！他很开心的把玩，不过不小心没拿稳将数列摔坏了！
现在他手上的两个数列分别为A和B，长度分别为n和m。小团很想再次让这两个数列变得一样。他现在能做两种操作：
操作一是将一个选定数列中的某一个数a改成数b，这会花费|b-a|的时间；
操作二是选择一个数列中某个数a，将它从数列中丢掉，花费|a|的时间；
小团想知道，他最少能以多少时间将这两个数列变得再次相同！

输入：

1. 第一行两个空格隔开的正整数n和m，分别表示数列A和B的长度
2. 第二行n个整数，分别为A1 A2…An
3. 第三行m个整数，分别为B1 B2…Bm
4. 对于所有数据，1≤n,m≤2000， |Ai|,|Bi|≤10000

输出：输出一行一个整数，表示最少花费时间，来使得两个数列相同

这道题用DP也会超时，拿不到满分

if __name__ == '__main__':
    n, m = map(int, input().split())
    A = list(map(int, input().split()))  # n
    B = list(map(int, input().split()))  # m

    dp = [[float('inf')for _ in range(m+1)]for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        dp[i][0] = abs(A[i-1]) + dp[i-1][0]
    for j in range(1, m+1):
        dp[0][j] = abs(B[j-1]) + dp[0][j-1]

    for i in range(1, n+1):
        for j in range(1, m+1):
            if A[i-1] != B[j-1]:
                v1 = dp[i-1][j] + abs(A[i-1])  # 删除A[i-1]
                v2 = dp[i][j-1] + abs(B[j-1])  # 删除B[j-1]
                v3 = dp[i-1][j-1] + abs(A[i-1]- B[j-1])  # 把A[i-1]变成B[j-1]
                dp[i-1][j-1] = min(v1, v2, v3)
            else:
                dp[i][j] = dp[i-1][j-1]
    print(dp[-1][-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22