1. 缓存转发数据包统计
题目描述
数据包转发线路结构：
- $k$ 个节点组成的队列
-
每个节点转发能力为 $m$，缓存能力为 $n$
- 节点可能由于故障直接跳过，但不会有两个连续故障节点
两轮操作：
- 向此队列发送 $a$ 个数据包让其转发；
- 继续转发之前缓存的数据包（如果第二轮仍有数据包缓存则丢弃)。
问题：
- 两轮操作后可能收到的最少数据包总数（如果第二轮仍有数据包缓存则丢弃)
- $1 <= k <= 40 \; ;\quad 1 <= m,n <= 1000 \; ;\quad 1 <= a <= 1000$
输入描述：
- 第 1 行：队列长度 $k$
- 第 2 行：$k$ 个节点转发能力数组，以空格分隔；每个节点的转发能力和缓存能力 $m,n$ 以逗号分隔
- 第 3 行：数据包个数 $a$
解题思路
总体就是用 dp 表储存到达某个节点处两次传递的状态：
- 第一次的传递数量
- 第二次的传递数量
dp[i] 表示 [第一次传递时从节点i发送的包数量, 第二次传递时从i发送的包数量]，初始发送的数据包数量 $a$ 可以视为来自 0 号节点（$m_0 = \infty, n_0=0$），即 dp[0]=[a, 0]。
由于节点可能发生故障导致被跳过，并且不存在连续两个节点故障，因此节点 $i$ 收到的数据包可能来自：
- 节点 $i-1$
- 或者节点 $i-2$（即节点 $i-1$ 坏掉了）
因此，我们可以取上面两种情况中使得节点 $i$ 能够传递的数据包总数最少的那种情况作为 $i$ 的状态。
然后就是理清楚如何从 $i-1$ 或者 $i-2$ 的状态得到 $i$（通过 cal() 函数完成）。
只需要一次遍历，最后输出第 $k-1$ 和第 $k$ 个节点中转发包总数较小的那个即可（因为可能存在最后一个节点 $k$ 出现故障的情况）。
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
# 从控制台读取输入数据
k = int(input()) # 节点数k
nodes = [[int(w) for w in s.split(',')] for s in input().split(' ')] # 各节点的转发能力m和缓存能力n
a = int(input()) # 初始发包总数a
# 动态规划主函数
def main(k, nodes, a):
"""
k: int, 节点数
nodes: list, 各节点的转发能力m和缓存能力n
a: int, 初始发包总数
return: int, 两轮操作后可能收到的最少数据包总数
"""
if k < 1:
return a
dp = [[a, 0]] # 初始化dp表，将初始数据包来源视为0号节点，初始发包数量为a
dp.append(cal(dp[0], nodes[0])) # 通过dp[0]计算dp[1]
for i in range(2, k + 1):
res1 = cal(dp[i-1], nodes[i-1]) # 情况1：节点i接收的数据包来自节点i-1（节点i-1正常工作）
res2 = cal(dp[i-2], nodes[i-1]) # 情况2：节点i接收的数据包来自节点i-2（节点i-1出现故障）
if res1[0] + res1[1] <= res2[0] + res2[1]: # 状态转移，选择当前节点转发包总数最少的情况
dp.append(res1)
else:
dp.append(res2)
return min(dp[k][0] + dp[k][1], dp[k-1][0] + dp[k-1][1]) # 比较最后两个节点发包总数（最后一个节点可能出现故障）
# 通过dp[i-1]或者dp[i-2]的状态来计算dp[i]的可能值
def cal(pre, cap):
"""
pre: list, 第i-1或者i-2个节点处两次传递发出的数量, 即 [第一次发包数，第二次发包数]
cap: list, 节点i的传输能力，即 [节点i的转发能力，节点i的缓存能力]
return: list, 节点i两轮操作发送的包数量，即 [节点i第一轮发包数量，节点i第二轮发包数量]
"""
send1 = min(pre[0], cap[0]) #第一次传递时从i发送的包数量
send2 = min(max(pre[0] - cap[0], 0) + pre[1], cap[1] + pre[1], cap[0]) #第二次传递时从i发送的包数量
return [send1, send2] # 返回节点i两轮的发包数量
print(main(k, nodes, a))
2. 查找知识图谱中的实例知识
题目描述
知识图谱中存在的关系：
- 概念：包括父概念及其子概念，通过
subClassOf关系关联，父子概念可以有多个层级 - 实例：仅和概念之间通过
instanceOf关系关联 - 关系：以三元组的形式表示，三元组是一个以空格为成员间分隔符的字符串。例如：
student subClassOf person表示student是person的子概念apple instanceOf fruit表示apple是概念fruit的实例
给定的图谱满足以下限制：
- 有向图中不存在环路
- 所有点和关系的定义对大小写敏感
问题：
- 给定一个知识图谱，编写一个方法，根据一个概念查找其所有的实例
- 如果一个概念拥有子概念，那么返回的结果需要包含其所有子概念的实例
- 输出结果中的字符串按照字典升序排列
- 如果输入的概念没有实例，则返回字符串
"empty"
输入描述：
- 第 1 行：图谱中关系的数量 $n$，其中 $1 \le n \le 10000$
- 第 2 到 $n+1$ 行：图谱中的关系，每一行是一个关系三元组
(entity1, relationship, entity2) - 第 $n+2$ 行：待查找的元节点，即目标概念
解题思路
递归查找：
- 遇到目标概念的实例就添加进结果集
- 否则就将其子概念视为新的目标概念，递归调用函数查找其对应的实例
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
# 从控制台读取输入数据
n = int(input()) # 图谱中的关系数n
relations = [input().split() for i in range(n)] # 图谱中的各关系三元组
k = input() # 目标概念
res = set() # 结果集合
# 递归函数，获取目标概念（及其子概念）的所有实例
def get_ins(n, k, relations):
"""
n: int, 图谱中的关系数
k: str, 目标概念
relations: list, 图谱中各关系三元组构成的列表
"""
for i in range(n):
if relations[i][2] == k: # 查找目标概念对应的子概念或实例
if relations[i][1] == 'instanceOf': # 如果是目标概念的实例，则加入结果集合中
res.add(relations[i][0])
else: # 如果是目标概念的子概念，则将子概念视为新的目标概念，递归调用该函数查找其对应的实例
new_k = relations[i][0]
get_ins(n, new_k, relations)
get_ins(n, k, relations)
print(' '.join(sorted(list(res)))) # 排序后打印结果
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！