「Summary」2022-08-11 做题记录

自闭了两天，把题解补上。

2022-08-11

$\mathbb{CF376E}$

link

我会开空间

一眼 vector 能做，细想其实不需要。
积累一个技巧，把一个区间拆成左右两个端点分开考虑。
考虑定义 $dp_{i, j, k}$ 表示前 $i$ 个点选了 $j$ 个左端点，选了 $k$ 个右端点。
为什么可以这样定义呢？
设想有两个左端点和两个右端点分别是 $l_1, l_2$ 和 $r_1, r_2$ ，组成的两个区间分别是 $[l_1, r_1]$ 和 $[l_2, r_2]$ 要满足这两个区间不存在包含关系，则应该满足的条件是 $l_1 < l_2, r_1 < r_2$ 或者 $l_1 > l_2, r_1 > r_2$ 具象一点，就是说同在中间的两个左右端点不会组成一个区间，推广来讲，把左端点和右端点都有序排列，则一定是 $l_i$ 和 $r_i$ 配对（当然要在保证能全部匹配的情况下）。
则有可能出现失配，则需要保证在每次转移时左端点的数量要大于等于右端点的数量。
则在不考虑题目限制的情况下，转移方程可以为 $dp_{i, j, k} = dp_{i - 1, j, k} + dp_{i - 1, j - 1, k} + dp_{i - 1, j, k - 1} + dp_{i - 1, j - 1, k - 1}$ ，简单来说就是 $i$ 这个点做不做左 / 右端点的讨论，再看到限制 $x$ 必须为左端点，则转移少掉不做左端点的两类就行 $dp_{i, j, k} = dp_{i - 1, j - 1, k} + dp_{i - 1, j - 1, k - 1}$ 。最后要看到题目规定区间无标号，则 $Ans = dp_{m, n, n} \times n!$
考虑空间问题，第一维可以滚掉，但是还是卡不下，可以用 vector ，但其实没必要，观察 $n \times m \le 100000$ ，考虑 $n > m$ 显然方案数为 $0$ ，则在 $n \le \sqrt{100000}$ 的情况下才有必要算，那么空间就正确了。

$\mathbb{CF140E}$

link

伏笔

为什么要叫伏笔呢？因为下面还有一道题的思想和这道题很类似。
看到题很麻，这个翻译太含糊了，We consider unordered sets (not multisets) 都没翻译出来。
首先发现两行之间的判重不是很好弄，则把行与行之间分开，考虑单行的简单情况（不考虑颜色标号），可以定义 $f_{i, j}$ 为第 $i$ 个位置用了 $j$ 种颜色的方案数，转移为 $f_{i, j} = f_{i - 1, j - 1} + f_{i - 1, j} \times (j - 1)$ ，最后考虑颜色是有标号的，则所有的 $f_{i, j}$ 都还要再乘上 $j!$ 。
再考虑行与行之间怎么合并，定义 $dp_{i, j}$ 表示第 $i$ 行，用了 $j$ 种颜色的方案数（考虑标号）。先不考虑限制条件，则 $dp_{i, j} = \sum_{k = 1}^{\min (l[i - 1], m)} dp_{i - 1, k} \times f_{l[i], j}$ 。思考在甚么情况下会重，用的颜色数不同则绝对不会重，在颜色数相同时会重 $dp_{i - 1, j} \times f_{l[i], j}$ 次。
最终得到的式子就是
$$ dp_{i, j} = A_{m}^{j} \times f_{l[i], j} \left(\sum_{k = 1}^{\min (l[i - 1], m)} dp_{i - 1, k} - dp_{i - 1, j}\right) $$

$\mathbb{CF1523E}$

link

精巧

从期望的定义入手 $E = p_{i} \times i$ ，其中 $p_i$ 表示恰好在第 $i$ 次停止操作的概率。
恰好相当难弄，不妨再对式子转化一下
$$ \begin{aligned} E &= p_{i} \sum_{j = 1}^{i} 1 \\ &= \sum_{i = 1}^{n} \sum_{j = i}^{n} p_j \end{aligned} $$
令 $P_{i} = \sum_{i + 1}^{n} p_i$ ，这个是个后缀，分析发现它是有意义的，表示操作到第 $i$ 步还没有停止的概率。
发现这个挺好算的，就是说 $n$ 个点，选 $i$ 个，使得两两之间满足距离不小于 $k$ ，把一个点和它后面的 $k - 1$ 个点绑在一起会比较好算，现在就变成 $n - (i - 1) \times k + (i - 1) = n - (i - 1) \times (k - 1)$ 个点中选 $i$ 个的方案数，为 $\binom{n - (i - 1) \times (k - 1)}{i}$ ，概率为 $\large \frac{\binom{n - (i - 1) \times (k - 1)}{i}}{\binom{n}{i}}$ 。
算到了 $P_i$ 则 $Ans = \sum_{i = 0}^{n} P_i$ 就好算了，只需要注意 $P_0$ 恒为 $1$。

$\mathbb{CF1237F}$

link

草蛇灰线，伏延千里

其实和上面那道题关系不算太大，但是有相同的解决问题的途径。
这里指冰冻罗非鱼二向箔打击。
二维的转成一维考虑。

发现这个骨牌很难受，横纵不一，下不了手。
利用相同的想法，把这个考虑行，再把行列合并。
考虑一个单行 $f_{i, j, k}$ 表示，放到了第 $i$ 个位置，有 $j$ 占两格，有 $k$ 个占一格。
这个是 $\Theta(n^3)$ 的，其实不需要记录 $k$ ，因为只要有一个空就能放，那么我只要知道这一行的空格数就能算放 $k$ 个一格的方案数，即是 $f_{i,j} \times \binom{n - j \times 2}{k}$。
同理可以对列求出 $g$ 。
最后合并行和列时，枚举有 $i$ 个横放， $j$ 个竖放，则方案数为 $f_{n, j} \times g_{m, i} \times A_{cntx - 2 \times i}^{j}A_{cnty - 2 \times j}^{i}$。
为什么是个排列捏？因为你要一一对应行和列！

$\mathbb{CF1188C}$

link

诈骗题

想不到就是想不到。
学会观察。
第一个观察是说排序之后不影响答案。
第二个观察是说单个权值不会超过 $\frac{a_n}{(k - 1)}$ 。
然后 $a_i$ 的范围在 $1e5$ 里面。
可以考虑枚举权值算贡献。
但是怎么算权值恰好为 $res$ 的方案数呢？这样是不好维护的，考虑继续使用套路，转化恰好为不小于，做差分。
设当前枚举了 $res$ 做为权值， $dp_{i, j}$ 表示前 $i$ 个数中选了 $j$ 个且满足要求的方案数， $\sum_{k = 0}^{pos} dp_{k, j - 1}$ 其中，$a_{pos}$ 是满足 $a_i - a_{k} \ge val$ 的最后一个数，这个可以前缀和优化。
其实转化为不大于理论上来说也可以，只不过前缀和要做个差分。