第一题证明一下排序后最后位置最小就行，第二题用个defaultdict存就行，第三题check二分从最大最小开始搜不同的位置，然后每个候选x去判断就行。其他都比较简单，就记录一下第四题吧小红拿到了一个n阶正方形矩阵{aij}，他准备从左上角走到右下角，每一步可以向右或向下走一格，向知道有多少种不同路径满足路径元素和恰好为x。0<x,aij<10^91<n<18注解：dp肯定能想到，首先必须用稀疏方式存储路径值，不然开三维数组内存爆炸时间太长。其次如果不剪枝只能过一半，剪枝两种方法，一种如果当前值已经超了，就不计算路径数量了；另一种计算当前位置到终点的最大路径，如果当前值加上最大路径还是不够，直接剪掉。from collections import defaultdictn,x = map(int,input().split())mat = []for i in range(n):    mat.append(list(map(int,input().split())))dp = [[defaultdict(int) for _ in range(n)] for __ in range(n)]dp[0][0][mat[0][0]] = 1leng = [[0 for _ in range(n)] for __ in range(n)]leng[-1][-1] = mat[-1][-1]for i in range(n-1,-1,-1):    for j in range(n-1,-1,-1):        if i == n - 1 and j == n - 1:            continue        if i == n - 1:            leng[i][j] = leng[i][j+1] + mat[i][j]        elif j == n - 1:            leng[i][j] = leng[i+1][j] + mat[i][j]        else:            leng[i][j] = max(leng[i][j+1],leng[i+1][j]) + mat[i][j]for i in range(n):    for j in range(n):        if i > 0:            for key,value in dp[i-1][j].items():                if key + mat[i][j] > x or key + leng[i][j] < x:                    continue                dp[i][j][key + mat[i][j]] += value        if j > 0:            for key,value in dp[i][j-1].items():                if key + mat[i][j] > x or key + leng[i][j] < x:                    continue                dp[i][j][key + mat[i][j]] += valueprint(dp[-1][-1][x])