10.12

押题卷01

B

最优路线应该是，上面一个阶梯型，下面一个反着的，这样是最好，走势如下，最优的选择，那么我们就进行dp，将上下两个梯形进行dp，然后需要减去中间那一行的，但是，要注意这样会超时，那么，根据过程，一定会超时，复杂度 ​O(n^2)，过不了，不可以总司令！但，我们只好发现转移过过程可以用单调栈优化，最后在进行转移即可。

C

首先，注意一下，我们需要注意下， 先枚举一下起点，再枚举一下终点，然后再进行算，然后要注意一下，因为，数组太大，内存会爆掉，所以要用bitset,然后注意到bitset也会爆掉，所以需要进行分块，对于每一次区间，去进行进行操作，然后即使清空内存

D

扫描线，略，蒟蒻不会QwQ

押题卷02

B

该题看似不可以DFS，实则可以，而当n = 45时，你一共拆出来的方案才大约 ​5 * 10^5左右（小店解析：要注意一下，DFS的时候，你应该枚举的​i应该​lst_i \leq i \leq n - sum，减少时间复杂度，然后，我们再去按照题目中去模拟即可

D

注意到这道题实际上只是一个 二叉树 所以，我们，就可以按照情况分类讨论一下，即只有一个儿子，和两个儿子的情况，然后设 ​dp_{i,j} = 以i个子树为根，放了j个硬币，最后按照状态，进行转移即可，注意计算组合数时，要逆元，注意到模数时指数，所以可以大胆算，可以用线性递推的方法来计算

模拟卷01

C

该题设 ​dp_{i, j, k} = 有i个1，j个0, s_{i + j}的值为k的结果，则 ​dp_{i, j, 0} = \sum _{t=1}^{i} dp_{i - t, j, 1} + dp_{i, j, 0} ，​dp_{i, j, 1} = \sum _{t=1}^{j}dp_{i, j - t, 0} + dp_{i, j, 0}，然后答案为 ​dp_{n, m, 0} + dp_{n, m, 1}, 记得取模

模拟卷02

C

设 ​dp_{i,j,k} = 表示第i天，选了j个物品，在k安全区度夜的最大方案，那么我们不难列出转移式，但后有一个问题需要处理，求value二维数组，此时我们其实可以进行BFS一下去求，最后，要注意，体力值不能超过k