前言

alt

题解

前5题比较简单，F题没思路，太难。

A. 清楚姐姐的糖葫芦

签到题

s = input()

print (s.count('o'))

B. 清楚姐姐买竹鼠

思路: 贪心

  1. , 则全买单只
  2. , 则需要优先买3只，多余的考虑买单只补足。

但是这题需要特别考虑:

存在用b购买三只竹鼠的费用，优于用a购买1或2只竹鼠的情况


if a * 3 <= b:
    print (x * a)
else:
    z1 = (x % 3) * a + (x // 3) * b
    z2 = (x // 3 + 1) * b
    print (min(z1, z2))

C. 竹鼠饲养物语

思路: 贪心 + 大剪枝

种类数 m 特别大，但是非常的稀疏

  1. 离散化，用map保存
  2. 大剪枝，因为最n , 超过n的都是无意义的种类

如果前后两个满足编号连续

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

from collections import Counter
arr = list(map(int, input().split()))

# 离散化计数
cnt = Counter()
for v in arr:
   cnt[v] += 1

# 排序
dp = sorted(cnt.items())

from math import inf

ans = 0
cap = inf
pre = 0
for i in range(0, len(dp)):
   # 保证连续+1递增
   if pre + 1 != dp[i][0]:
       break
   cap = min(cap, dp[i][1])
   ans += cap
   pre += 1
   
print (ans)

D. 清楚姐姐跳格子

思路: BFS + 因子拆解(剪枝）

一个正整数的因子个数为

则其因子个数为

在 的情况下，其实还是蛮大的, 因子个数级别

但实际上，切入点，还是大剪枝，因为很多因子都是无效数据

直接枚举即可

还是

n = int(input())

arr = list(map(int, input().split()))

def factor(v, limit):
    res = []
    i = 1
    while i <= v // i and i <= limit:
        if v % i == 0:
            res.append(i)
            if i != v // i:
                if v // i <= limit:
                    res.append(v // i)
        i += 1
    return res

from math import inf
dp = [inf] * n

from collections import deque
deq = deque()
dp[0] = 0
deq.append(0)

while len(deq) > 0:
    u = deq.pop()
    ls = factor(arr[u], n)
    for x in ls:
        if u - x >= 0 and dp[u - x] > dp[u] + 1:
            dp[u - x] = dp[u] + 1
            deq.append(u - x)
        if u + x < n and dp[u + x] > dp[u] + 1:
            dp[u + x] = dp[u] + 1
            deq.append(u + x)      

print (dp[-1])

E. 清楚姐姐的布告规划

思路: 0-1背包

带有限制的0-1背包，属于板子题

t = int(input())

from math import inf
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    dp = [inf] * (n + 1)
    dp[0] = 0
    for (i, v) in enumerate(arr):
        for j in range(n - v, -1, -1):
            if j <= i and j + v > i:
                dp[j + v] = min(dp[j + v], dp[j] + 1)

    if dp[-1] == inf:
        print (-1)
    else:
        print (dp[-1])
    
for _ in range(t):
    solve()

F. 竹鼠，宝藏与故事

先占个坑

写在最后

alt