以下是河南萌新联赛 2024 第（三）场所有题目的 python 题解，只包含求解的主体部分：

A

python 可直接使用 decimal 库进行高精度运算。

import decimal
from decimal import *
setcontext(Context(prec=200, Emax=200, Emin=0))

def solve():
    pi = Decimal("3.14159265358979323846264338327950288419716939937510582097")
    n = ii()
    mn = inf
    res = (0, 0)
    for i in range(n):
        p, a = mii()
        dis = abs(Decimal(Decimal(p) / Decimal(a)) - pi)
        if dis == mn:
            if p < res[0]:
                res = (p, a)
        elif dis < mn:
            mn = dis
            res = (p, a)
    print(res[0], res[1])
    return

B

直接判断。

def solve():
    n = ii()
    res = 0
    for _ in range(n):
        s = input()
        s = s.split('.')
        if all(0 <= x <= 255 for x in map(int, s)):
            res += 1
    print(res)
    return

C

递推。每个新增的圆与之前的 n - 1 个圆最多形成 2(n - 1) 个交点，新增的区域数即 2(n-1)，于是 f(n) = f(n-1) + 2(n-1)，通项公式为 f(n) = 2 + n*(n-1) (n>0).

def solve():
    n = ii()
    q = lmii()
    res = [x * (x - 1) + 2 if x > 0 else 1 for x in q]
    print(*res)

D

每个数只会被以其左侧元素作为左端点的区间操作影响。从左往右考虑，每次以某元素为左端点时，使区间包含所有与其相同的元素（因为 x ^ x = 0，这样相同的元素都会变为 0 之后无需再操作；而若包含其它的元素，之后还是得操作，不会更优）；另外，若元素本身为 0，可直接跳过，无需操作。

from itertools import groupby
def solve():
    n = ii()
    a = lmii()
    res = 0
    for x, g in groupby(a):
        if x: res += 1
    print(res)
    return

E

线段树维护区间最大连续段。这里维护每段内从左往右第一个黑色的下标 lpos （若为 0 则说明该区间全是白色）和从右往左数第一个黑色元素的下标 rpos（也就等价于维护前缀和后缀的白***间长度），每段内最大连续白色长度为 ans。合并时首先将 ans 更新为左右子区间的 ans 最大值，然后重点考虑跨左右子区间形成更长连续白色长度的情况，分情况讨论即可。

class Info:
    __slots__ = 'l', 'r', 'lpos', 'rpos', 'ans'
    
    def __init__(self, l = 0, r = 0, lpos = 0, rpos = 0, ans = 0):
        self.l, self.r = l, r
        self.lpos, self.rpos, self.ans = lpos, rpos, ans

    def __add__(self, other):
        u = Info(self.l, other.r, 0, 0, max(self.ans, other.ans))
        if self.lpos == 0 and other.lpos == 0:
            u.ans = max(u.ans, u.r - u.l + 1)
            u.lpos, u.rpos = 0, 0
        elif self.lpos == 0 and other.lpos:
            u.ans = max(u.ans, self.r - self.l + 1 + other.lpos - other.l)
            u.lpos, u.rpos = other.lpos, other.rpos
        elif self.lpos and other.lpos == 0:
            u.ans = max(u.ans, self.r - self.rpos + other.r - other.l + 1)
            u.lpos, u.rpos = self.lpos, self.rpos
        else:
            u.ans = max(u.ans, other.lpos - self.rpos - 1)
            u.lpos, u.rpos = self.lpos, other.rpos
        return u

class SegmentTree:
    __slots__ = 'n', 'info'

    def __init__(self, n: int = 0, v: Info = Info()):
        self.n = n
        self.info = [Info() for _ in range(4 * n)]

    def init(self, n: int, v: Info = Info()):
        self._build(1, 1, n, [v for _ in range(n)])

    def _build(self, p: int, l: int, r: int, init_: List[Info]):
        if r == l:
            self.info[p] = init_[l - 1]
            return
        m = (l + r) // 2
        self._build(2 * p, l, m, init_)
        self._build(2 * p + 1, m + 1, r, init_)
        self._pull(p)

    def _pull(self, p: int):
        self.info[p] = self.info[2 * p] + self.info[2 * p + 1]

    def _modify(self, p: int, l: int, r: int, x: int, v: Info):
        if r == l:
            self.info[p] = v
            return
        m = (l + r) // 2
        if x <= m: self._modify(2 * p, l, m, x, v)
        else: self._modify(2 * p + 1, m + 1, r, x, v)
        self._pull(p)

    def modify(self, p: int, v: Info):
        self._modify(1, 1, self.n, p, v)

    def _range_query(self, p: int, l: int, r: int, x: int, y: int) -> Info:
        if l > y or r < x: return None
        if l >= x and r <= y: return self.info[p]
        m = (l + r) // 2
        left = self._range_query(2 * p, l, m, x, y)
        right = self._range_query(2 * p + 1, m + 1, r, x, y)
        if left is None: return right
        elif right is None: return left
        return left + right

    def range_query(self, l: int, r: int) -> Info:
        return self._range_query(1, 1, self.n, l, r)

