sunzhihong edited 1 年，7 月前
宝石划分：
题意为如果 $N$ 不是 $M$ 的倍数就一直让M减1，直到 $N$ 是 $M$ 的倍数。
根N的复杂度找出 $N$ 的所有因子，找到比 $M$ 小的最大的那个因子就是最终的人数，再输出 $N/M$ 即可。
另一种做法：设最终每人分配到的宝石个数为 $X$ ，则有关系 $M*X=N$ ，因此如果在输入之后如果 $M$ 大于 $10^6$ ，则让初始的 $X$ 不断加 $1$ ；否则就按照题意让 $M$ 不断减 $1$ 即可
$f[i][0/1]$表示考虑到第 $i$ 位是不是以 $o$ 为结尾的个数，考虑到每个字母长度不一样，从前往后转移比较方便。
注意划分后的每个摩斯电码都必须是26个字母中的一个。
首先，我们询问20个元素的完全图，每个元素的值是所有和他有关的询问的结果的“或“
这是因为，假设一个询问的结果在某一位上是1，那么询问的两个值在这个位置上面一定是1
这个值猜测错误的可能性是，当前值在某一位上是1，但是另外19个元素的值是0，这个可能性很小
于是我们得出20个元素的值，其中大概率有两个值的“或”的结果是全1
考虑两个随机值或的结果，每一位是1的可能性是3/4，总的可能性是 (3/4)^10
20个元素相当于190次随机，成功一次即可。这个概率也是非常大的
于是，我们有两个或的结果全1的数字，2n询问剩下的数字即可。
数据是随机数据，不再下发
回文串构造时可看做左右两半部分；一开始将每个字符串放进优先队列（在左 (l, empty, cost) 和在右 (empty, r, cost)）。然后每次 1~n 加入新的字符串在当前节点字符串短的一侧，看能否抵消（回文）。如果能有一边全部抵消，则将剩下部分加入优先队列。直到一边回文或者两边都空。