2024.3.7习题总结

CF1288C

题目

可以把 \(a\) 数组和 \(b\) 数组的倒序合并, 这样, 题目就成了求出长度为 \(2m\) 的序列递增的方案数, \(dp\) 求解

可以把长度为 \(2m\) 的差分数组。
对于任意一个 \(c_i\), \(c_i \ge 0, \sum c_i \le n\), 所以方案数为 \(C_{n + 2 * m - 1}^{2 * m}\)

CF1569C

题目

如果一个排列 \(a\) 是一个好的发言顺序, 那么 \(max(a_i)\) 出现最少两次或者次大值有一个在最大值前面

分成三种情况

• \(max(a_i)\) 出现多次 任何一个排列都是合法的
• 次大值 \(<\) \(max(a_i)\) - \(1\) 非法
• \(max(a_i)\) 出现一次

对于 \(max(a_i)\) 出现一次

考虑非法

令 \(ok\) 表示次小值出现的次数

枚举 \(max(a_i)\) 出现的位置 \(v\), 那么所以次小值一定要在这些的前面, 其他的任意排列

非法方案数为 \(A_{v - 1}^{ok} \cdot (n - ok - 1)!\)

用总方案数减去这些非法的就是答案

GYM103117K

题目

贪心让 \(x, x + k, x + 2k \dots \le n\) 的要放在一起

luoguP5520

题目

我们有 \(n - m + 1\) 个土地, 要做这些土地上插入 \(m\) 个花

方案数为 \(A(n - m + 1, m)\)

Gym103117

题目

\(2n\) 为一个循环节, 循环的一起处理

CF1725C

题目

结论, 在元素任意三个点构成的三角形, 如果有一条边为直径, 这个三角形就是直角三角形, 否则不能

对于一条直径, 如果当前直径两点颜色相同, 那么剩下的就不能和它相同。
对于一条直径, 如果当前直径两点颜色不相同, 除了这两个点, 对于其他点的颜色方案不影响

令 \(cnt\) 表示直径的数量

枚举有几条直径两点颜色相等 \(i\), 方案数为 \(C(cnt, i) \cdot A(m, i) \cdot (m - i)^{n - 2 * cnt} \cdot ((m - i) \cdot (m - i - 1))^{cnt - i}\)