def solve():
    n, q = mii()
    T = SegmentTree(n)
    for i in range(1, n + 1):
        T.modify(i, Info(i, i, 0, 0, 1))
    for _ in range(q):
        ops = lmii()
        if ops[0] == 1:
            y = ops[1]
            if T.range_query(y, y).lpos == 0:
                T.modify(y, Info(y, y, y, y, 0))
            else:
                T.modify(y, Info(y, y, 0, 0, 1))
        else:
            l, r = ops[1], ops[2]
            print(T.range_query(l, r).ans)
    return

F

预处理 + 前缀和作差。注意到某个数在前一个相邻的数基础上变化的 bit 位就是 lowbit 的部分。

M = 2000005
pre = [0] * M
for i in range(1, M):
    pre[i] = pre[i - 1]
    lb = i & (-i)
    pre[i] += lb.bit_length()

def solve():
    x, k = mii()
    print(pre[x + k] - pre[x])
    return

G

固定 x 时，若 b > c，ax + by + cz 随 y 的增大单调递增，|ax + by + cz - w| 的最小值为 ax + by + cz - w 的最大负值和最小非负值的绝对值中的一个，于是枚举 x，二分 y。

def solve():
    a, b, c, n, w = mii()
    if b < c: b, c = c, b

    def check(y):
        nonlocal x, n, w
        z = n - x - y
        return a * x + b * y + c * z - w >= 0

    x = 1
    res = inf
    for i in range(n + 1):
        x = i
        left, right = 0, n - x + 1
        while left < right:
            mid = (left + right) // 2
            if check(mid): right = mid
            else: left = mid + 1

        y, z = left, n - x - left
        if y >= 0 and z >= 0:
            res = min(res, abs(a * x + b * y + c * z - w))
        y, z = left - 1, n - x - left + 1
        if y >= 0 and z >= 0:
            res = min(res, abs(a * x + b * y + c * z - w))

    print(res)
    return

H

动态规划，判断最多使用 x 次魔法时最终能否在 h 体力值限制下到达终点，f[i][j][k] 表示使用 k 次魔法时到达 (i, j) 最少耗费的体力值。若到终点时最小耗费大于初始值 h，则 x 次魔法不可行。进而二分 x 即可。

def solve():
    m, n, h = mii()
    cost = [lmii() for _ in range(m)]
    
    def check(x):
        f = [[[inf] * (x + 1) for _ in range(n)] for _ in range(m)]
        for k in range(x + 1): f[0][0][k] = 0
        
        for i in range(m):
            for j in range(n):
                for k in range(x + 1):
                    # 不使用魔法，体力值耗费增加
                    if i > 0:
                        f[i][j][k] = min(f[i - 1][j][k] + cost[i][j], f[i][j][k])
                    if j > 0:
                        f[i][j][k] = min(f[i][j - 1][k] + cost[i][j], f[i][j][k])
                    # 使用魔法，魔法次数加一，体力值耗费不变
                    if k > 0:
                        if i > 0:
                            f[i][j][k] = min(f[i - 1][j][k - 1], f[i][j][k])
                        if j > 0:
                            f[i][j][k] = min(f[i][j - 1][k - 1], f[i][j][k])
        
        return True if f[m - 1][n - 1][x] < h else False

    left, right = 0, m * n + 1
    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1

    print(left)
    return

I

跑两遍最短路即可。（1）针对可通过的边，以 1 为起始点跑一次，求出到 n 和到 k 的最短路 d0 和 d1；（2）再加入初始不可通过的边，以 k 为起始点求到 n 的最短路 d2。答案即为 d0 和 d1 + d2 的较小值，若都无法到达则输出 -1。

def Dijkstra(g, node):
    n = len(g)
    dis = [inf] * n
    dis[node] = 0
    h = [(0, node)]
    while h:
        d, x = heappop(h)
        if d > dis[x]: continue
        for y, w in g[x]:
            if d + w < dis[y]:
                dis[y] = d + w 
                heappush(h, (dis[y], y))
    return dis

def solve():
    n, m, k = mii()
    hidden = []
    g = [[] for _ in range(n)]
    for _ in range(m):
        x, y, w, state = mii()
        x -= 1; y -= 1
        if state == 1:
            g[x].append((y, w))
            g[y].append((x, w))
        else:
            hidden.append((x, y, w))

    dis = Dijkstra(g, 0)
    res = inf
    if dis[k - 1] == inf and dis[n - 1] == inf:
        return -1
    if dis[n - 1] < inf:
        res = dis[n - 1]
    if dis[k - 1] < inf:
        for x, y, w in hidden:
            g[x].append((y, w))
            g[y].append((x, w))
        dis2 = Dijkstra(g, k - 1)
        if dis2[n - 1] < inf:
            res = min(res, dis[k - 1] + dis2[n - 1])
    return res

