(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 礼物
动态规划，背包。
数据范围很小，这是一个非常简单的无穷背包计算方案数。
因为是无限背包，所以是从1(2)到k的循环，对于每个物品循环一次即可。

T2 麻婆豆腐
概率/计数题
首先注意到，必须选的集合中有一个数字精确的是0.5，才能保证选的集合中异或起来是1的概率是0.5。

T3 寻宝
动态规划
是一个简单的动态规划……但是会爆栈，需要非递归实现。 每个点出度为1，那一定是一个内向树，中间一个环，外面所有点指向中间。 先处理里面的环，然后计算外面的树的情况。

T4 最短路2
简单计算几何
不借助直线的话，就是曼哈顿距离。 借助直线的话 从起点走到直线，只沿着x方向走，只沿着y方向走，两者中一定有一个是最优解之一。 从直线走到终点类似，这样相当于一共4个决策。
每个都求出来就可以了。

T5 托米历险记
模拟，记录3种面值剩余的个数即可。
收到25肯定没问题。收到50找钱，只有找25一种可能。 收到50找钱，需要找75，如果有50的话，试图找50和25，如果没有50的话，试图找3个25。 按照这个规则模拟就好了。

T6 填数字
模拟
首先因为没有0的问题，位数越多一定越大。 想要位数最多，先假设全部填ai最小的数字i。 能填n/ai个。（如果一个都填不了，就是无解） 然后从高位到低位，依次填，能填的最大的数字。（即保证能填的位数不变的前提下，该位最大） 注意这样的情况，3的代价是3，4的代价是4，n=11 最优解是443，即除了最高位之外，也可能和ai最小的i不同。

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305