摘要
Title: Acwing 第 42 场周赛
Tag: 树的DFS、kmp

第 42 场周赛

A AcWing 4311. 最小值

思路

模拟

代码

'''
Author: NEFU AB-IN
Date: 2022-03-12 18:59:53
FilePath: \ACM\Acwing\42\b.py
LastEditTime: 2022-03-12 19:02:02
'''
n, m = map(int, input().split())
minn = int(2e9)
for i in range(n):
    a, b = map(int, input().split())
    minn = min(minn, a / b)
print(f'{m * minn:.6f}')

B AcWing 4312. 出现次数

思路

思路是直接KMP，复杂度大约1e8可以过，但不保险
正解是 $O(n^2)$ 处理出来模板串的前缀和，之后在进行 $O(1)$ 的查询

代码

'''
Author: NEFU AB-IN
Date: 2022-03-12 18:59:53
FilePath: \ACM\Acwing\42\b.py
LastEditTime: 2022-03-12 19:13:46
'''
n, m, q = map(int, input().split())
s = " " + input()
t = " " + input()

N = 2000
ne = [0] * N

j = 0
for i in range(2, m + 1):
    while j and t[i] != t[j + 1]:
        j = ne[j]
    if t[i] == t[j + 1]:
        j += 1
    ne[i] = j
for _ in range(q):
    l, r = map(int, input().split())
    j, ans = 0, 0
    for i in range(l, r + 1):
        while j and s[i] != t[j + 1]:
            j = ne[j]
        if s[i] == t[j + 1]:
            j += 1
        if j == m:
            ans += 1
            j = ne[j]
    print(ans)

C AcWing 4313. 满二叉树等长路径

思路

没有推结论，看数据比较小，直接DFS爆搜的
- 首先，先求出每个点上面路径的权值和，这样可以顺便求出来根节点到子节点的最大值 maxn
- 其次，求出每个点为根节点的子节点的最大值，不包括根节点
- 最后从根节点爆搜即可，因为从根节点开始加边的权值是最优的
  - 其次每次加边不能让子节点的最大值超过maxn，所以记录差值为 $maxn - (w[u] + w + maxw[v])$
  - 即最大值 - (此节点u上面的权值和 + (u->v)这条边的权值 + v下面的最大值)
  - 比如下面这个例子，当u = 1，v = 2时
    cha = 22 - 0 - 1 - 14 = 7
  - 之后将上面补的差值和自己补的差值往下传即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-12 19:29:40
FilePath: \ACM\Acwing\42\c.py
LastEditTime: 2022-03-12 21:44:35
'''
N = int(1e4 + 10)
g = [[] * N for _ in range(N)]
ww = [0] * N  # 记录当前点上面的权值
maxw = [0] * N  #记录当前点下面的最大值

maxn = 0
maxjd = 1
ans = 0


def dfs1(fa, u, len):
    global maxn, maxjd
    for v, w in g[u]:
        if v == fa:
            continue
        ww[v] = ww[u] + w
        dfs1(u, v, len + w)
    if len > maxn:
        maxn = len
        maxjd = u


def dfs2(fa, u):
    for v, w in g[u]:
        if v == fa:
            continue
        maxw[u] = max(maxw[u], dfs2(u, v) + w)
    return maxw[u]


def dfs(fa, u, z):
    global ans
    for v, w in g[u]:
        if v == fa:
            continue
        cha = maxn - ww[u] - maxw[v] - w
        ww[v] += (cha + z)  #差值 和 补充父节点补的
        ans += cha
        dfs(u, v, cha + z)


n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
    g[i + 2].append([(i + 2) // 2, a[i]])
    g[(i + 2) // 2].append([i + 2, a[i]])

dfs1(0, 1, 0)
dfs2(0, 1)
dfs(0, 1, 0)
print(ans)

第 42 场周赛

A AcWing 4311. 最小值

思路

代码

B AcWing 4312. 出现次数

思路

代码

C AcWing 4313. 满二叉树等长路径

思路

代码