Sweetlemon 的博客

Sweetlemon 的博客

异或粽子——玄学复杂度的神奇分治法

posted on 2019-07-06 21:35:51 | under 题解 |

异或粽子——玄学复杂度的神奇分治法

引子

似乎大家的做法大多都用到 Trie?蒟蒻不熟悉 Trie,更不会可持久化 Trie,所以……

前几天听学长说这题是毒瘤 Trie,没想到今天模拟考就用了这套题……当时看到题面的时候我的内心是崩溃的。

于是——赶紧写个暴力!

暴力分还是挺好拿的——枚举所有连续子段,求出其异或值,把所有的连续子段的异或值排序,取前 $k$ 大相加即可。写完暴力,不甘心只拿这些分的我就开始想一个能拿更多部分分的算法。

思考

看到位运算,我想到了按位处理。

考虑最高位——只有最高位为 $0$ 的数和最高位为 $1$ 的数异或起来才能最高位为 $1$ 。自然,最高位为 $1$ 的异或值一定比最高位为 $0$ 的异或值大。

因此,如果最高位为 $1$ 的异或值已经多于 $k$ 个,那么前 $k$ 大只能从这些较大的异或值里取;否则,所有最高位为 $1$ 的异或值都在答案范围内,并且还要取一些最高位为 $0$ 的较小异或值补足 $k$ 个。

上面就是本解法的基本思想。