20241228 测试笔记

前两题都比较有意思，记一下。

T1

简要题意：有 $n(n\le 50)$ 个宿舍，每个宿舍有 $4$ 个人，其中 $a_i(0\le a_i\le 4)$ 个人有笔记本，现在每个有笔记本的人送给不是同一宿舍的人，每个人只能收一本来自别人的笔记本，求不同赠送方案数。

解析：学 NOIP T2 直接数数显然不可行，如到第 $i$ 个宿舍需考虑前面究竟有多少种送给 $i$ 舍的，多少种没有，具体送了多少……

范围这么小，直接暴力设状态，但过于简单的 dp 显然有后效性，难以维护。所以能不能考虑只往前看？显然可以，分为从前面拿笔记本和送给前面笔记本两种状况。因此可以设 $f_{i,j}$ 表示考虑到前 $i$ 个宿舍，一共还有 $j$ 本笔记本可以往后送。由于有出有入，先枚举转移到的状态再枚举送多少得多少过于复杂，不如直接设送了 $give$ 本，得了 $get$ 本，接着分别计算对答案的贡献。

• 假设 $1\sim i-1$ 中共有 $cnt$ 个人有笔记本，那么显然前面还有 $last\leftarrow 4(i-1)-(cnt-j)$ 个人没有收到笔记本，任意地选 $give$ 个人给，即 $C_{last}^{give}$，$i$ 舍的人给可以一一对应排列，即再乘上 $A_{a_i}^{give}$。

• 得的也差不多，从前面 $j$ 本种任意拿 $get$ 本到自己宿舍并任意分配：$C_j^{get}\times A_4^{get}$。

一番操作下来，现有的能往后送的笔记本数应为 $j-get+a_i-give$，故总的转移为：

$$f_{i,j-get+a_i-give}=f_{i-1,j}\times C_{last}^{give}\times A_{a_i}^{give}\times C_j^{get}\times A_4^{get}$$

时间复杂度 $O(n\times 4n\times 4\times 4)=O(64n^2)$。

反思：切忌固化思维，在 NOIP T2 中看到计数下意识想 dp 浪费 $2\mathrm{h}$，回来做这题下意识直接数浪费 $2\mathrm{h}$，应结合数据实际范围，实现难易程度，正确解决问题。

T2 AT_arc101_b [ABC107D] Median of Medians

解析：看数据范围，能想到考虑每个数作为中位数的区间有多少个，但这样显然不好做。

换个角度想，每个可能成为答案的数都应该满足有 $\lfloor \frac{n(n+1)}{2}÷2\rfloor$ 个区间的中位数比这个数大，答案是满足这个条件数中的最大值，此时，答案显然具有单调性，故二分答案。

二分出来 $mid$ 之后怎么数呢？对于中位数，绝对众数等，都有一个套路：将一类数设为 $1$，另一类数设为 $-1$。这里将 $a_i\ge mid$ 的 $b_i\leftarrow 1$，$a_i<mid$ 的 $b_i\leftarrow -1$。$a_l\sim a_r$ 的中位数比 $mid$ 大，当且仅当 $\sum _{i=l}^r{b}_i\ge 0$。那直接树状数组套前缀和维护即可。具体地，设 $q_i=\sum _{k=1}^i{b}_i$，找 $\mathrm{\forall }1\le l\le r,q_r-q_l\ge 0$，即 $q_r\ge q_l$ 的个数，显然可以树状数组。

时间复杂度 $O(n{\log }^{2}n)$。