比赛补题
Codeforces Round 960 (Div. 2)
这次比赛可以看出最近的代码准确度又在下降，A - C 题不能快速的做出来，且一共吃了 6 发罚时，这说明了代码准确度练习较少已经到了非常严重的地步，最近难题看的较多又失去了对简单题的熟练度，其实也可以说明之前练的还不够，有一定的效果，但随着时间的推移有所反弹。
当然，心态可能也对考试时的发挥有所影响，在做前面的题目时有可能操之过急，导致了悲剧的发生。
计划：在 2024/07/21 - 2024-07/27 每天一场 CF EDU 暂时先不管难题，巩固基础为重，难题只是陪衬。值得一提的是不能排除晚上状态不好所造成的影响.
Educational Codeforces Round 162 (Rated for Div. 2)(CF1923)
彩笔 PMC 不会二分，距今 0 天，望周知。
A - C 简单
D
二分二分！！！
二分该在什么时候用？排过序，单调的就可以用！可以用在什么地方？前缀和！
考场上想错了两个点：
- 只要两只史莱姆不是等价的，那么先向左吞，先向右吞是等价的。先考虑序列中相邻元素都不相同的情况，我们要求史莱姆 $i$ 的答案，定义 $l < i < r$ ，且
\sum_{l \le x < i} a_x > x_i，\sum_{ia_i ，所有答案即为 \min\{i - l, r - i\} 。
- 那如果有相邻的元素相同呢？考虑记录一个 $k$ ：使得区间 $[i + 1, k)$ 均为相同元素，处理完后，对刚刚所求的答案取 $\max$ 。由于处理了 $k$ 的缘故，在答案为 $1$ 的时候需要特判，请读者自行思考。
- 可以分开处理左边和右边的情况，写好一种情况后
reverse 即可。
处理 $k$ 的时间复杂度为 $O(n)$，第一步可以通过二分实现，总时间复杂度 $O(tn\log n)$
总结：此题巨大的数据范围暗示了使用 $\log n$ 的算法，前缀和数组是有序的，二分只能用于有序的情况，若数组中含负数则不行。
二分的常见场景：求最大值最小，最小值最大，有序数组中查找（这道题就是这个）。
Codeforces Round 925 (Div. 3)(CF1931)
A- D 简单
F
将题目条件转化一下，相当于就是给了一堆先后关系，考虑将前面的与后面的连边，也就是 $a{ij} \rightarrow a{ij+1}$ 连边，然后用拓扑判环，如果无环则有解，反之亦然。
总结：
- 对于题目中有一堆关系时，可以互相连边，若有环，则说明了关系不成立。
- ❓连边还适用于排序类问题。
G
四个拼图，其个数记为 $c_1,c_2,c_3,c_4$ ，分析拼图的凹凸性，只有拼图 1、2 会改变整个序列的凹凸性，且 1、2 拼图只能交替拼在一起。
那么可以得到，若 $|c_1-c_2| > 1$ 则问题无解，否则一定有解，而且拼图 3、4 并不会相互影响，我们可以进行分类讨论。
-
若 $c_1 = c_2 = 0$ ，且 $c_3\neq 0 且 c_4 \neq 0$ ，则无解，否则方案数为 1。
-
若 $c_1 = c_2$ ，有两种情况：
- 若 1 开头，那么 3 有 $c_1$ 个地方可以插入，4 有 $c_1 + 1$ 个地方可以插入，方案数为 $\binom{c_1+c_3-1}{c_1-1} \binom{c_2+c_4}{c_1}$ 。
- 若 2 开头，那么 3 有 $c_1 + 1$ 个地方可以插入，4 有 $c_1$ 个地方可以插入，方案数为 $\binom{c_1+c_3}{c_1} \binom{c_1+c_4-1}{c_1-1}$。
总方案数为二者的和 $\binom{c_1+c_3-1}{c_1-1} \binom{c_2+c_4}{c_1} + \binom{c_1+c_3}{c_1}\binom{c_1+c_4-1}{c_1-1}$。
-
若 $c_1 = c_2 + 1$ 拼好 1,2 只有一种方案，3,4 均有 $c_1$ 个地方可以插入，方案数为 $\binom{c_1+c_3 - 1}{c_1 - 1} \binom{c_1+c_4-1}{c_1-1}$。
-
若 $c_1 = c_2 - 1$ 拼好 1,2 也只有一种方案， 3,4 均有 $c_1 + 1 $ 个地方可以插入，方案数为 $\binom{c_1+c_3}{c_1} \binom{c_1+c_4}{c_1}$。
预处理组合数，$O(1)$ 询问即可。
总结：
- 若有无解的情况，可以先分析无解的情况。
- 若某项事物对于某些性质没有改变，则无需在意，优先分析情况比较少且对某些性质（比如说有无解）有影响的。
杂题选做
一眼和 2、5 因数有关系。
额，然后就不会了。
我们定义 $p5$ 代表数字 5 的最大次幂，$p5(i)$ 代表数字 $i$ 5 次幂的数量；$p2$ 同理。
定义 $dp(i, j, k)$ 代表我们已经遍历了 $i$ 个数，选择了 $j$ 个所得到的 5 的次幂的数量为 $k$ ，所得到 $2$ 的次幂的最大值。这就是经典的背包问题。我们分为两种情况，列出如下转移方程。
- $dp(i + 1, j + 1, k + p5(i)) = \max(dp(i + 1, j + 1, l + p5(i)), dp(i, j, k) + p2(i))$
- $dp(i + 1, j, k) = max(dp(i + 1, j, k ), dp(i, j, k))$
因为一个 0 是由 一个 2 和 5 相乘得到的，最终的答案为 $\min(i, dp(n, k, i))$ ，这里的 $k$ 是题目中给定的 $k$ ，但是上文的不是，我懒得改了将就看。
时间复杂度 $O(n^3)$
总结：分析性质，尝试将某些值看成贡献