周赛 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)
自底向上树形 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)
