【IOI2016】解读bug

题意:有一个未知排列\(p\),给定一个空集合,可以向空集合中插入不超过\(w\)个\(n\)位二进制数,插入完毕后每个数的第\(i\)位会变为原来的第\(p_i\)位,然后你可以查询不超过\(r\)次某个\(n\)二进制数是否在集合内,最终确定排列\(p\)。

 

考虑使用整体二分的思想。

要确定\([l,r]\)中每个数在排列\(p\)中的位置,我们可以先确定\([l,m]\)以及\([m+1,r]\)在排列\(p\)中位置的集合。对于\([l,m]\)将只有该位为\(1\)的数插入,然后对于\([l,r]\)查询该位为\(1\)的数是否出现。出现的个数\(1\)的位置集合即为\([l,m]\)对应的集合。再递归向下做即可确定每个数的位置。

但到了下一层插入和查询的数不能和上面的相同了。于是我们可以将不在当前区间的数位全部记为\(1\)来区分(当然也可以使用一些其它的技巧,只要能区分开即可)。这样插入和查询的次数都是不大于\(n\lceil logn\rceil\)次的,即可通过(插入实际上只有一半)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz