前言

题目难度中等，但是总体不比国内简单。

开电动汽车回家过年

题目描述

新年即将来临，小明计划开新买的电动汽车回老家过年。

已知小明的工作地在上海，老家在中部某城市A。上海到城市A的距离是L公里(1<=L≤100000)。

小明的电动汽车的电池航程是P，电池最大电量也是P(假设电动汽车行使一公里需要消耗1度电。(1<=P<=100))。如果电动车在中途电量耗尽了，将无法继续强行，也就无法到达目的地了。

已知小明出发前已经把电池充满了。途中依次经过N(1<=N<10000)个充电站。第i个充电站距离城市A有 Ai公里，最大可充电 Bi度。

请问，小明能不能顺利地回老家过年?如果可以，请输出最少需要充电多少次;如果不可以，请输出-1。

解答要求

时间限制: C/C++ 1000ms, 其他语言: 2000ms内存限制: C/C++ 256MB,其他语言: 512MB

输入

输入的第一行为数字N。

接下来的N行，每行包含2个数并用空格隔开: Ai Bi

最后一行包括两个数LP，并用空格隔开。

输出

按照题目要求输出最少次数或者-1。

样例1

输入:4
     4 4
     5 5
     11 6
     15 8
     25 10
输出:3
解释:小明出发时电池电量是10，距离城市A 25公里。
行驶10公里后，到达距离城市A 15公里的充电站，充点前电池电量为0，充电8度之后，再出发。
行驶4公里后，到达距离城市A11公里的充电站，充电前电池电量为4。充电6度之后，再出发。
行驶6公里后，到达距离城市A 5公里的充电站，充电前电池电量为4，充电1度之后，再出发。
之后，可以直接开到城市A
一共需要充电3次才能到达城市A。

思路与代码

动态规划。

此处使用记忆化搜索来进行实现。f[i, j]表示从第i个充电桩，剩余电量为j的时候，走到终点的最小充电次数。

f[i, j] = min(f[i+1,j-diff],  f[i+1, j+B[i] - diff] + 1) //充电和不充电

from functools import cache
from math import inf

N = int(input())

stations = []
for _ in range(N):
    stations.append([int(c) for c in input().split()])

stations.sort(key=lambda x:x[0])
stations = [[0,0]] + stations

L,P = map(int, input().split())

def solve():
    for i, station in enumerate(stations):
        if i > 0 and stations[i][0] - stations[i-1][0] > P:
            return -1

    @cache
    def dfs(i, j):
        if i == N:
            diff = L - stations[-1][0]
            if j >= diff: return 0
            if j + stations[-1][1] >= diff: return 1
            return inf
        diff = stations[i+1][0] - stations[i][0]
        ans = inf
        if j >= diff:
            ans = min(ans, dfs(i+1,j-diff)) #不充电

        if j + stations[i][1] >= diff:
            curP = min(j + stations[i][1], P) #防止充爆
            ans = min(ans, dfs(i+1, curP - diff) + 1)
        return ans

    ans = dfs(0, P)
    if ans == inf: return -1
    return ans


print(solve())

查询节点路径

1.树的节点有三个属性:节点名称、节点ID，节点的父级节点ID

2.同一个父级节点下的所有子节点名称不会重复，但节点名称在全局可能重复。节点名称中不包含 / 字符

3.节点的id全局唯一

4.如果节点是树的根节点，则其父级节点1D的约定为-1

5.可以使用节点路径唯一标识一个节点在树中的位置。节点路径生成方式是:从树的根节点开始，找出到目标节点所经过的所有节点，然后将这些节点名称、用/字符分隔拼接而成。

请实现树的节点查询功能:根据指定节点名称，返回查询出的所有节点路径。

解答要求

时间限制: C/C++1000ms,其他语言: 2000ms内存限制: C/C++ 256MB,其他语言:512MB

输入

标准IO输入。

第一行为要查询的节点名称。

第二行为节点名称序列，名称间使用逗号分隔。序列的序号即为节点id，序号从0开始。节点总数小于1024。

第三行为每个节点的父级节点的id。根节点的父级id约定为:-1

输出

返回搜索到的所有节点的路径。

