我也不知道我在总集什么但总之 2026 题目总集

2026.3.31 定时训练

CF573D Bear and Cavalry

总之我只会 $O(nq)$。将 $w$ 和 $h$ 分别排序，存一下每个战士对应的马，每次修改直接交换。每次询问从前到后统计答案，只需要这一个对应，然后左右两个交叉对应，然后三个对应，这几种情况取最大就行。

CF838D Airplane Arrangements

方案数也可以转成概率乘总方案数。我们将问题转换为每个人随机指定一个位置并开始走，求最后合法的概率。那这样仍然是求解困难的，我们可以将其想象成在一个长度为 $n$ 的环上顺时针或逆时针走，那就可以在 $1$ 与 $n$ 之间加入一个虚点表示无解。

则问题转为统计给一个 $n+1$ 的环分配 $m$ 个人任意走最后使得 $n+1$ 没有被占据的概率，一个位置被占据的概率为 $\frac{m}{n+1}$​，可以得到答案发生的概率为 $\frac{n+1-m}{n+1}$，乘以方案数 $(2 \times (n+1))^m$ 即可。