P8019 [ONTAK2015] OR-XOR

发布时间 2023-08-09 20:33:47作者: FOX_konata

原题

一道很好的思维题

首先因为区间操作不太好做,所以我们可以先对所有数做一个前缀异或和,这样原问题就变成了从n个数中选m个数,使得\(Or_{i=1}^{m}{(prexor_{x_i} \oplus prexor_{x_{i-1}})}\)最大

然后这里有一个很关键的想法,我们可以发现or操作只要某一位有1,则答案一定为1,所以我们虽然把\(prexor_{x_{i-1}}\)疑惑掉了,但在\(i-1\)时刻他已经被算了一遍。

如果此时他对某一位产生了1的贡献,则再or上一次答案是不变的;而如果没有产生贡献,再or一次也不会有贡献

因此,我们就把原问题变成了从\(n\)个数中选\(m\)个数,使得\(Or_{i=1}^{m}{(prexor_{x_i})}\)最大

所以我们考虑求出前缀异或和后按位贪心,我们可以发现如果对于某一位他满足不和高位冲突的0的数量<m,则这一位是不可能产生1的贡献的。

而如果0的数量>=m,也不一定有答案,因为不要忘记第n个数必须被选,所以要保证当前这一位\(prexor_n = 0\)

我们可以记录数组\(b_i\)表示第i个数前j位有哪些数不能选,更新即为\(b_i = b_i | (prexor_i >> j \& 1)\)

复杂度\(O(nloga)\)