如果查询出多条路径，则按照路径的字典序从小到大排序后输出，逗号分隔。

如果搜索结果为空，则输出 null。

样例1

输入:c
     a,b,c,d,c
     -1,0,1,0,3
输出: /a/b/c,/a/d/c

思路与代码

dfs+回溯。

总体来说就是先建树， 然后树上找路径。

from collections import defaultdict

target = input()
names = [c for c in input().split(",")]
pids = [int(c) for c in input().split(",")]

graph = defaultdict(list)

root = -1

for i,pid in enumerate(pids):
    if pid == -1: root = i
    else:
        graph[i].append(pid)
        graph[pid].append(i)

res = []
path = []
def dfs(node, pre):
    path.append(names[node])
    if names[node] == target:
        res.append(list(path))
    for next in graph[node]:
        if next != pre:
            dfs(next, node)
    path.pop()

dfs(root, -1)
res.sort()
ans = []
for r in res:
    ans.append("/"+'/'.join(r))

print(','.join(ans))

PCB印刷电路板布线

在PCB印剧电路板设计中，器件之间的连线需要避免线路的用抗值增大，而且器件之间还有别的器件和别的干扰源，在布线时我们希望爱到的干扰尽量小。

现将电路板简化成一个M*N的矩阵，每个位置(单元格) 的值表示其源干扰度。

如果单元格的值为0，表示此位置没有干扰源;如果单元格的值为非0，则表示此位置是干扰源，其值为源干扰度。

连线经过干扰源或千扰源附近会增加连线的总干扰度。

位置A[x,y]的干扰源的源干扰度为d(d>0)，则连线的干扰度计算如下

1、若连线经过位置A[x,y]，则其总干扰度会增加d;

2、若连线经过离位置A[x,y]距离小于d的位置时，设其距离为k，则总干扰度会增加(d-k);

3、若连线经过离位置A[x,y]距离大于或等于d的位置时，总干扰度不会增加；

注:位置[x1,y1]和位置[x2,y2]之间距离的定义为:|x1-x2| + |y1-y2|。

如下3x3矩阵，位置[1,1]的源干扰度是2，连线的位置序列为:[0,0]->[0,1]->[0,2]->[1,2]>[2.2]。

其中[0,1]和[1,0]到干扰源的距离为1，会叠加1的干扰度;其他位置到[1,1]的距离均大于等于2，所以不会叠加干扰度。

因此这条连线的总干扰度为2。

现在我们需要将左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的[0,0]和右下角的[M-1,N-1]。由于我们希望连线尽量地短，从位置[0,0]到[M-1,N-1]的连线途中，我们规定连线只能向下或向右。

请根据输入 (MxN的矩阵)，计算出连线的最小干扰度。

样例

输入：4
     4 4
     5 5
     11 6
     15 8
     25 10
输出：3

思路与代码

动态规划。

1. 首先计算出所有节点的干扰值
2. 动态规划计算走到终点的最小干扰值。 f[i,j] = min(f[i-1,j], f[i,j-1]) + dis[i,j]

from collections import deque
from math import inf

m,n = map(int, input().split())
matrix = []

for _ in range(m):
    matrix.append([int(c) for c in input().split()])

dis = [[0]*n for _ in range(m)]

def ranse(i,j):
    vst = [[False]*n for _ in range(m)]
    q = deque()
    q.append((i,j,matrix[i][j]))
    vst[i][j] = True
    while q:
        i,j,g = q.popleft()
        if g == 0: continue
        dis[i][j] += g
        for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if ni<0 or nj<0 or ni>=m or nj>=n or vst[ni][nj]: continue
            vst[ni][nj] = True
            q.append((ni,nj,g-1))

q = deque()
for i in range(m):
    for j in range(n):
        if matrix[i][j] != 0:
            ranse(i,j)

dp = {}
def dfs(i,j):
    if i >= m or j >= n: return inf
    if i == m-1 and j == n-1: return dis[-1][-1]
    if (i,j) in dp:
        return dp[(i, j)]
    dp[(i,j)] = min(dfs(i+1,j),dfs(i,j+1)) + dis[i][j]
    return dp[(i,j)]

print(dfs(0,0))