周赛 Round 41 A~E题解

A 小红接雨水

没看，GPT 秒的

# 读取输入
a, b, c = map(int, input().split())

# 计算左右两边的最大高度
left_max = max(a, b)
right_max = max(b, c)

# 计算能接的最大水面积
max_water = min(left_max, right_max) - b

# 输出结果
print(max(0, max_water))

B 小红的排列构造

选最后 k 个位置，shift 一位

def solve(n, k, p):
    if k > n or k==1:
        print(-1)
        return
    res = p[: n - k]
    left = p[n - k :]
    res += left[1:] + left[:1]
    print(" ".join(map(str, res)))


n, k = map(int, input().split())
p = list(map(int, input().split()))
solve(n, k, p)

C 小红的循环移位

用 deque 模拟，每次只需要判断最后 2 位能否被 4 整除，循环最多 n 次

长度<2 的时候，需要特判能否被4 整除。

from collections import deque


def minOperation(s):
    n = len(s)
    if n < 2:
        if int(s) % 4 == 0:
            return 0
        return -1
    s = list(map(int, s))
    d = deque(s)
    for _ in range(n + 1):
        x, y = d.pop(), d.pop()
        v = y * 10 + x
        if v % 4 == 0:
            return _
        d.append(y)
        d.append(x)
        d.append(d.popleft())

    return -1


s = input()
print(minOperation(s))

D 小红的好串

猜结论，尽量等分成 r e d 三份，red 子序列的个数最多。

区间%3 !=0 时，要枚举所有情况。

比如余数为 1, 3 个子区间长度可能是

x+1, x, x

x, x+1, x

x, x, x+1

余数为 2 时，分成 2 个 1，也是 3 种情况

x+1, x+1, x

x+1, x, x+1

x, x+1, x+1

知道了每个区间的长度，要想快速求解要修改几次把该区间全部变成 r / e /d, 可以使用前缀和。

helper 函数的参数函数：l, r 是区间左右边界。x, y 分别是 r e 2 个区间的长度。

class PrefixSum:
    def __init__(self, a):
        self.n = len(a)
        self.sum = [0] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.sum[i] = self.sum[i - 1] + a[i - 1]
 
    def __getitem__(self, key):
        if isinstance(key, slice):
            start = key.start if key.start is not None else 0
            stop = key.stop if key.stop is not None else self.n - 1
 
            return self.get_sum(start, stop)
 
        return self.sum[key + 1]
 
    def __iter__(self):
        return iter(self.sum)
 
    def __len__(self):
        return self.n
 
    def get_sum(self, l, r):
        if l > r:
            return 0
        return self.sum[r + 1] - self.sum[l]
 
    def __repr__(self):
        return str(self.sum)
 
 
n, q = map(int, input().split())
s = input()
g = [[] for _ in range(3)]
for c in s:
    g[0].append(int(c == "r"))
    g[1].append(int(c == "e"))
    g[2].append(int(c == "d"))
 
pre = [PrefixSum(g[i]) for i in range(3)]

 
def helper(l, r, x, y):
    n1, n2, n3 = x, y, r - l + 1 - x - y
    cost1 = n1 - pre[0][l : l + x - 1]
    cost2 = n2 - pre[1][l + x : l + x + y - 1]
    cost3 = n3 - pre[2][l + x + y : r]
    return cost1 + cost2 + cost3
 
 
for _ in range(q):
    l, r = MII(1)
    N = r - l + 1
 
    if N <= 2:
        print(0)
        continue
    x, y = divmod(N, 3)
 
    if y == 0:
        print(helper(l, r, x, x))
    elif y == 1:
        res = helper(l, r, x, x)
        res = min(res, helper(l, r, x, x + 1))
        res = min(res, helper(l, r, x + 1, x))
        print(res)
    else:
        res = helper(l, r, x + 1, x)
        res = min(res, helper(l, r, x, x + 1))
        res = min(res, helper(l, r, x + 1, x + 1))
        print(res)

E 小红的树上赋值（easy）

自底向上树形 dp, 每个节点记录所在子树中没有染色的节点列表。

遇到红色节点就从 t[u] 中取一半赋值 1，再取一半赋值-1.

合并列表的时候使用 small to large 技巧，降低复杂度。

最终树中可能剩余一些节点不是任何红色节点的子节点，它们最终恰好都被收集在 t[0] 中，全部赋值成 1 就可以了。

class Tree:
    def __init__(self, g=None, edges=None, root=0):
        if edges is not None:
            self.n = n = len(edges) + 1
            self.g = g = [[] for _ in range(n)]
            for u, v in edges:
                self.g[u].append(v)
                self.g[v].append(u)
        else:
            self.n = n = len(g)
            self.g = g
        self.root = root
        self.parent = parent = [-1] * n
        stk = [root]
        self.order = order = [root]

        while stk:
            u = stk.pop()
            for v in g[u]:
                if v != root and parent[v] == -1:
                    parent[v] = u
                    stk.append(v)
                    order.append(v)


n, l, r = MII()
s = input()
edges = [LII(1) for _ in range(n - 1)]
tree = Tree(edges=edges)
t = [[i] for i in range(n)]  # 每个节点所在子树中没有染色的节点列表
a = [0] * n  # 每个节点的权值


def merge(t1, t2):
    if len(t1) >= len(t2):
        t1.extend(t2)
        return t1
    else:
        t2.extend(t1)
        return t2


for u in reversed(tree.order):
    # 首先合并所有子树
    for v in tree.g[u]:
        if v != tree.parent[u]:
            t[u] = merge(t[u], t[v])
    if s[u] == "R":
        N = len(t[u])
        n2 = N // 2
        for v in t[u][:n2]:
            a[v] = -1
        for v in t[u][n2 : n2 * 2]:
            a[v] = 1
        t[u] = []
for v in t[0]:
    a[v] = 1
print(*a)