P7148 [USACO20DEC] Cowntagion S
1号点有一头牛
节点的牛的来源只能来自于父亲节点
现在如果要给2号牛,1号节点给一只牛就是最优选择 为什么呢?
因为翻倍和给一头牛代价一样,所以给2头牛和给1头牛再翻倍是一样的
以此类推,多头牛时,翻倍是更优的一种选择,并且只需给每个子节点1头牛
1读一个 n2统计每个点儿子数量 son3每次读一条边4 x, y5 son[x] += 16 son[y] += 17for i in range(2, n + 1):8 son[i] -= 19ans = 010for i in range(1, n + 1):11 假设到达这个点的时候它的感染数量一定是 1 (x = 1)12 while x 还没到 (i 的儿子数量 + 1):13 x *= 214 ans += 115 ans += i 的儿子数量1 collapsed line
16print(ans)
1sum_counts = [0] * 100001 # Initialize an array to keep track of the number of edges2total = 03
4n = int(input()) # Read the number of nodes5for _ in range(1, n):6 x, y = map(int, input().split()) # Read edges7 sum_counts[x] += 1 # Record the number of edges8 sum_counts[y] += 19
10for i in range(1, n + 1):11 if i != 1: # Exclude the root node12 sum_counts[i] -= 1 # Subtract 1 from the edge count for the subtree13 x = 114 while x <= sum_counts[i]: # While the required count is not reached15 total += 14 collapsed lines
16 x *= 2 # Double the growth17 total += sum_counts[i] # Allocate the remaining edges18
19print(total)
P3142 [USACO16OPEN] Field Reduction S
想要求出最终围栏围起来的面积,只需要计算 (maxx−minx)(maxy−miny)(maxx−minx)(maxy−miny) 的值即可。
首先,我们先用 Xi 排序,求得最大的 3 个点和最小的 3 个点。同样的方法给 Yi 排序,求得最大的 3 个点和最小的 3 个点。我们要暴力的答案中必定包含这 12 个点(当然有重复的点要去重)。
接下来就是暴力的核心,用 dfs 每一次选择 3 个点,然后最后计算它的面积,取最小值即可。
1class Node:2 def __init__(self, x, y, down):3 self.x = x4 self.y = y5 self.down = down6
7def check(r1, r2, r3):8 global ans9 min_x = float('inf')10 max_x = float('-inf')11 min_y = float('inf')12 max_y = float('-inf')13 for i in range(1, n + 1):14 if b[i].down == r1 or b[i].down == r2 or b[i].down == r3:15 continue43 collapsed lines
16 min_x = min(min_x, b[i].x)17 max_x = max(max_x, b[i].x)18 min_y = min(min_y, b[i].y)19 max_y = max(max_y, b[i].y)20 ans = min(ans, (max_x - min_x) * (max_y - min_y)) # Update the answer with the minimum value21
22n = int(sys.stdin.readline().strip())23b = [None] * (50005)24ans = 1e1825g = [0] * (50005)26cnt = 027
28for i in range(1, n + 1):29 x, y = map(int, sys.stdin.readline().strip().split())30 b[i] = Node(x, y, i)31
32b[1:n + 1] = sorted(b[1:n + 1], key=lambda node: node.x)33for i in range(1, 4):34 cnt += 135 g[cnt] = b[i].down36for i in range(n, n - 3, -1):37 cnt += 138 g[cnt] = b[i].down39
40b[1:n + 1] = sorted(b[1:n + 1], key=lambda node: node.y)41for i in range(1, 4):42 cnt += 143 g[cnt] = b[i].down44for i in range(n, n - 3, -1):45 cnt += 146 g[cnt] = b[i].down47
48g = sorted(g[1:cnt + 1])49m = len(set(g[1:cnt + 1])) # Unique values to prevent duplicate contributions.50
51for i in range(1, m + 1): # Enumerate the nodes52 for j in range(1, m + 1):53 for k in range(1, m + 1):54 if k == j or i == j or i == k:55 continue56 check(g[i], g[j], g[k])57
58print(int(ans))
P5198 [USACO19JAN] Icy Perimeter S
种子填充算法可以简单的解决。
这道题就是让我们求最大连通块的面积和周长。面积很简单,就是这个冰激凌球中’#‘的数量。而周长我们可以轻而易举地推出是这个冰激凌球中’#‘上下左右四个方向‘.’的个数。对于递归中的每个点,如果周围是未编号节点,大小加一并且进入该点,如果周围是空地,周长加一。