Skip to content

P7148 [USACO20DEC] Cowntagion S

1号点有一头牛

节点的牛的来源只能来自于父亲节点

现在如果要给2号牛，1号节点给一只牛就是最优选择 为什么呢？

因为翻倍和给一头牛代价一样，所以给2头牛和给1头牛再翻倍是一样的

以此类推，多头牛时，翻倍是更优的一种选择,并且只需给每个子节点1头牛

读一个 n
统计每个点儿子数量 son
每次读一条边
    x, y
    son[x] += 1
    son[y] += 1
for i in range(2, n + 1):
    son[i] -= 1
ans = 0
for i in range(1, n + 1):
    假设到达这个点的时候它的感染数量一定是 1 (x = 1)
    while x 还没到 （i 的儿子数量  + 1）:
        x *= 2
        ans += 1
    ans += i 的儿子数量
print(ans)

sum_counts = [0] * 100001  # Initialize an array to keep track of the number of edges
total = 0

n = int(input())  # Read the number of nodes
for _ in range(1, n):
    x, y = map(int, input().split())  # Read edges
    sum_counts[x] += 1  # Record the number of edges
    sum_counts[y] += 1

for i in range(1, n + 1):
    if i != 1:  # Exclude the root node
        sum_counts[i] -= 1  # Subtract 1 from the edge count for the subtree
    x = 1
    while x <= sum_counts[i]:  # While the required count is not reached
        total += 1
        x *= 2  # Double the growth
    total += sum_counts[i]  # Allocate the remaining edges

print(total)

P3142 [USACO16OPEN] Field Reduction S

想要求出最终围栏围起来的面积，只需要计算 (maxx−minx)(maxy−miny)(maxx−minx)(maxy−miny) 的值即可。

首先，我们先用 Xi​ 排序，求得最大的 3 个点和最小的 3 个点。同样的方法给 Yi​ 排序，求得最大的 3 个点和最小的 3 个点。我们要暴力的答案中必定包含这 12 个点（当然有重复的点要去重）。

接下来就是暴力的核心，用 dfs 每一次选择 3 个点，然后最后计算它的面积，取最小值即可。

class Node:
    def __init__(self, x, y, down):
        self.x = x
        self.y = y
        self.down = down

def check(r1, r2, r3):
    global ans
    min_x = float('inf')
    max_x = float('-inf')
    min_y = float('inf')
    max_y = float('-inf')
    for i in range(1, n + 1):
        if b[i].down == r1 or b[i].down == r2 or b[i].down == r3:
            continue
        min_x = min(min_x, b[i].x)
        max_x = max(max_x, b[i].x)
        min_y = min(min_y, b[i].y)
        max_y = max(max_y, b[i].y)
    ans = min(ans, (max_x - min_x) * (max_y - min_y))  # Update the answer with the minimum value

n = int(sys.stdin.readline().strip())
b = [None] * (50005)
ans = 1e18
g = [0] * (50005)
cnt = 0

for i in range(1, n + 1):
    x, y = map(int, sys.stdin.readline().strip().split())
    b[i] = Node(x, y, i)

b[1:n + 1] = sorted(b[1:n + 1], key=lambda node: node.x)
for i in range(1, 4):
    cnt += 1
    g[cnt] = b[i].down
for i in range(n, n - 3, -1):
    cnt += 1
    g[cnt] = b[i].down

b[1:n + 1] = sorted(b[1:n + 1], key=lambda node: node.y)
for i in range(1, 4):
    cnt += 1
    g[cnt] = b[i].down
for i in range(n, n - 3, -1):
    cnt += 1
    g[cnt] = b[i].down

g = sorted(g[1:cnt + 1])
m = len(set(g[1:cnt + 1]))  # Unique values to prevent duplicate contributions.

for i in range(1, m + 1):  # Enumerate the nodes
    for j in range(1, m + 1):
        for k in range(1, m + 1):
            if k == j or i == j or i == k:
                continue
            check(g[i], g[j], g[k])

print(int(ans))

P5198 [USACO19JAN] Icy Perimeter S

种子填充算法可以简单的解决。

这道题就是让我们求最大连通块的面积和周长。面积很简单，就是这个冰激凌球中'#'的数量。而周长我们可以轻而易举地推出是这个冰激凌球中'#'上下左右四个方向‘.’的个数。对于递归中的每个点，如果周围是未编号节点，大小加一并且进入该点，如果周围是空地，周长加一。