2022 年 12 月青少年软编等考 C 语言四级真题解析

T1. 开餐馆

此题为 2020 年 12 月四级第一题原题，见 2020 年 12 月青少年软编等考 C 语言四级真题解析中的 T1。

T2. 糖果

由于在维护世界和平的事务中做出巨大贡献，Dzx 被赠予糖果公司 2010 年 5 月 23 日当天无限量糖果免费优惠券。在这一天，Dzx 可以从糖果公司的 $N$ 件产品中任意选择若干件带回家享用。糖果公司的 $N$ 件产品每件都包含数量不同的糖果。Dzx 希望他选择的产品包含的糖果总数是 $K$ 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx 最多能带走多少糖果呢？注意：Dzx 只能将糖果公司的产品整件带走。

时间限制：7 s
内存限制：64 MB

• 输入
  第一行包含两个整数 $N(1\le N\le 100)$ 和 $K(1\le K\le 100)$。
  以下 $N$ 行，每行 $1$ 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 $1000000$。
• 输出
  符合要求的最多能达到的糖果总数，如果不能达到 $K$ 的倍数这一要求，输出 $0$。
• 样例输入

  5 7
  1
  2
  3
  4
  5
  

• 样例输出

  14
  

• 提示
  Dzx 的选择是 $2+3+4+5=14$，这样糖果总数是 $7$ 的倍数，并且是总数最多的选择。

思路分析

此题考查动态规划中的背包问题，属于基础题。

容易想到定义 $f_{i,j}$ 表示前 $i$ 种糖果是否可以获得总数 $j$ 颗糖果，然后从大到小遍历状态数组，找到最大且满足是 $k$ 的倍数的 $j$ 即为答案，但是糖果的总数最多为 $10^8$，会导致空间和时间超限。

根据题目描述，我们需要求出糖果总数是 $k$ 的倍数的结果，于是我们可以只记录糖果总数在 $\mathrm{mod}k$ 的状态下可以获得的最大值，于是定义 $f_{i,j}$ 表示前 $i$ 种糖果在总数 $\mathrm{mod}k=j$ 的状态下可以获得的最大值，容易得到状态转移方程为
f i , j = max ⁡ { f i − 1 , j , f i − 1 , ( j − ( a i   m o d   k ) )   m o d   k + a i } f_{i,j} = \max\{f_{i-1,j}, f_{i-1, (j-(a_i\bmod k)) \bmod k} + a_i\} fi,j​=max{ fi−1,j​,fi−1,(j−(ai​modk))modk​+ai​}

此题询问的是恰好满足的情况，因此初始值为 f i