[JZOJ4937] 与运算

Description

Solution

设 F[i] 表示当前前若干项异或起来为 i 的最大答案

考虑转移。

显然我们可以只转移i的一个二进制位。

找一位去掉，设去掉后为 j ，并求出有多少个a能包含 j 而不包含i（包含指 i 的所有1的位在这些a上对应的位也是1）

设 num[i] 表示有多少个包含 i 的。

显然包含j一定包含 i

因此求的值就是num[j]−num[i]

然后直接转移即可。

关键在于预处理num

直接递推会有重复，怎么办呢。

观察特性

0 ~2m−1处理

可以分成 [0 ~ 2m−1−1],[2m−1 ~ 2m−1] 两部分，前一部分 2m−1 这一位是0，后一部分这一位是1。

所以显然后一部分每一个的 num[i] 可以转移到前一个的 num[i−2m−1] 中。

然后其他的 m <script type="math/tex" id="MathJax-Element-3542">m</script>也类似，可以用分治的办法在两个区间分别下去。

为了避免重复，返回的时候再转移。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 1000005
#define M 1048576
#define LL long long
using namespace std;
int n;
LL a[N],num[M+],f[M+],lim;
void fd(LL l,LL r,LL c)
{
    LL mid=<<(c-);
    if(l>=r-) return;
    fd(mid+l,r,c-);
    fd(l,l+mid,c-);
    fo(i,,mid-) num[l+i]+=num[l+i+mid];
}
int main()
{
    cin>>n;
    memset(num,,sizeof(num));
    fo(i,,n) scanf("%lld",&a[i]),num[a[i]]++,lim=max(lim,a[i]);
    fd(,lim,);
    LL ans=;
    fod(i,min(*lim,(LL)M),)
    {
        fo(j,,)
        {
            LL p=<<j;
            if((i&p)>) f[i-p]=max(f[i-p],f[i]+((LL)i-p)*(num[i-p]-num[i]));
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
}