Skip to content

课堂计划

P10135 [USACO24JAN] Potion Farming S

每个叶子恰好走一次，若叶子个数为 $v$，则只需考虑前 $v$ 次遍历。若一个子树中有 $n$ 次药水出现，$m$ 个叶子，则其对答案的贡献为 $min(n, m)$

N = int(1e5 + 19)
p = [0] * N
cnt = [0] * N
dep = [0] * N
tot = 0
mx = 0
f = [0] * N
fa = [0] * N
g = [[] for _ in range(N)]
depid = [[] for _ in range(N)]

def dfs(node, parent):
    global mx, tot
    dep[node] = dep[parent] + 1
    fa[node] = parent
    mx = max(dep[node], mx)
    depid[dep[node]].append(node)
    flag = False
    for neighbor in g[node]:
        if neighbor != parent:
            dfs(neighbor, node)
            flag = True
    if not flag:
        tot += 1
        f[node] += 1

def read():
    return int(input().strip())

def write(value, end_char):
    print(value, end=end_char)

n = read()
for i in range(1, n + 1):
    p[i] = read()
for _ in range(1, n):
    a, b = read(), read()
    g[a].append(b)
    g[b].append(a)
dfs(1, 1)
for i in range(1, tot + 1):
    cnt[p[i]] += 1
ans = 0
while mx:
    for i in depid[mx]:
        if f[i]:
            if cnt[i] <= f[i]:
                f[i] -= cnt[i]
                ans += cnt[i]
            else:
                ans += f[i]
                f[i] = 0
        f[fa[i]] += f[i]
    mx -= 1
write(ans, '\n')

P5197 [USACO19JAN] Grass Planting S

一个点的相邻的点都不能是同一颜色，如果算上自己有 $n$ 个颜色，那就至少要 $n$ 个颜色。

定义每个点的度为 d[i]，取 d[i] + 1 的最大值就是答案吗？答案是肯定。设最大值为 $t$，则先随便涂一个点 $i$ 的相邻点，以它为根继续考虑孩子颜色，发现对于每个孩子来说只有 $2$ 个颜色被确定了，从剩下 $t - 2$ 个颜色中任意选一些不同的颜色来涂孩子，以此递归就可以。

x = 0
y = 0
ans = 0
n = 0
deg = [0] * 100007

n = int(input())
for i in range(1, n):
    x, y = map(int, input().split())
    deg[x] += 1 # 统计度数
    deg[y] += 1
    if deg[x] > ans:
        ans = deg[x] + 1
    if deg[y] > ans:
        ans = deg[y] + 1

print(ans + 1)

P7148 [USACO20DEC] Cowntagion S

首先，对于每一个节点，如果它的感染者数目已经超过了儿子数，则进行的一定是儿子个数次 (2) 操作。

反之，如果在还没有足够的感染者个数的情况下就开始分，显然是不优的。

所以对于每一个节点都进行贪心：

  • 如果还不够分，就执行若干次 (1) 操作，直到够分了为止。
  • 如果已经够分了，就花若干天，每天执行一次 (2) 操作直到所有儿子都有感染者为止。

很容易证明这是最优的。

于是我们记录每一个节点的儿子个数，记为 cson[u]cson[u]，每次 dfsdfs 到一个点，我们就先计算 log⁡cson[u]+1logcson[u]+1，表示自增至足够感染者的天数（注意不是 ceil），然后进行分发，即花 cson[u]cson[u] 天给所有儿子都发一个感染者，最后注意根节点本身就有一只感染者，处理一下即可。