how to

读取奶牛数量

Nov 9, 2024
notesjulyfun工作william241109
8 Minutes
1456 Words

P3416 [USACO16DEC] Moocast S

https://usaco.org/index.php?page=viewproblem2&cpid=668

约翰农场主的 $N$ 头奶牛需要建立一个广播系统，每头奶牛有一个对讲机，具有一定的传输半径 $P$。一头奶牛可以通过直接或中继的方式，将信息传递给其他奶牛。目标是找到从某头奶牛开始广播时，能够到达的奶牛的最大数量。

算法分析

  1. 图的构建：

    • 每头奶牛看作一个节点。
    • 如果奶牛 $i$ 的对讲机能直接覆盖奶牛 $j$，则在图中从 $i$ 到 $j$ 添加一条有向边。

  2. 广度优先搜索 (BFS)：

    • 从每个节点开始，使用 BFS 遍历可达的所有节点。
    • 记录从某个节点开始可以到达的最大节点数。

代码注释

1
# 读取奶牛数量
2
n = int(input())
3


4
# 初始化邻接表，用于存储每头奶牛可以直接发送信息到达的奶牛
5
e = [[] for _ in range(n)]
6


7
# 初始化位置和能量列表
8
pos, p = [], []
9


10
# 读取每头奶牛的位置和能量
11
for _ in range(n):
12
    x1, y1, p1 = map(int, input().split())
13
    pos.append((x1, y1))
14
    p.append(p1)
15


40 collapsed lines
16
# 计算两头奶牛之间的距离平方
17
def dis(a, b):
18
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
19


20
# 构建图，确定每头奶牛可以直接向哪些奶牛发送信息
21
for i in range(n):
22
    for j in range(n):
23
        if i == j: continue  # 跳过自己
24
        # 如果奶牛 j 在奶牛 i 的传输范围内，则添加到邻接表
25
        if dis(pos[i], pos[j]) <= p[i] ** 2:
26
            e[i].append(j)
27


28
from collections import deque
29


30
# 初始化最大可到达奶牛数量
31
ans = 0
32


33
# 对每头奶牛执行广度优先搜索（BFS）
34
for i in range(n):
35
    # 用于记录访问过的奶牛
36
    vis = [False] * n
37
    # 创建队列进行 BFS
38
    q = deque()
39
    q.append(i)
40
    tot = 0
41
    vis[i] = True
42
    while len(q) > 0:
43
        tot += 1
44
        u = q.popleft()
45
        # 遍历当前奶牛可以直接到达的奶牛
46
        for v in e[u]:
47
            if not vis[v]:  # 如果奶牛 v 未访问过
48
                q.append(v)
49
                vis[v] = True
50
    # 更新最大可到达奶牛数量
51
    if tot > ans:
52
        ans = tot
53


54
# 输出最大可到达奶牛数量
55
print(ans)

程序填空版

1
n = int(input())
2
e = [[] for _ in range(n)]
3
pos, p = [], []
4


5
for _ in range(n):
6
    x1, y1, p1 = map(int, input().split())
7
    pos.append((x1, y1))
8
    p.append(p1)
9


10
def dis(a, b):
11
    # 计算两头奶牛之间的距离平方
12
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
13


14
for i in range(n):
15
    for j in range(n):
32 collapsed lines
16
        if i == j: continue
17
        # 如果奶牛 j 在奶牛 i 的传输范围内，则添加到邻接表
18
        if dis(pos[i], pos[j]) <= ________:
19
            e[i].append(j)
20


21
from collections import ________
22
ans = 0
23


24
for i in range(n):
25
    # 用于记录访问过的奶牛
26
    vis = [False] * n
27
    # 创建队列进行 BFS
28
    q = deque()
29
    q.append(i)
30
    tot = 0
31
    vis[i] = ________
32


33
    while len(q) > 0:
34
        tot += 1
35
        u = q.________()
36
        # 遍历当前奶牛可以直接到达的奶牛
