前言

alt

题解

赞助场，果然难。

每次周赛都能学到知识，^_^.

A. 小红小紫投硬币

思路: 数学

假设都是n次投硬币

  • p(win)为小红胜利的概率

  • P(draw)为平局的概率d

  • p(lose)为小红失利的概率

根据对称性, p=p(win)=p(lose)

此时小红多投一次，那么

  • 原先胜利，多投一次还是胜利
  • 原先失败，多投一次最多平局
  • 原先平局，多投一次，有一半概率转化为胜局

这就是恒为 1/2=0.5 的由来

print ("%.06f" %(0.5))

B. 小红的字符串

思路: 谈心

左移/右移的最小代价为

s = input()

i, j = 0, len(s) - 1
res = 0
while i < j:
    p1, p2 = ord(s[i]), ord(s[j])
    res += min(abs(p1 - p2), 26 - abs(p1 - p2))
    i += 1
    j -= 1
    
print (res)

C. 小红的 01 消除

思路: 栈模拟

其实'11', '00', 没有任何价值，操作只会让'01'配对数变少

因此单纯的栈模拟，模拟01配对消除

n = int(input())

s = input()

x, y, z = list(map(int, input().split()))

res = 0
stk = 0 # 模拟栈上的1个数
for c in s:
    if c == '0':
        stk += 1
    else:
        if stk > 0:
            stk -= 1
            res += 1

# 取两者的最小值
print (min(res, y))

D. 小红组比赛

思路: 分组背包

板子题

不过需要注意的是

  • 取每组的最大值总和，作为背包最大容量S
  • 不能取Target作为背包容量

因为和target最接近，是一个 绝对值最小的概念

n, m = list(map(int, input().split()))

g = []

for _ in range(n):
    tmp = list(map(int, input().split()))
    g.append(tmp)
    
target = int(input())

# 取每组的最大和，作为背包的最大容量
MX = sum([max(row) for row in g])
dp = [False] * (MX + 1)
dp[0] = True

for i in range(n):
    arr = g[i]
    dp2 = [False] * (MX + 1)
    for v in arr:
        for k in range(MX - v, -1, -1):
            if dp[k]:
                dp2[k + v] = True
    dp = dp2

from math import inf
ans = inf
for i in range(MX, -1, -1):
    if dp[i]:
        ans = min(ans, abs(target - i))
    
print (ans)

E. 折半丢弃

思路: 二分+贪心

这个数组的mex存在单调性，所以二分一定可行。

问题在于这个check如何构造验证呢？

这里有个贪心技巧，就是从大到小去构造补足。

为啥从小到大贪心构造不行呢？

比如存在，[0,1,2,4,5,6,7,7] 这个数组 从小到大贪，容易得到非最优解.

推而广之:

t = int(input())

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    def check(m):
        vis = [0] * (m + 1)
        for v in arr:
            while v > m:
                v //= 2
            vis[v] += 1
        ptr = m
        while vis[ptr] > 0 and ptr >= 0:
            if vis[ptr] == 0:
                return False
            vis[ptr // 2] += vis[ptr] - 1
            ptr -= 1
        return ptr == -1
    
    l, r = 0, n - 1
    while l <= r:
        m = l + (r - l) // 2
        if check(m):
            l = m + 1
        else:
            r = m - 1
    
    print (r + 1)
        
for _ in range(t):
    solve()

F. 小红走矩阵

思路: 分层BFS

这题应该属于多状态的分层BFS

  • 没有用技能, 普通BFS
  • 使用技能（枚举某个方向）+ 分层BFS

设计状态：

h, w = list(map(int, input().split()))

g = []
for _ in range(h):
    g.append(input())
    
from math import inf
dp = [[[[inf] * w for _ in range(h)] for _ in range(2)] for _ in range(5)]

from collections import deque

deq = deque()
if g[0][0] == '.':
    deq.append((4, 0, 0, 0))
    dp[4][0][0][0] = 0
    
    for i in range(4):
        dp[i][0][0][0] = 0
        deq.append((i, 0, 0, 0))
else:
    for i in range(4):
        dp[i][1][0][0] = 0
        deq.append((i, 1, 0, 0))
        
while len(deq) > 0:
    op, d, y, x = deq.popleft()
    cost = dp[op][d][y][x]
    
    for (i, (dy, dx)) in enumerate([(-1, 0), (1, 0), (0, -1), (0, 1)]):
        ty, tx = y + dy, x + dx
        if 0 <= ty < h and 0 <= tx < w:
            if g[ty][tx] == '.':
                if dp[op][d][ty][tx] > cost + 1:
                    dp[op][d][ty][tx] = cost + 1
                    deq.append((op, d, ty, tx))
            elif g[ty][tx] == 'X' and op != 4:
                if d == 0 and op != i:
                    if dp[op][1][ty][tx] > cost + 1:
                        dp[op][1][ty][tx] = cost + 1
                        deq.append((op, 1, ty, tx))
    
res = inf
for i in range(5):
    for j in range(2):
        res = min(res, dp[i][j][-1][-1])
        
print (-1 if res == inf else res)

备注: 这题好像卡python，同等的java代码能过

G. 游游的删点直径

写在最后

alt