[CF1299E]So Mean

这个题我想了一天多,感觉比较巧妙。
直接说一下我的做法吧。
首先考虑一个分治做法。如果元素个数小于等于2,则直接结束,否则第i层的分治按按$\mod 2^i$后的结果分成2组,递归下去做。最后合并结果。
考虑建出这棵分治的树,不妨令每一个叶子节点深度相等。(因为最终状态是1或2均可)。那么第i层的组分别代表$\mod 2^{i-1}$的不同值。
对于第i层,我们已知有$2^{i-1}$组元素,如果这其中存在元素个数小于2的组,那么就说明这是叶子,不需要再分了。否则考虑每一组各随机取两个元素,可以发现这个和一定是$2^{i-1}$的倍数。
如果按余数排序,此时第j组的元素一定可以表示成$2^{i-1}k+j$的形式。
那么随机取数的和就是$\displaystyle\sum_{j=0}^{2^{i-1}-1} (2^{i-1}\times k_{i,1}+j)+(2^{i-1}\times k_{i,2}+j) \equiv 2\times \frac{2^{i-1}(2^{i-1}-1)}{2} \equiv 0(\mod 2^{i-1})$
此时我们正好取了$2^i$个数,而且可以发现,这个结果在模$2^i$意义下只有两种取值。
我们可以利用这一点来依次将每一组分别分成两组即可生成递归树上的下一层。
具体分法是:设原先的取的集合为S,令第j组在其中的一个元素为$a_j$,令一个为$b_j$,在这组中再找一个元素$x$,只需要判断$query(S)$与$query(S-\lbrace a_j\rbrace+\lbrace x\rbrace )$是否相等即可判断$a_j$与$x$是否在同一组。最后$b_j$可单独处理。
分治过程一开始每组取两个出来询问一次,对于一个大小为x的组再询问$x-1$次,所以总共的询问次数不超过$n(\lg n-1)+\lg n$次。按n=800来算,这部分大约用掉了$8n$次询问。
然后考虑合并结果。可以发现分成的每一组几乎都有两种不同的结果,我们只需要记录其中的一种即可。
对于一组中的元素个数是奇数的情况和个数是偶数的情况有很大区别。我们可以分开来考虑。
对于偶数的情况,最大值和最小值分别存在于两组中,并且我们可以轻松找到最大值或最小值的两个位置(虽然并不知道哪个是最大值,哪个是最小值)。
求法是:
对于$\mod 2^i$意义下的组,设这些元素排序后依次为$g_1,g_2,g_3,…,g_m$,设$F_i=query(\lbrace g_j|1\le j\le m,j\not =i\rbrace )$,则可以发现$F_i=\lbrack i==1 or i==m\rbrack$。意思就是依次把每个元素去掉询问一遍,返回值为1的两个元素分别是最大值和最小值。
我们可以以此确定两组的相对位置来确定下这组的答案。
对于奇数的情况,最大值和最小值都在其中一组中,而从返回答案来看,最大值和最小值已经在之前的操作中求出了。那么我们可以去掉其中一个,然后将其变为偶数的情况,做完再将去掉的元素加回去。
加个优化,由于最大值和最小值只可能在之前两组的最大值和最小值中出现,所以对于偶数我们只需要询问之前的极值位置,最多询问4次,对于奇数我们只需要询问较小组的极值位置,最多询问2次。
所以就做完了。总询问次数不超过$4n$,期望情况下可以更低。
对于$n\le 800$,总询问次数不超过$12n+9$,期望情况下只有$10n$左右的样子。
交上去吊打std,cf上暂时登顶。

Tagged with:

发表评论