2024.7.2 集训

### 数位 DP

1. 记录：1. 是否顶上限；2. 是否当前填了的都是前导 $0$；3. 当前位是否是从左往右数第一位。（2 和 3 是两种做法，2 是在 Query 里只调用一次 DFS，3 是在 Query 里枚举第一个非 $0$ 位调用多次 DFS）。
2. 记忆化的数组可以不用记所有内容。
3. 注意 DFS 返回时要返回 res，而不是记忆化的数组里的内容，因为记忆化的数组记的不是所有内容（如果这样写的话）。
4. 注意特判。比如左边界 $- 1$ 变成了 $- 1$。还有 $0$ 的情况。
5. 注意算的是 $[1, n]$ 的答案还是 $[0, n]$ 的答案。
6. 注意给记忆化的数组赋初值为 $- 1$，注意要不要多次赋初值（注意在哪里赋初值）。
7. 可以用 $[0, 9]$ 以外的数来表示之前没填的数位（前导 $0$），如用 $10$。一般不用 $- 1$，因为数组的下标没有 $- 1$（？）。
8. 在 Query 里枚举第一个非 $0$ 位的写法中，注意不是每次都是一来就顶上限，而是只有 i == pos 时才一开始就顶上线。

写法：

1. 记录填了的是否都是前导 $0$，在 Query 里调用一次 DFS。
2. 记录当前位是不是第一个非 $0$ 位，在 Query 里枚举第一个非 $0$ 位，多次调用 $DFS$。
######
1. 记忆化的数组只记录一部分内容。
2. 记忆化的数组记录全部内容。

### 贪心

可以考虑从之前的某个假设最优的情况开始分析。如：例4：大神排队。

不确定贪心的正确性时，可以能写暴力的写暴力，暴力过不了的部分再用贪心。（先暴力后贪心）。

### 状态压缩

可以把 max(a, b) 或 min(a, b) 的结果用 0 或 1 来表示（0 表示是 a，1 表示是 b）。如：P1648 看守。