备战2024年蓝桥杯 -- 每日一题
Python大学A组

        试题一：包子凑数
        试题二：砝码称重
        试题三：倍数问题

---

试题一：包子称重

【题目描述】

        小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。比如一共有 3 种蒸笼，分别能放3、4 和 5 个包子。当顾客想买 11个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2笼 4 个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 33 种蒸笼，分别能放 4、5和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。

【输入格式】

        第一行包含一个整数 N。

        接下来 N 行，每行包含一个整数 Ai。

【输出格式】

        输出一个整数代表答案。

        如果凑不出的数目有无限多个，输出INF。

【数据范围】

        1≤N≤100
        1≤Ai≤100

【输入样例】

2
4
5

【输出样例】

6

【解题思路】

        容易看出是完全背包的变形，有几个物品，每个物品无限个，每个物品选任意个，能否凑到某个重量。题目说会出现有无限个数被凑不出来的， 说明这些数的gcd不是1。gcd为1呢？最大不能表示出来的数必定有个上界，因为两个数a,b（当gcd=1时），最大不能表示出来的数是：(a−1)(b−1)−1。当数字更多的时候，这个上界必然更小（可选的数字变多了），而99和98是100内最大的互质的数，所以这个上界选择10000。

【Python程序代码】

from math import *
n = int(input())
w = [0] + list(map(int,input().split()))
res = sum(w)
f = [[0]*(2*10**5+10) for _ in range(110)]
f[0][0]=1
for i in range(1,n+1):
    f[i][w[i]]=1
    for j in range(1,sum(w)+1):
        t = j-w[i]
        if t<0:t=-t
        f[i][j] += f[i-1][j] + f[i-1][j+w[i]] + f[i-1][t]
ans = 0
for i in range(1,sum(w)+1):
    if f[n][i]:
        ans+=1
print(ans)

---

试题二：砝码称重

【题目描述】

        你有一架天平和 N个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。请你计算一共可以称出多少种不同的正整数重量？注意砝码可以放在天平两边。

【输入格式】

        输入的第一行包含一个整数 N。

        第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN。

【输出格式】

        输出一个整数代表答案。

【数据范围】

        对于 50% 的评测用例，1≤N≤15。
        对于所有评测用例，1≤N≤100，N 个砝码总重不超过 105。

【输入样例】

3
1 4 6

【输出样例】

10

【样例解释】

【解题思路】 

        可以看出是01背包的变形，在放与不放中的放中变成了放左边还是放右边，假设左边固定是物品，f[i][j]表示前i个砝码称体重为j的物体是否成功。所以当选择不放第i个物体时f[i-1][j]，选择放左边时f[i-1][j+w[i]]，选择放右边时f[i-1][ j-w[i] ]三种状态转移过来，初始化f[0][0]=1同时f[i][w[i]]=1。

【Python程序代码】

from math import *
n = int(input())
w = [0] + list(map(int,input().split()))
res = sum(w)
f = [[0]*(2*10**5+10) for _ in range(110)]
f[0][0]=1
for i in range(1,n+1):
    f[i][w[i]]=1
    for j in range(1,sum(w)+1):
        t = j-w[i]
        if t<0:t=-t
        f[i][j] += f[i-1][j] + f[i-1][j+w[i]] + f[i-1][t]
ans = 0
for i in range(1,sum(w)+1):
    if f[n][i]:
        ans+=1
print(ans)

---

试题三：倍数问题

【题目描述】

        众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。

【输入格式】

        第一行包括 2 个正整数 n, K。

        第二行 n 个正整数，代表给定的 n 个数。

【输出格式】

        输出一行一个整数代表所求的和。

【数据范围】

        1≤n≤105,
        1≤K≤103,
        给定的 n 个数均不超过 108

【输入样例】

4 3
1 2 3 4

【输出样例】

9

【解题思路】

        这也是01背包的变形，不过还控制了选择的数量，因为是选三个数同时n的范围比k的范围大很多，所以可以优化一下n，也就是只取a[i]%k前三大的数，所以第一维枚举压缩到了k*3，第二维枚举三位数，从3开始枚举（主要原因是只用二维空间存储）只能从大的开始枚举，否则会出现重复。最后一维度枚举余数。具体看代码表述。

【Python程序代码】

n,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
mp = [[]for _ in range(K+5)]
for i in range(len(a)):
    mp[a[i]%K].append(a[i])
f = [[-1e9]*(K+5) for _ in range(5)]
f[0][0]=0
for i in range(K):
    for u in range(0,min(3,len(mp[i]))):
        t = mp[i][u]
        for j in range(3,0,-1):
            for k in range(K):
                f[j][k] = max(f[j][k],f[j-1][ (k-i+K)%K ]+t)
print(f[3][0])