12月月考题解

· · 个人记录

T1 火柴棍

题意简述

答案对

998244\textcolor{#E74C3C}{8}53 998244\textcolor{#9D3DCF}{8}53 998244\textcolor{#7E0C6E}{8}53 998244\textcolor{#52C41A}{8}53 998244\textcolor{#3498DB}{8}53 998244\textcolor{#0E1D69}{8}53

取模！

解题思路

在赛时我打了 30% 数据强度的搜索，发现一种贪心策略：先保证拼出的数的位数小，再保证大小。因为 8 所需要的火柴棍数量最多（7 根），所以尽可能的拼 8，然后再考虑剩下的数。

赛时因为懒没把 1-30 所有的数打表出来，没发现 17 其实并不满足上面的贪心策略，18 以后就满足了，导致挂分。

代码实现

先打表打出 2 - 17 的答案，然后递推至 100000。

T2 游戏

永远的7日之都！

解题思路

因为 n \times m \le 30，所以可以爆搜，只需要在传参的时候补上上一步走的方向。题目并没有要求方案最优，所以我们只要搜到了一种可行路径，就里面把所有的分枝剪掉（剪枝× 除根√）。

代码实现

咕咕咕...

虽然但是，为什么我把 Debug 用的代码交上去了啊喂！

T3 第K排列

解题思路

枚举 ？ 所有的可能，先枚举字典序大的，再用可行性剪枝，怎么剪呢？用 dp！令 f_{i,j} 表示 i - n 最大能产生的价值。j 的取值只有 0,1,2,3，分别对应：N O I P。

代码实现

搜索传参：第几位，已经确定的价值。

T4 成绩单

解题思路

咕咕咕...

真的还不会