蓝桥杯备赛：15届真题第二题 奖杯排列

题目：

• 问题的根源是变量名和内置类型名冲突了。在代码中，list 被当成了一个变量名，但实际上它和 Python 内置的 list 类重名了，导致 Python 解释器混淆了。

解决方法：把列表变量名改成nums

sum += p
TypeError: unsupported operand type(s) for +=: 'builtin_function_or_method' and 'int'

• 
• 在 Python 中，sum 是一个内置函数，用于计算可迭代对象（如列表、元组等）中所有元素的总和。如果在代码中直接使用了 sum 作为变量名，就会覆盖内置的 sum 函数。
• 当尝试对 sum 使用 += 操作符时，Python 会将 sum 视为一个函数对象（builtin_function_or_method），而不是一个可以进行加法运算的数值类型。因此，尝试将一个整数（int）加到一个函数对象上时，就会引发 TypeError。
• 解决方法：把变量名sum改成q

正确题解：

解题步骤

1. 读取输入：我们首先读取题目给我们的输入，包括奖杯的数量 和等差数列的公差 ，以及每个奖杯的价值 。

2. 初始化：

   • 我们创建一个列表 dp，其中 dp[i] 表示以第  个奖杯结尾的等差数列的方案数。
   • 我们创建一个字典 last，其中 last[A_i] 表示值为  的奖杯在原序列中的位置。

3. 遍历奖杯：我们从第一个奖杯开始，逐个检查每个奖杯。

   • 对于每个奖杯 ，我们检查是否存在一个奖杯 （其中 ），使得 。
   • 如果存在这样的奖杯 ，那么 dp[i] 就等于 dp[j] + 1，因为我们可以把  加到以  结尾的等差数列后面，形成一个新的等差数列。
   • 如果不存在这样的奖杯 ，那么 dp[i] 就等于 1，因为以  结尾的等差数列只能包含  本身。

4. 更新位置：在检查完每个奖杯 之后，我们更新 last[A_i] 为 ，以便在后续的检查中快速找到 的位置。

5. 计算总方案数：我们把所有 dp[i] 的值加起来，得到总方案数。

6. 取模

1. 代码

额，写到这里，其实我也不会。

因为我根本不会哈希表和动态规划，今天马上学