J

模拟。

def solve():
    n, m = mii()
    kernel = [lmii() for _ in range(n)]
    matrix = [lmii() for _ in range(m)]
    res = [[0] * (m - n + 1) for _ in range(m - n + 1)]

    def mul(a, b):
        ans = 0
        for i, row in enumerate(a):
            for j, x in enumerate(row):
                ans += x * b[i][j]
        return ans

    for i in range(m - n + 1):
        for j in range(m - n + 1):
            sub = [[] for _ in range(n)]
            for k in range(n):
                sub[k] = matrix[i + k][j: j + n]
            res[i][j] = mul(kernel, sub)

    for row in res:
        print(*row)
    return

K

考虑向左侧，对于某个史莱姆 i，设其体积为 x，则它可以吃掉的同伴数量就是左侧第一个体积不大于 x 的史莱姆 j 可吃掉的同伴数量 + 1（在此之前体积大于 x 的史莱姆可先不断向左侧吃合并至 j）；向右侧也是一样的道理。于是用单调栈维护左侧和右侧不大于当前元素的首个元素下标之后递推即可。最终答案即为左右两侧可吃的数量之和。

def solve():
    n = ii()
    a = lmii()

    left = [-1] * n
    st = []
    for i, x in enumerate(a):
        while st and a[st[-1]] > x:
            st.pop()
        if st: left[i] = st[-1]
        st.append(i)

    right = [n] * n
    st = []
    for i in range(n - 1, -1, -1):
        while st and a[st[-1]] > a[i]:
            st.pop()
        if st: right[i] = st[-1]
        st.append(i)

    res = [0] * n
    for i in range(n):
        pre = left[i]
        if pre >= 0: res[i] = res[pre] + 1

    res2 = [0] * n
    for i in range(n - 1, -1, -1):
        sur = right[i]
        if sur < n: res2[i] = res2[sur] + 1
    
    ans = [res[i] + res2[i] for i in range(n)]
    print(*ans)

L

模拟。

def solve():
    m, n, q = mii()
    H = dict()
    for _ in range(m):
        pub, pri = input().split()
        H[pri] = pub
    H2 = defaultdict(set)
    H3 = defaultdict(set)
    for _ in range(n):
        ip, k = input().split()
        k = int(k)
        for _ in range(k):
            data = input().split()
            H3[ip].add(data[0])
            H2[data[0]].update(data[2:])
    for _ in range(q):
        name, ip, pri = input().split()
        if name in H3[ip] and H[pri] in H2[name]:
            print('Yes')
        else:
            print('No')
    return

M

暴搜。没有技巧，全是感情。

def solve():
    x, y, tx, ty, curx, cury = mii()
    x -= 1; y -= 1; tx -= 1; ty -= 1, curx -= 1; cury -= 1
    m = ii()
    obs = [[0] * 30 for _ in range(30)]
    dis = [[[[-1] * 30 for _ in range(30)] for _ in range(30)] for _ in range(30)]
    for _ in range(m):
        ox, oy = mii()
        obs[ox - 1][oy - 1] = 1
    in_g = lambda x, y: True if (0 <= x < 30 and 0 <= y < 30) else False
    
    reach = False
    offset = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    q = deque([(x, y, curx, cury)])
    dis[x][y][curx][cury] = 0

    while q:
        x0, y0, curx0, cury0 = q.popleft()
        for dx, dy in offset:
            x1, y1 = x0 + dx, y0 + dy
            curx1, cury1 = curx0 + dx, cury0 + dy
            if not in_g(x1, y1) or obs[x1][y1]: continue
            if x1 == curx0 and y1 == cury0:
                if not in_g(curx1, cury1) or obs[curx1][cury1]: continue
                if dis[x1][y1][curx1][cury1] == -1:
                    dis[x1][y1][curx1][cury1] = dis[x0][y0][curx0][cury0] + 1
                    if curx1 == tx and cury1 == ty:
                        reach = True
                        break
                    q.append((x1, y1, curx1, cury1))
            else:
                if dis[x1][y1][curx0][cury0] == -1:
                    dis[x1][y1][curx0][cury0] = dis[x0][y0][curx0][cury0] + 1
                    q.append((x1, y1, curx0, cury0))
        if reach: break

    res = inf
    for dx, dy in offset:
        a, b = tx + dx, ty + dy
        if not in_g(a, b) or obs[a][b]: continue
        if dis[a][b][tx][ty] != -1:
            res = min(res, dis[a][b][tx][ty])
    res = -1 if res == inf else res
    print(res)
    return