Ender_hz: 直接考虑面积 $S=1+2+\cdots +n=\dfrac{n(n+1)}{2}$，可以证明这样拼成的矩形周长最小（最长边长度 $\ge n$）。

Ender_hz: 一开始想着答案可能的范围，最后发现二分的时候好像用不到。

+1: 二分模板没改完全（边界）；

+2: 瞎改一通，避免了编译时的 warning；

+3: 重构代码，把用数组维护边界改成了在 check 内部找边界；

+4: 发现了 tm 没有赋初值导致的二分越界和全部为 $1$ 的情况，但是没有考虑全部为 $0$ 的情况；

+5: 发现了全部为 $0$ 的情况以及判定边界能否覆盖时的错误。

_istina_: 最幽默的一集，封榜后才成功签到。定义【神秘异或】的运算结果是把异或从低位数起第偶数个 $1$ 删去。给定 $n$ 个正整数，求所有无序对神秘异或和。考虑按位考虑，当前对 $(n, m)$ 在第 $i$ 位对答案有贡献当且仅当 $(n\oplus m)_i == 1$ 且 $\sum_{j=0}^{i-1}(n\oplus m)_j$ 是偶数。注意到 $\sum_{j=0}^{i-1}(n\oplus m)_j = \sum_{j=0}^{i-1}n_j + \sum_{j=0}^{i-1}m_j - 2 \sum_{j=0}^{i-1}(n\& m)_j$ ，而最后一项是偶数，因此只需要分别考虑 $n$ 和 $m$ 各自前 $i$ 位和的奇偶性。开四个变量分别记录当前位为 $0/1$，低位和为 $奇/偶$ 的数量即可，将各位贡献累加即可。

这题的难度相当一部分来自于冗长的题面，我费了老大劲才把原题面中 Civilization VI 的元素换成了数学语言。赛时也是被这题面吓到以为是大模拟。

首先显然可以二分答案，将问题转化成给定 $p$ ，判定方案存在性。

考虑 $dp$ 来做。令 $dp_{i,j,l}$ 表示前 $i$ 次操作中，已经使 $a_j=0$，选择了 $l$ 次 $b_{\{j + 1 \ldots n\}}$ 中元素的情况下 $cnt$ 的最大值。

设 $sum_i = m+\sum_{j=1}^{i}k_j$ ，有如下三种转移：

• 第 $i$ 次操作选择增加 $cnt$：

$$ dp_{i,j,l}+sum_j\to dp_{i+1,j,l+1} $$

• 通过若干次操作使 $a_{j+1}\to0$（未触发 $a_i\to \max\{a_i - c_i, 0\}$）：

$$ dp_{i,j,l}\to dp_{i+\left \lceil \frac{a_{j+1}}{sum_j} \right \rceil,j+1, l+\left \lceil \frac{a_{j+1}}{sum_j} \right \rceil} $$

• 通过若干次操作使 $a_{j+1}\to0$（触发 $a_i\to \max\{a_i - c_i, 0\}$）：

$$ dp_{i,j,l}\to dp_{i+ \left \lceil \frac{a_{j+1} - c_{j+1}}{sum_j} \right \rceil,j+1,l-\left \lceil \frac{b_{j+1}}{p} \right \rceil + \left \lceil \frac{a_{j+1} - c_{j+1}}{sum_j} \right \rceil} $$

其中 $l-\left \lceil \frac{b_{j+1}}{p} \right \rceil + \left \lceil \frac{a_{j+1} - c_{j+1}}{sum_j} \right \rceil \geq 0$ 。

存在某 $dp_{i,j,l}\geq s$ 则方案存在。

注意写好转移时的边界条件，并特判 $p=0$ 的情况即可。

时间复杂度 $\mathcal O(t^2n\log b)$ ，可以通过本题。

Ender_hz:

_istina_: 在宿舍里打的究极坐牢场，到都签不出。

MeowScore: