牛客周赛 Round 36 解题报告 | 珂学家 | 状态DP + 构造 + 9棵树状数组

前言

整体评价

今天index.php/tags-41973.html" >���对容易，E的构造题，感谢出题人极其善意的Case 1, 算是放水了。F题是个很典的结论题，由于存在动态点修改，所以引入树状数组做区间和的快速计算。

A. 小红的数位删除

题型: 签到

s = input()print (s[:-3])

B. 小红的小红矩阵构造

思路: 模拟

h, w, s = list(map(int, input().split()))ts = 0grid = []for i in range(h):    arr = list(map(int, input().split()))    grid.append(arr)    ts += sum(arr) hs = set()for i in range(h):    v = 0    for u in grid[i]:        v = v ^ u    hs.add(v)for i in range(w):    v = 0    for j in range(h):        v ^= grid[j][i]    hs.add(v)    if len(hs) == 1 and ts == s:    print ("accepted")else:    print ("wrong answer")

C. 小红的白色字符串

思路: 状态机DP

引入三个状态

• 0, 末尾是空格，
• 1, 末尾是小写字母
• 2, 末尾是大写字母

  具体转移和当前的字母的大小写性质有关

  具体看代码

  s = input()from math import infdp0, dp1, dp2 = 0, inf, infn = len(s)for c in s:    if c >= 'A' and c  0:    y, x = deq.popleft()    for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:        ty = y + dy        tx = x + dx        if 0