[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;
}