251107 模拟赛

T1

直接 dp 即可

T2

直接贪心即可

T3

给你 \(n\) 个 \([1,m]\) 之间的数，找出两个不同且无交的子集，使得两个子集的和在模 \(m\) 意义下相等。\(n\le 1000,~m\le 10^{18}\)

直接生日悖论可以做到 \(O(\sqrt m)\)，考虑优化。发现时间复杂度太高的原因是随机生成的集合的和模 \(m\) 的结果太大。考虑缩小值域，设置阈值 \(B\)，我们可以在 \(O(\frac{m}{B})\) 的期望时间内获得一组值域小于 \(B\) 的解。这样复杂度为 \(O(\frac{m}{\sqrt B})\)，疑似没有优化。\(\sqrt B\) 似乎不能降低，考虑优化 \(\frac{m}{B}\)。我们将序列分三段，在每一段中各找 \(B^{1/6}\) 个不超过 \(\frac{B}{3}\) 的解，然后从每组各取一个解，加起来得到一组 \(\le B\) 的解，时间复杂度 \(O(\frac{9m}{B}B^{1/6}+\sqrt B)\)。稍微调调参就能过了。

如果不缩小值域但直接分块，由于瓶颈在于 \(\sqrt m\) 的哈希找生日碰撞，因此不能起到优化作用。

求导可得块数取 \(\frac{n}{e}\) 最优（是这样吗？），反正取 \(3\) 能过。

fjj的爆标做法：排序后做差分，重复 \(6\) 次，大概率出现相同的数。在差分序列对应原序列上的数字不相邻的情况下，可以通过差分序列的解推出一组原序列的解。相邻的概率不是很大。

T4

给你 \(n\) 个数，每次你可以选一个集合，将每个数变为集合中所有数平均值向下取整之后的结果。最小化最终的最大值。

去掉最大值之后答案一定不会变大，并且可以构造前 \(6\) 个数的答案为最终答案，因此前 \(6\) 个数的答案等于最终答案。

进行爆搜和减枝，发现最大值和最小值的差距不是很大时 \(\le 2^{n-1}\)，可以删去最大值。可以把所有数都减去最小值来减小状态数。卡卡过了。