37
        for v in e[u]:
38
            if not vis[v]:
39
                q.append(v)
40
                vis[v] = ________
41


42
    # 更新最大可到达奶牛数量
43
    if tot > ans:
44
        ans = tot
45


46
# 输出最大可到达奶牛数量
47
print(______)

该算法使用图的表示和 BFS 来计算每头奶牛作为起点时，最多可以到达多少头奶牛。通过遍历每个节点并执行 BFS，我们可以找到最大的可达节点数。复杂度主要受 BFS 和图的构建影响，为 $O(N^2)$。

P6111 [USACO18JAN] MooTube S

https://usaco.org/index.php?page=viewproblem2&cpid=788

树的性质:

由于是树形结构，任意两个节点之间有且仅有一条路径。 任意两个视频间的相关性是路径上所有边中相关性最小的那一条。 解题思路 深度优先搜索 (DFS): 我们可以从给定的视频节点出发，使用 DFS 遍历整棵树。 在遍历过程中，只访问那些与当前节点相关性大于等于 K 的节点。 计数满足条件的节点。

1
def dfs(u, fa, k):
2
    global cnt
3
    # 遍历当前节点 u 的所有邻接节点
4
    for v, w in G[u]:
5
        # 如果该节点不是父节点且相关性 w 大于等于 k
6
        if v != fa and w >= k:
7
            cnt += 1  # 满足条件的节点计数加一
8
            dfs(v, u, k)  # 递归调用 DFS
9


10
import sys
11
# 增加递归深度限制，确保 DFS 不会因深度过大而失败
12
sys.setrecursionlimit(10000)
13


14
n, Q = map(int, input().split())
15
G = [[] for _ in range(n + 1)]  # 初始化邻接表
13 collapsed lines
16


17
# 读取 N-1 条边的信息
18
for _ in range(n - 1):
19
    p, q, r = map(int, input().split())
20
    G[p].append((q, r))  # 添加边 p -> q
21
    G[q].append((p, r))  # 添加边 q -> p (无向图)
22


23
# 处理每个查询
24
for _ in range(Q):
25
    k, v = map(int, input().split())
26
    cnt = 0  # 初始化计数
27
    dfs(v, -1, k)  # 从节点 v 开始 DFS，父节点设为 -1 表示无父节点
28
    print(cnt)  # 输出满足条件的视频数量

填空:

1
def dfs(u, fa, k):
2
    global cnt
3
    # 遍历当前节点 u 的所有邻接节点
4
    for v, w in G[u]:
5
        # 如果该节点不是父节点且相关性 w 大于等于 k
6
        if ___ and ___:
7
            cnt += 1  # 满足条件的节点计数加一
8
            dfs(___)  # 递归调用 DFS
9


10
import sys
11
# 增加递归深度限制，确保 DFS 不会因深度过大而失败
12
sys.setrecursionlimit(10000)
13


14
n, Q = map(int, input().split())
15
G = [[] for _ in range(___)]  # 初始化邻接表
13 collapsed lines
16


17
# 读取 N-1 条边的信息
18
for _ in range(n - 1):
19
    p, q, r = map(int, input().split())
20
    G[p].append((q, r))  # 添加边 p -> q
21
    G[q].append((___, ___))  # 添加边 q -> p (无向图)
22


23
# 处理每个查询
24
for _ in range(Q):
25
    k, v = map(int, input().split())
26
    cnt = ___  # 初始化计数
27
    dfs(v, ___, k)  # 从节点 v 开始 DFS，父节点设为 -1 表示无父节点
28
    print(___)  # 输出满足条件的视频数量

作业题 # P2997 [USACO10NOV] Banner S

https://www.luogu.com.cn/problem/P2997

1
平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内

枚举 dx, dy, dx 与 dy 互质即可。

deque
常规 Q-learning
Article title：读取奶牛数量
Article author：Julyfun
Release time：Nov 9, 2024
Copyright 2025
Sitemap